# A lower bound on the positive semidefinite rank of convex bodies

3 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : The positive semidefinite rank of a convex body C is the size of its smallest positive semidef-inite formulation. We show that the positive semidefinite rank of any convex body C is at least $\sqrt{log d}$ where d is the smallest degree of a polynomial that vanishes on the boundary of the polar of C. This improves on the existing bound which relies on results from quantifier elimination. Our proof relies on the Bézout bound applied to the Karush-Kuhn-Tucker conditions of optimality. We discuss the connection with the algebraic degree of semidefinite programming and show that the bound is tight (up to constant factor) for random spectrahedra of suitable dimension.
Type de document :
Article dans une revue
SIAM Journal on Applied Algebra and Geometry, SIAM, In press, pp.1-14
Domaine :

Littérature citée [19 références]

https://hal.inria.fr/hal-01657849
Contributeur : Mohab Safey El Din <>
Soumis le : jeudi 7 décembre 2017 - 10:45:38
Dernière modification le : jeudi 17 mai 2018 - 10:42:02

### Fichier

lower_bound_psdrank_revised.pd...
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01657849, version 1

### Citation

Hamza Fawzi, Mohab Safey El Din. A lower bound on the positive semidefinite rank of convex bodies. SIAM Journal on Applied Algebra and Geometry, SIAM, In press, pp.1-14. 〈hal-01657849〉

### Métriques

Consultations de la notice

## 190

Téléchargements de fichiers