¿Más general que el programa semidefinido?

Question

Estaba dando mi clase de optimización convexa y explicando que los programas lineales son un caso especial de los programas cónicos de segundo orden, que a su vez son casos especiales de los programas semidefinidos. Mi pregunta es, ¿hay alguna clase bien establecida de problemas de optimización que sea más general que los programas semidefinidos? Optimización cónica problemas sería un ejemplo de esto, pero espero algo un poco más algebraico, si es que existe.

Answer 1

Existe el concepto de programación hiperbólica introducido en los años 90 por Osman Güler:

• O. Güler, Polinomios hiperbólicos y métodos de punto interior para la programación convexa , Math. Oper. Res. 22 (1997) 350-377.

Ver también

• H.H. Bauschke, O. Güler, A.S. Lewis, H.S. Sendov, Polinomios hiperbólicos y análisis convexo , Canad. J. Math. 53 (2001) 470-488;
• J. Renegar, Programas hiperbólicos y sus relajaciones derivadas , Found. Comput. Math. 6 (2005) 59-79.

Se basa en el concepto de cono de hiperbolicidad introducido por Lars Gårding en los años 50 en el contexto de la teoría de las ecuaciones diferenciales parciales hiperbólicas.

Decimos que un polinomio homogéneo $P:\mathbb{R}^n\rightarrow\mathbb{R}$ es hiperbólica con respecto a $\tau\in\mathbb{R}^n$ si $P(\tau)\neq 0$ y las raíces del polinomio de una variable $P_{\xi,\tau}(\lambda)\doteq P(\xi-\lambda\tau)$ son todos real para todos $\xi\in\mathbb{R}^n$ . A continuación, definimos el cono de hiperbolicidad $C(P,\tau)$ de $P$ con respecto a $\tau$ como $$ C(P,\tau)=\{\xi\in\mathbb{R}^n\ |\ \text{the roots of }P_{\xi,\tau}\text{ are all positive}\}\ . $$ Gårding demostró que $C(P,\tau)$ es un cono abierto y convexo que es el componente conectado de $\{\xi\ |\ P(\xi)\neq 0\}$ al que $\tau$ pertenece. Además, el cierre de $C(P,\tau)$ tiene la forma $$ \overline{C(P,\tau)}=\{\xi\in\mathbb{R}^n\ |\ \text{the roots of }P_{\xi,\tau}\text{ are all nonnegative}\}\ . $$ La programación hiperbólica es entonces simplemente una programación cónica cuando el cono de viabilidad es (el cierre de) un cono de hiperbolicidad de algún polinomio hiperbólico $P$ . Comprobar si $\xi\in\mathbb{R}^n$ pertenece a $C(P,\tau)$ (resp. $\overline{C(P,\tau)}$ ) equivale a comprobar si los coeficientes del polinomio mónico de una variable $P(\tau)^{-1}P_{\xi,\tau}=P_{\tau,\tau}(0)^{-1}P_{\xi,\tau}$ son todas positivas (o no negativas).

La programación hiperbólica generaliza la programación semidefinida en el siguiente sentido: si $\gamma_1,\ldots,\gamma_n$ son $N\times N$ matrices simétricas y establecemos $\gamma(\xi)=\sum^n_{j=1}\xi_j\gamma_j$ , $\xi\in\mathbb{R}^n$ entonces $P(\xi)=\det\gamma(\xi)$ es un polinomio hiperbólico con respecto a cualquier $\tau\in\mathbb{R}^n$ tal que $\gamma(\tau)$ es positiva definida. En ese caso, $$ C(P,\tau)=\{\xi\in\mathbb{R}^n\ |\ \gamma(\xi)\text{ is positive definite}\} $$ y $$ \overline{C(P,\tau)}=\{\xi\in\mathbb{R}^n\ |\ \gamma(\xi)\text{ is positive semidefinite}\}\ . $$ No se sabe si se trata de una estricto Sin embargo, se conjetura que cualquier cono de hiperbolicidad puede ser representado como un cono de matrices definidas positivas para una elección adecuada de $N$ . Ya que esto fue originalmente conjeturado (en una forma más fuerte) por Peter Lax en los años 50 para $n=3$ Esta conjetura (aún abierta) se conoce como la conjetura de Lax generalizada . La afirmación original de Lax fue probada por A.S. Lewis, P.A. Parrilo y M.V. Ramana ( La conjetura de Lax es cierta Proc. Amer. Math. Soc. 133 (2005) 2495-2499) basándose en los trabajos de J.W. Helton y V. Vinnikov ( Representación de la desigualdad de la matriz lineal de los conjuntos Commun. Pure Appl. Math. 60 (2007) 654-674).

Answer 2

Si quieres, puedes mirar los conos de sumas de cuadrados de polinomios (los conos de matrices PSD son lo mismo que los conos de sumas de cuadrados de polinomios lineales). Este es el punto de partida de la técnica moderna de resolución de problemas de optimización en conjuntos semialgebraicos, debida a J.Lasserre y otros.

En términos más generales, se pueden considerar conos de polinomios no negativos, y esto abre todo el asunto del problema 17 de Hilbert.