MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was TAing 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. My question is, 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.

share|cite|improve this question

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).

share|cite|improve this answer

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.

share|cite|improve this answer
1  
But you can rewrite these sum of squares cones as projections of appropriate linear sections of larger positive semidefinite cones, so from a strict representability perspective you don't get anything new here. – Noah Stein Feb 22 at 22:55
    
this is only true asymptotically --- and then, you know, every nice function on a compact is asymptotically a polynomial, so why bother :-) – Dima Pasechnik Feb 23 at 10:20
    
OK, it's not quite true what I just wrote. I meant cones of nonnegative polynomials. – Dima Pasechnik Feb 23 at 10:21
    
Ok, well cones of nonnegative polynomials are more general than SDP cones, but unfortunately computationally intractable. – Noah Stein Feb 23 at 19:31
1  
speaking about complexity, for SDPs in general is it not known, and so one has to tread carefully here. – Dima Pasechnik Feb 25 at 7:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.