Return to Answer

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_{\xi,\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).

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

There is the concept of hyperbolic programming, introduced in the 90's by Osman 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), 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_{\xi,\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).

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_{\xi,\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).

There is the concept of hyperbolic programming, introduced in the 90's by Osman 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), 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_{\xi,\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).

There is the concept of hyperbolic programming, introduced in the 90's by Osman 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), 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_{\xi,\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).