A lower bound on the positive semidefinite rank of convex bodies

DOI10.1137/17M1142570MaRDI QIDQ4564016zbMATH OpenOpenAlexWikidataFDO

Authors Hamza Fawzi, Mohab Safey El Din

Publication date 12 June 2018

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.06996

zbMATH Keywords

semidefinite programmingalgebraic degreepositive semidefinite rank

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of higher-dimensional varieties (14Q15)

Abstract: The positive semidefinite rank of a convex body $C$ is the size of its smallest positive semidefinite formulation. We show that the positive semidefinite rank of any convex body $C$ is at least $sqrtlogd$ 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. The proof relies on the B'ezout 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.

Recommendations

• Worst-case results for positive semidefinite rank
• Polytopes of minimum positive semidefinite rank
• The complexity of positive semidefinite matrix factorization
• Lower bounds on the size of semidefinite programming relaxations
• Some upper and lower bounds on PSD-rank

Cites work

• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• A general formula for the algebraic degree in semidefinite programming
• Algebraic boundaries of convex semi-algebraic sets
• Algebraic degree in semidefinite and polynomial optimization
• Dualities
• Generic Spectrahedral Shadows
• Intrinsic volumes of symmetric cones and applications in convex programming
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Lifts of Convex Sets and Cone Factorizations
• On a positive semidefinite relaxation of the cut polytope
• On symmetric and skew-symmetric determinantal varieties
• Positive semidefinite rank
• Smallest compact formulation for the permutahedron
• The algebraic degree of semidefinite programming
• Vertices of spectrahedra arising from the elliptope, the theta body, and their relatives

Cited in

(6)

• Lifting for simplicity: concise descriptions of convex sets
• Bad projections of the PSD cone
• Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
• Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• Limitations on the Expressive Power of Convex Cones without Long Chains of Faces

This page was built for publication: A lower bound on the positive semidefinite rank of convex bodies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4564016)