Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones

DOI10.1007/S10107-014-0804-YMaRDI QIDQ747766zbMATH OpenOpenAlexFDO

Authors James Saunderson, Pablo A. Parrilo

Publication date 19 October 2015

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

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

zbMATH Keywords

hyperbolicity conehyperbolic polynomialelementary symmetric polynomialsemidefinite representation

Mathematics Subject Classification ID

Convex programming (90C25) Semidefinite programming (90C22) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Convex functions and convex programs in convex geometry (52A41)

Abstract: We give explicit polynomial-sized (in $n$ and $k$) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree $k$ in $n$ variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in $k,m$, and $n$) of the hyperbolicity cones associated with $k$th directional derivatives of polynomials of the form $p(x)=det(su{m}_{i=1}^n{A}_i{x}_i)$ where the $A_i$ are $mimesm$ symmetric matrices. These convex cones form an analogous family of outer approximations to any spectrahedral cone. Our representations allow us to use semidefinite programming to solve the linear cone programs associated with these convex cones as well as their (less well understood) dual cones.

Recommendations

• Exponential lower bounds on spectrahedral representations of hyperbolicity cones
• On the derivative cones of polyhedral cones
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Semidefinite representation of convex sets
• Semidefinite representations for finite varieties

Cites work

• scientific article; zbMATH DE number 3146819 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• Advances in convex optimization: conic programming
• Group majorization, the convex hulls of sets of matrices, and the diagonal element - singular value inequalities
• Homogeneous multivariate polynomials with the half-plane property
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Hyperbolic programs, and their derivative relaxations
• Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Lifts of Convex Sets and Cone Factorizations
• Linear matrix inequality representation of sets
• ORBITOPES
• On hyperbolicity cones associated with elementary symmetric polynomials
• On the derivative cones of polyhedral cones
• Positive polynomials and projections of spectrahedra
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite representation of the \(k\)-ellipse
• Some geometric results in semidefinite programming
• Symmetry matters for the sizes of extended formulations
• The Lax conjecture is true

Cited in

(23)

• Approximate cone factorizations and lifts of polytopes
• Spectral linear matrix inequalities
• Definite determinantal representations of multivariate polynomials
• Automorphisms of Rank-One Generated Hyperbolicity Cones and Their Derivative Relaxations
• Symbolic computation in hyperbolic programming
• Semidefinite descriptions of cones defining spectral mask constraints
• On hyperbolicity cones associated with elementary symmetric polynomials
• Some geometric results in semidefinite programming
• Semidefinite representations for finite varieties
• On polyhedral approximations of the positive semidefinite cone
• Hyperbolic polynomials, interlacers, and sums of squares
• On the derivative cones of polyhedral cones
• Certifying Polynomial Nonnegativity via Hyperbolic Optimization
• Exponential lower bounds on spectrahedral representations of hyperbolicity cones
• Semidefinite representation of the \(k\)-ellipse
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• On eigenvalues of symmetric matrices with PSD principal submatrices
• Spectrahedral shadows
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Semidefinite characterization of sum-of-squares cones in algebras
• Exact conic programming relaxations for a class of convex polynomial cone programs
• On representing the positive semidefinite cone using the second-order cone
• Polyhedral approximations of the semidefinite cone and their application

Describes a project that uses

Uses Software

• SDPT3
• YALMIP

This page was built for publication: Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones

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