Programación semidefinida

Un problema de programación lineal es aquel en el que deseamos maximizar o minimizar una función objetivo lineal de variables reales sobre un politopo . En la programación semidefinida, en cambio, utilizamos vectores de valores reales y podemos tomar el producto escalar de vectores; las restricciones de no negatividad sobre las variables reales en LP ( programación lineal ) se reemplazan por restricciones de semidefinición sobre las variables matriciales en SDP ( programación semidefinida ). Específicamente, un problema general de programación semidefinida puede definirse como cualquier problema de programación matemática de la forma

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{sujeto a}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ para todo }}k\\\end{array}}}$

donde el${\displaystyle c_{i,j},a_{i,j,k}}$y el${\displaystyle b_{k}}$son números reales y${\displaystyle x^{i}\cdot x^{j}}$es el producto escalar de${\displaystyle x^{i}}$y ${\displaystyle x^{j}}$.

Un${\displaystyle n\times n}$matriz${\displaystyle M}$Se dice que es semidefinida positiva si es la matriz de Gram de algunos vectores (es decir, si existen vectores${\displaystyle x^{1},\ldots ,x^{n}}$de tal manera que${\displaystyle m_{i,j}=x^{i}\cdot x^{j}}$a pesar de${\displaystyle i,j}$). Si este es el caso, lo denotamos como${\displaystyle M\succeq 0}$. Tenga en cuenta que existen otras definiciones equivalentes de ser semidefinida positiva; por ejemplo, las matrices semidefinidas positivas son matrices autoadjuntas que tienen únicamente valores propios no negativos .

Denotemos por${\displaystyle \mathbb {S} ^{n}}$el espacio de todos${\displaystyle n\times n}$matrices simétricas reales. El espacio está equipado con el producto interno (donde${\displaystyle {\rm {trace}}}$denota la traza ):

${\displaystyle \langle A,B\rangle$ :={\rm {traza}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}

Podemos reescribir el programa matemático dado en la sección anterior de forma equivalente como

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{sujeto a}}&\langle A_{k},X\rangle \leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

donde entrada${\displaystyle i,j}$en${\displaystyle C}$es dado por${\displaystyle {\frac {c_{i,j}+c_{j,i}}{2}}}$de la sección anterior y${\displaystyle A_{k}}$es simétrico${\displaystyle n\times n}$matriz que tiene${\displaystyle i,j}$ª entrada${\displaystyle {\frac {a_{i,j,k}+a_{j,i,k}}{2}}}$de la sección anterior. Por lo tanto, las matrices ${\displaystyle C}$y${\displaystyle A_{k}}$son simétricas y los productos internos anteriores están bien definidos.

Tenga en cuenta que si agregamos variables de holgura de manera apropiada, este SDP se puede convertir a una forma ecuacional :

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{sujeto a}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

Para mayor comodidad, un SDP puede especificarse de una forma ligeramente diferente, pero equivalente. Por ejemplo, se pueden agregar expresiones lineales que involucren variables escalares no negativas a la especificación del programa. Esto sigue siendo un SDP porque cada variable puede incorporarse a la matriz.${\displaystyle X}$como entrada diagonal (${\displaystyle X_{ii}}$para algunos${\displaystyle i}$). Para asegurar que${\displaystyle X_{ii}\geq 0}$, restricciones${\displaystyle X_{ij}=0}$se puede agregar para todos${\displaystyle j\neq i}$. Como otro ejemplo, observe que para cualquier matriz semidefinida positiva${\displaystyle X}$, existe un conjunto de vectores${\displaystyle \{v_{i}\}}$de tal manera que el${\displaystyle i}$,${\displaystyle j}$entrada de${\displaystyle X}$es${\displaystyle X_{ij}=(v_{i},v_{j})}$el producto escalar de${\displaystyle v_{i}}$y${\displaystyle v_{j}}$Por lo tanto, los SDP se formulan a menudo en términos de expresiones lineales sobre productos escalares de vectores. Dada la solución al SDP en la forma estándar, los vectores${\displaystyle \{v_{i}\}}$se puede recuperar en${\displaystyle O(n^{3})}$tiempo (por ejemplo, utilizando una descomposición de Cholesky incompleta de X).

De forma análoga a la programación lineal, dado un SDP general de la forma

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{sujeto a}}&\langle A_{i},X\rangle =b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}}$

(el problema primal o P-SDP), definimos el programa semidefinido dual (D-SDP) como

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&b^{T}y\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}}$

donde para cualesquiera dos matrices${\displaystyle P}$y${\displaystyle Q}$,${\displaystyle P\succeq Q}$medio${\displaystyle P-Q\succeq 0}$.

El teorema de dualidad débil establece que el valor del SDP primal es al menos igual al valor del SDP dual. Por lo tanto, cualquier solución factible del SDP dual limita inferiormente el valor del SDP primal, y viceversa, cualquier solución factible del SDP primal limita superiormente el valor del SDP dual. Esto se debe a que

${\displaystyle \langle C,X\rangle -b^{T}y=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,}$

donde la última desigualdad se debe a que ambas matrices son semidefinidas positivas, y el resultado de esta función a veces se denomina brecha de dualidad.

Cuando el valor de los SDP primal y dual es igual, se dice que el SDP satisface la propiedad de dualidad fuerte . A diferencia de los programas lineales , donde todo programa lineal dual tiene un objetivo óptimo igual al objetivo primal, no todo SDP satisface la dualidad fuerte; en general, el valor del SDP dual puede estar estrictamente por debajo del valor del primal, y el P-SDP y el D-SDP satisfacen las siguientes propiedades:

(i) Supongamos que el problema primal (P-SDP) está acotado inferiormente y es estrictamente factible (es decir, existe ${\displaystyle X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0}$de tal manera que${\displaystyle \langle A_{i},X_{0}\rangle =b_{i}}$,${\displaystyle i=1,\ldots ,m}$). Entonces existe una solución óptima${\displaystyle y^{*}}$al (D-SDP) y

${\displaystyle \langle C,X^{*}\rangle =b^{T}y^{*}.}$

(ii) Supongamos que el problema dual (D-SDP) está acotado superiormente y es estrictamente factible (es decir, ${\displaystyle \sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C}$para algunos${\displaystyle y_{0}\in \mathbb {R} ^{m}}$). Entonces existe una solución óptima${\displaystyle X^{*}}$a (P-SDP) y se cumple la igualdad de (i).

Una condición suficiente para que se cumpla la dualidad fuerte en un problema SDP (y, en general, en cualquier problema de optimización convexa) es la condición de Slater . También es posible alcanzar la dualidad fuerte para los SDP sin condiciones de regularidad adicionales mediante un problema dual extendido propuesto por Ramana. ^{[ 2 ] [ 3 ]}

Consideremos tres variables aleatorias.${\displaystyle A}$,${\displaystyle B}$, y${\displaystyle C}$. Un conjunto dado de coeficientes de correlación${\displaystyle \rho _{AB},\ \rho _{AC},\rho _{BC}}$son posibles si y solo si

${\displaystyle {\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0.}$

Esta matriz se llama matriz de correlación . Supongamos que sabemos, a partir de algún conocimiento previo (resultados empíricos de un experimento, por ejemplo), que${\displaystyle -0.2\leq \rho _{AB}\leq -0.1}$y${\displaystyle 0.4\leq \rho _{BC}\leq 0.5}$. El problema de determinar los valores más pequeños y más grandes que${\displaystyle \rho _{AC}\ }$se puede tomar está dado por:

${\displaystyle {\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end{array}}}$

Nosotros establecimos${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}}$para obtener la respuesta. Esto se puede formular mediante un SDP. Manejamos las restricciones de desigualdad aumentando la matriz de variables e introduciendo variables de holgura , por ejemplo

${\displaystyle \mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right)\cdot \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1}&0&0\\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0.1}$

Resolver este SDP proporciona los valores mínimo y máximo de${\displaystyle \rho _{AC}=x_{13}\ }$como${\displaystyle -0.978}$y${\displaystyle 0.872}$respectivamente.

Consideremos el problema

minimizar${\displaystyle {\frac {(c^{T}x)^{2}}{d^{T}x}}}$

sujeto a${\displaystyle Ax+b\geq 0}$

donde asumimos que${\displaystyle d^{T}x>0}$cuando sea${\displaystyle Ax+b\geq 0}$.

Introducción de una variable auxiliar${\displaystyle t}$El problema puede reformularse:

minimizar${\displaystyle t}$

sujeto a${\displaystyle Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t}$

En esta formulación, el objetivo es una función lineal de las variables.${\displaystyle x,t}$.

La primera restricción se puede escribir como

${\displaystyle {\textbf {diag}}(Ax+b)\geq 0}$

donde la matriz${\displaystyle {\textbf {diag}}(Ax+b)}$es la matriz cuadrada con valores en la diagonal iguales a los elementos del vector${\displaystyle Ax+b}$.

La segunda restricción se puede escribir como

${\displaystyle td^{T}x-(c^{T}x)^{2}\geq 0}$

Definición${\displaystyle D}$como sigue

${\displaystyle D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]}$

Podemos utilizar la teoría de los complementos de Schur para ver que

${\displaystyle D\succeq 0}$

(Boyd y Vandenberghe, 1996)

El programa semidefinido asociado a este problema es

minimizar${\displaystyle t}$

sujeto a${\displaystyle \left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\end{array}}\right]\succeq 0}$

Los programas semidefinidos son herramientas importantes para desarrollar algoritmos de aproximación para problemas de maximización NP-difíciles. El primer algoritmo de aproximación basado en un SDP se debe a Michel Goemans y David P. Williamson (JACM, 1995). ^{[ 1 ] : Cap.1} Estudiaron el problema del corte máximo : dado un grafo G = ( V , E ), generar una partición de los vértices V de manera que se maximice el número de aristas que cruzan de un lado al otro. Este problema se puede expresar como un programa cuadrático entero :

Maximizar${\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},}$de tal manera que cada${\displaystyle v_{i}\in \{1,-1\}}$.

A menos que P = NP , no podemos resolver este problema de maximización de manera eficiente. Sin embargo, Goemans y Williamson observaron un procedimiento general de tres pasos para abordar este tipo de problema:

1. Relaja el programa cuadrático entero convirtiéndolo en un programa de dinámica estocástica (SDP). (Esto también se puede derivar utilizando el primer nivel de la jerarquía de suma de cuadrados ).
2. Resuelva el SDP (con un error aditivo arbitrariamente pequeño)${\displaystyle \epsilon }$).
3. Redondea la solución SDP para obtener una solución aproximada al programa cuadrático entero original.

Para un corte máximo, la relajación más natural es

${\displaystyle \max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}},}$de tal manera que${\displaystyle \lVert v_{i}\rVert ^{2}=1}$donde la maximización se realiza sobre vectores${\displaystyle \{v_{i}\}}$en lugar de escalares enteros.

Este es un SDP porque la función objetivo y las restricciones son todas funciones lineales de productos internos de vectores. Resolver el SDP da como resultado un conjunto de vectores unitarios en${\displaystyle \mathbf {R^{n}} }$Dado que no se requiere que los vectores sean colineales, el valor de este programa relajado solo puede ser mayor que el valor del programa entero cuadrático original. Finalmente, se necesita un procedimiento de redondeo para obtener una partición. Goemans y Williamson simplemente eligen un hiperplano aleatorio uniforme que pasa por el origen y dividen los vértices según en qué lado del hiperplano se encuentran los vectores correspondientes. Un análisis directo muestra que este procedimiento logra una razón de aproximación esperada (garantía de rendimiento) de 0,87856 - ε. (El valor esperado del corte es la suma sobre los bordes de la probabilidad de que el borde se corte, que es proporcional al ángulo${\displaystyle \cos ^{-1}\langle v_{i},v_{j}\rangle }$entre los vectores en los extremos de la arista sobre${\displaystyle \pi }$. Comparando esta probabilidad con${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}}$, en promedio la razón siempre es al menos 0,87856.) Suponiendo la conjetura de juegos únicos , se puede demostrar que esta razón de aproximación es esencialmente óptima.

Desde el artículo original de Goemans y Williamson, los SDP se han aplicado para desarrollar numerosos algoritmos de aproximación. Posteriormente, Prasad Raghavendra desarrolló un marco general para problemas de satisfacción de restricciones basado en la conjetura de juegos únicos . ^{[ 4 ]}

La programación semidefinida se ha aplicado para encontrar soluciones aproximadas a problemas de optimización combinatoria, como la solución del problema de corte máximo con una razón de aproximación de 0,87856. Los SDP también se utilizan en geometría para determinar grafos de tensegridad y surgen en la teoría de control como LMI , y en problemas de coeficientes elípticos inversos como restricciones de semidefinición convexas, no lineales y de definición parcial. ^{[ 5 ]} También se utiliza ampliamente en física para restringir teorías de campos conformes con el bootstrap conforme . ^{[ 6 ]}

El método del elipsoide es un método general para la programación convexa y puede utilizarse en particular para resolver SDP. En el contexto de los SDP, el método del elipsoide proporciona la siguiente garantía. ^{[ 1 ] : Teorema 2.6.1} Considere un SDP en la siguiente forma ecuacional:

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

Sea L el subespacio afín de matrices en S ⁿ que satisfacen las m restricciones de igualdad; entonces el SDP se puede escribir como:${\displaystyle \max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0}$Supongamos que todos los coeficientes del SDP son números racionales. Sea R una cota superior explícitamente dada para la norma de Frobenius máxima de una solución factible, y ε > 0 una constante. Una matriz X en S ⁿ se denomina ε-profunda si toda matriz Y en L con una distancia de Frobenius como máximo ε de X satisface la condición de factibilidad.${\displaystyle Y\succeq 0}$. Denotar${\displaystyle v_{deep}:=\sup\{\langle C,X\rangle :X{\text{ is }}\epsilon {\text{-deep}}\}}$El elipsoide devuelve una de las siguientes salidas:

• Una matriz X* en L (es decir, que satisface exactamente todas las restricciones de igualdad lineales), tal que la distancia de Frobenius entre X* y alguna solución factible es como máximo ε (es decir, que satisface aproximadamente la restricción de desigualdad).${\displaystyle X\succeq 0}$), y${\displaystyle \langle C,X^{*}\rangle \geq v_{deep}-\epsilon }$(es decir, valor objetivo aproximadamente óptimo).
• Un certificado que acredite que el problema no tiene soluciones ε-profundas (es decir, que el problema es aproximadamente inviable).

El tiempo de ejecución es polinomial en las codificaciones binarias de las entradas y en log(R/ ε ), en el modelo de máquina de Turing .

Nótese que, en general, R puede ser doblemente exponencial en n. En ese caso, la garantía de tiempo de ejecución del método del elipsoide es exponencial en n . Pero en la mayoría de las aplicaciones, R no es tan grande. En estos casos, el método del elipsoide es el único método conocido que garantiza un tiempo de ejecución polinomial en el modelo de máquina de Turing. ^{[ 1 ] : 23} Pero en la práctica, su rendimiento no es tan bueno.

La mayoría de los códigos se basan en métodos de punto interior (CSDP, MOSEK , SeDuMi, SDPT3 , DSDP, SDPA). Estos son robustos y eficientes para problemas SDP lineales generales, pero están limitados por el hecho de que los algoritmos son de segundo orden y necesitan almacenar y factorizar una matriz grande (y a menudo densa). Teóricamente, los algoritmos SDP de alta precisión más avanzados ^{[ 7 ] [ 8 ]} se basan en este enfoque.

Los métodos de primer orden para la optimización cónica evitan calcular, almacenar y factorizar una matriz hessiana grande y escalan a problemas mucho mayores que los métodos de punto interior, a costa de cierta pérdida de precisión. Un método de primer orden se implementa en el Splitting Cone Solver (SCS). ^{[ 9 ]} Otro método de primer orden es el método de direcciones alternas de multiplicadores (ADMM). ^{[ 10 ]} Este método requiere en cada paso la proyección sobre el cono de matrices semidefinidas.

El código ConicBundle formula el problema SDP como un problema de optimización no diferenciable y lo resuelve mediante el método de haces espectrales para la optimización no diferenciable. Este enfoque es muy eficiente para una clase especial de problemas SDP lineales.

Los algoritmos basados ​​en el método del lagrangiano aumentado (PENSDP) tienen un comportamiento similar al de los métodos de punto interior y pueden especializarse para algunos problemas de gran escala. Otros algoritmos utilizan información de bajo rango y reformulan el SDP como un problema de programación no lineal (SDPLR, ManiSDP). ^{[ 11 ]}

También se han propuesto algoritmos que resuelven SDP de forma aproximada. El objetivo principal de estos métodos es lograr una menor complejidad en aplicaciones donde las soluciones aproximadas son suficientes y la complejidad debe ser mínima. Un método destacado que se ha utilizado para la detección de datos en sistemas inalámbricos de entrada múltiple y salida múltiple (MIMO) es la relajación semidefinida aproximada triangular (TASER), ^{[ 12 ]} que opera sobre los factores de descomposición de Cholesky de la matriz semidefinida en lugar de la matriz semidefinida. Este método calcula soluciones aproximadas para un problema similar al corte máximo que a menudo son comparables a las soluciones de los solucionadores exactos pero en solo 10-20 iteraciones del algoritmo. Hazan ^{[ 13 ]} ha desarrollado un algoritmo aproximado para resolver SDP con la restricción adicional de que la traza de la matriz de variables debe ser 1.