Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones

DOI10.1007/S10107-014-0804-YzbMATH Open1327.90180arXiv1208.1443OpenAlexW3100992911MaRDI QIDQ747766FDOQ747766

Authors: James Saunderson, Pablo A. Parrilo 

Publication date: 19 October 2015

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

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.

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

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

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)

Cites Work

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

Cited In (16)

• Symbolic computation in hyperbolic programming
• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Semidefinite descriptions of cones defining spectral mask constraints
• Semidefinite representation of the \(k\)-ellipse
• Semidefinite representations for finite varieties
• Spectral linear matrix inequalities
• Automorphisms of Rank-One Generated Hyperbolicity Cones and Their Derivative Relaxations
• Hyperbolic polynomials, interlacers, and sums of squares
• Spectrahedral Shadows
• Certifying Polynomial Nonnegativity via Hyperbolic Optimization
• Definite determinantal representations of multivariate polynomials
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• On hyperbolicity cones associated with elementary symmetric polynomials
• Some geometric results in semidefinite programming
• On eigenvalues of symmetric matrices with PSD principal submatrices
• Approximate cone factorizations and lifts of polytopes

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)