Limitations on the expressive power of convex cones without long chains of faces

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

A convex optimization problem in conic form involves minimizing a linear functional over the intersection of a convex cone and an affine subspace. In some cases, it is possible to replace a conic formulation using a certain cone, with a “lifted” conic formulation using another cone that is higher-dimensional, but simpler, in some sense. One situation in which this can be computationally advantageous is when the higher-dimensional cone is a Cartesian product of many “low-complexity” cones, such as second-order cones, or small positive semidefinite cones. This paper studies obstructions to a convex cone having a lifted representation with such a product structure. The main result says that whenever a convex cone has a certain neighborliness property, then it does not have a lifted representation using a finite product of cones, each of which has only short chains of faces. This is a generalization of recent work of Averkov [SIAM J. Appl. Alg. Geom., 3 (2019), pp. 128–151], which considers only lifted representations using products of positive semidefinite cones of bounded size. Among the consequences of the main result is that various cones related to nonnegative polynomials do not have lifted representations using products of “low-complexity” cones, such as smooth cones, the exponential cone, and cones defined by hyperbolic polynomials of low degree.

Original languageEnglish
Pages (from-to)1033-1047
Number of pages15
JournalSIAM Journal on Optimization
Volume30
Issue number1
DOIs
Publication statusPublished - 2020

Keywords

  • Cone factorization
  • Conic optimization
  • Hyperbolicity cone
  • Lifts

Cite this