Is there a class of optimization problems more general than semidefinite programming?

Question

I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there any well-established class of optimization problems that is more general than semidefinite programs? Conic optimization problems would be an example of this, but I'm hoping for something a little more algebraic, if it exists.

Answer 1

There is the concept of hyperbolic programming, introduced in the 90's by Osman Güler:

• O. Güler, Hyperbolic Polynomials and Interior Point Methods for Convex Programming, Math. Oper. Res. 22 (1997) 350-377.

See also

• H.H. Bauschke, O. Güler, A.S. Lewis, H.S. Sendov, Hyperbolic Polynomials and Convex Analysis, Canad. J. Math. 53 (2001) 470-488;
• J. Renegar, Hyperbolic Programs, and their Derivative Relaxations, Found. Comput. Math. 6 (2005) 59–79.

It is based on the concept of hyperbolicity cone introduced by Lars Gårding in the 50's in the context of the theory of hyperbolic partial differential equations.

We say that an homogeneous polynomial $P:\mathbb{R}^n\rightarrow\mathbb{R}$ is hyperbolic with respect to $\tau\in\mathbb{R}^n$ if $P(\tau)\neq 0$ and the roots of the one-variable polynomial $P_{\xi,\tau}(\lambda)\doteq P(\xi-\lambda\tau)$ are all real for all $\xi\in\mathbb{R}^n$. We then define the hyperbolicity cone $C(P,\tau)$ of $P$ with respect to $\tau$ as $$ C(P,\tau)=\{\xi\in\mathbb{R}^n\ |\ \text{the roots of }P_{\xi,\tau}\text{ are all positive}\}\ . $$ It was shown by Gårding that $C(P,\tau)$ is an open, convex cone which is the connected component of $\{\xi\ |\ P(\xi)\neq 0\}$ to which $\tau$ belongs. Moreover, the closure of $C(P,\tau)$ has the form $$ \overline{C(P,\tau)}=\{\xi\in\mathbb{R}^n\ |\ \text{the roots of }P_{\xi,\tau}\text{ are all nonnegative}\}\ . $$ Hyperbolic programming is then simply conic programming when the feasibility cone is (the closure of) an hyperbolicity cone of some hyperbolic polynomial $P$. Checking if $\xi\in\mathbb{R}^n$ belongs to $C(P,\tau)$ (resp. $\overline{C(P,\tau)}$) amounts to checking if the coefficients of the monic one-variable polynomial $P(\tau)^{-1}P_{\xi,\tau}=P_{\tau,\tau}(0)^{-1}P_{\xi,\tau}$ are all positive (resp. nonnegative).

Hyperbolic programming generalizes semidefinite programming in the following sense: if $\gamma_1,\ldots,\gamma_n$ are $N\times N$ symmetric matrices and we set $\gamma(\xi)=\sum^n_{j=1}\xi_j\gamma_j$, $\xi\in\mathbb{R}^n$, then $P(\xi)=\det\gamma(\xi)$ is an hyperbolic polynomial with respect to any $\tau\in\mathbb{R}^n$ such that $\gamma(\tau)$ is positive definite. In that case, $$ C(P,\tau)=\{\xi\in\mathbb{R}^n\ |\ \gamma(\xi)\text{ is positive definite}\} $$ and $$ \overline{C(P,\tau)}=\{\xi\in\mathbb{R}^n\ |\ \gamma(\xi)\text{ is positive semidefinite}\}\ . $$ It is not known whether this is a strict generalization of semidefinite programming, though - it is in fact conjectured that any hyperbolicity cone can be represented as a cone of positive definite matrices for a suitable choice of $N$. Since this was originally conjectured (in a stronger form) by Peter Lax in the 50's for $n=3$, this (still open) conjecture became known as the generalized Lax conjecture. Lax's original claim was proven by A.S. Lewis, P.A. Parrilo and M.V. Ramana (The Lax Conjecture is True, Proc. Amer. Math. Soc. 133 (2005) 2495-2499) building on work by J.W. Helton and V. Vinnikov (Linear Matrix Inequality Representation of Sets, Commun. Pure Appl. Math. 60 (2007) 654-674).

Answer 2

If you like, you might look at cones of sums of squares of polynomials (cones of PSD matrices are the same thing as cones of sums of squares of linear polynomials). This is the starting point of the modern technique of solving optimisation problems on semi-algebraic sets, due to J.Lasserre and others.

More generally, you might look at cones of nonnegative polynomials, and this opens up the whole Hilbert 17th problem business.