Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization

DOI10.1137/18M1201342zbMath1420.90043arXiv1806.08656MaRDI QIDQ5742692

Gennadiy Averkov

Publication date: 8 May 2019

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

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

zbMATH Keywords

linear matrix inequalityRamsey theorysemidefinite optimizationconic optimizationpolynomial optimizationsecond-order conereal algebraic geometrysum of squaresextended formulationprojected spectrahedronnonnegative circuit polynomialtruncated quadratic module

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Semialgebraic sets and related spaces (14P10) Ramsey theory (05D10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Lifting for Simplicity: Concise Descriptions of Convex Sets, Sublinear circuits for polyhedral sets, Symmetry Reduction in AM/GM-Based Optimization, Hyperbolic secant varieties of \(M\)-curves, SONC optimization and exact nonnegativity certificates via second-order cone programming, Linear optimization over homogeneous matrix cones, Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023, On eigenvalues of symmetric matrices with PSD principal submatrices, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Terracini convexity, Sublinear circuits and the constrained signomial nonnegativity problem, The \(\mathcal{S}\)-cone and a primal-dual view on second-order representability, The dual cone of sums of non-negative circuit polynomials, Fitting tractable convex sets to support function evaluations, Limitations on the Expressive Power of Convex Cones without Long Chains of Faces, Second-Order Cone Representation for Convex Sets in the Plane, A unified framework of SAGE and SONC polynomials and its duality theory

Uses Software

• Benchmarks for Optimization Software

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Relative entropy optimization and its applications
• Lower bounds for a polynomial in terms of its coefficients
• Handbook on semidefinite, conic and polynomial optimization
• Linear optimization with cones of moments and nonnegative polynomials
• Positive semidefinite rank
• Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
• An independent benchmarking of SDP and SOCP solvers
• Maximum semidefinite and linear extension complexity of families of polytopes
• Combinatorial bounds on nonnegative rank and extended formulations
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• On representing the positive semidefinite cone using the second-order cone
• Lectures on Modern Convex Optimization
• Relative Entropy Relaxations for Signomial Optimization
• Lower Bounds for Polynomials Using Geometric Programming
• An Introduction to Polynomial and Semi-Algebraic Optimization
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• On the Matrix Equation X′X = A
• Lectures on Polytopes
• A Lower Bound on the Positive Semidefinite Rank of Convex Bodies
• On Ranks of Regular Polygons
• Spectrahedral Shadows
• Lifts of Convex Sets and Cone Factorizations
• A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
• Semidefinite Descriptions of the Convex Hull of Rotation Matrices
• Equivariant Semidefinite Lifts of Regular Polygons
• Handbook of semidefinite programming. Theory, algorithms, and applications