Skip to main content
2 of 11
Added explanation, slight rewording

There is the concept of hyperbolic programming, introduced in the 90's by Osman Güler (Hyperbolic 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), based on the concept of hyperbolicity cone introduced by Lars Garding in the 50's in the context of the theory of hyperbolic partial differential equations.

We say that a 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 Garding that $C(P,\tau)$ is an open, convex cone which is the connected component of $\{\xi\ |\ P(\xi)\neq 0\}$ to which $\tau$ belongs. Hyperbolic programming is then simply conic programming when the feasibility cone is an hyperbolicity cone of some hyperbolic polynomial.

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. 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. Since this was originally conjectured (in a stronger form) by Peter Lax in the 50's for $3\times 3$ matrices, 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 (Commun. Pure Appl. Math. 60 (2007) 654-674).