Sum of squares generalizations for conic sets

DOI10.1007/S10107-022-01831-6MaRDI QIDQ6038674zbMATH OpenOpenAlexFDO

Authors L. Kapelevich, Chris Coey, J. P. Vielma

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

interior pointnon-symmetric conic optimizationpolynomial optimizationsum of squares

Mathematics Subject Classification ID

Polynomial optimization (90C23) Interior-point methods (90C51)

Abstract: In polynomial optimization problems, nonnegativity constraints are typically handled using the sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz [18], using the sum of squares cone directly in a nonsymmetric interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and $el{l}_1$-norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized polynomial cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with smaller parameters. In most cases, these algorithmic advantages also translate to faster solving times in practice.

Recommendations

• Semidefinite characterization of sum-of-squares cones in algebras
• Sum-of-squares optimization without semidefinite programming
• Exact conic programming relaxations for a class of convex polynomial cone programs
• A Sum of Squares Approximation of Nonnegative Polynomials
• SONC optimization and exact nonnegativity certificates via second-order cone programming

Cites work

• A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
• An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
• Convergent Relaxations of Polynomial Matrix Inequalities and Static Output Feedback
• Generalized Chebyshev Polynomials Associated with Affine Weyl Groups
• scientific article; zbMATH DE number 3678009 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1489808 (Why is no real title available?)
• Optimization Problems over Positive Pseudopolynomial Matrices
• Second-order cone programming
• Self-concordant barriers for cones generated by Chebyshev systems
• Semidefinite characterization of sum-of-squares cones in algebras
• Semidefinite Optimization and Convex Algebraic Geometry
• Solving Natural Conic Formulations with Hypatia.jl
• Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming
• Sum-of-squares optimization without semidefinite programming

Cited in

(5)

• Semidefinite characterization of sum-of-squares cones in algebras
• On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities
• Sum-of-squares optimization without semidefinite programming
• Performance enhancements for a generic conic interior point algorithm
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima

This page was built for publication: Sum of squares generalizations for conic sets

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