Cone programming

Cone programs are optimization problems that minimize a linear functional over the intersection of an affine subspace and a convex cone :

\[ \begin{aligned} \text{minimize} \quad & \langle c, x \rangle \\ \text{subject to} \quad & Ax=b \\ & x \in \mathcal{K} \end{aligned} \]

Any convex constraint can be represented as a conic constraint, so not every cone program is efficiently solvable. Even so, many commonly occurring cones give rise to tractable optimization problems, making cone programming a useful unifying framework.

Table 1: Important convex cones in optimization
Convex cone Cone program
\(\mathbb{R}^n_+\), the nonnegative orthant Linear program (LP)
\(\mathcal{Q}^n\), the quadratic (ice cream) cone Second-order cone program (SOCP)
\(\mathcal{S}^n_+\), the cone of PSD matrices Semidefinite program (SDP)
Exponential cone Geometric program
Cone of copositive matrices Copositive program

General cone programs

  • Ben-Tal & Nemirovski, 2001: Lectures on modern convex optimization (doi)
  • Renegar, 2001: A mathmatical view of interior point methods, Ch. 3: Conic programming and duality (doi)
  • Boyd & Vandenberghe, 2004: Convex optimization (pdf), Sec. 4.6: Generalized inequality constraints
  • Vandenberghe, 2016, lecture notes: Conic optimization (pdf)

Geometric programs

Cone programs based on the exponential cone and its reparametrization, the relative entropy cone.

  • Chandrasekaran & Shah, 2014: Conic geometric programming (doi, arxiv)
    • Not having read the paper, I don’t see how this is any more general than cone programming over a product cone of the exponential cone and another convex cone
  • Chandrasekaran & Shah, 2016, expository paper: Relative entropy optimization and its applications (doi)

Copositive programs

Unlike most other standard cone programs, copositive programming is NP-hard.

  • Gärtner & Matoušek, 2012: Approximation algorithms and semidefinite programming, Ch. 7: Copositive programming (doi)
  • Burer, 2012, book chapter: Copositive programming (doi, pdf)

Hyperbolic programs

Hyperbolic programming includes semidefinite (and thus also linear and second-order cone) programming) as a special case.

  • Renegar, 2006: Hyperbolic programs, and their derivative relaxations (doi)
  • Renegar, 2019: Accelerated first-order methods for hyperbolic programming (doi, arxiv)

For more recent work, see the 2019 Simons Workshop on Hyperbolic Polynomials and Hyperbolic Programming.