A lower bound on the positive semidefinite rank of convex bodies

DOI10.1137/17M1142570zbMATH Open1391.90456arXiv1705.06996OpenAlexW2620334136WikidataQ130159436 ScholiaQ130159436MaRDI QIDQ4564016FDOQ4564016

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Lifting for simplicity: concise descriptions of convex sets
• Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
• 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

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)