A lower bound on the positive semidefinite rank of convex bodies - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Applied Algebra and Geometry Année : 2018

A lower bound on the positive semidefinite rank of convex bodies

Mohab Safey El Din

Résumé

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.
Fichier principal
Vignette du fichier
lower_bound_psdrank_revised.pdf (379.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01657849 , version 1 (07-12-2017)

Identifiants

Citer

Hamza Fawzi, Mohab Safey El Din. A lower bound on the positive semidefinite rank of convex bodies. SIAM Journal on Applied Algebra and Geometry, 2018, 2 (1), pp.126-139. ⟨10.1137/17M1142570⟩. ⟨hal-01657849⟩
256 Consultations
106 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More