Programación Semidefinida

Programación Semidefinida (SDP) es una subrama de la optimización convexa cuyo interés principal yace en la optimización de una función objetiva lineal (una función especificada por el usuario, que dicho usuario busca minimizar o maximizar) sobre la intersección del cono de matrices positivo semidefinidas con un espacio afín, i.e., un espectrahedro.

La programación semidefinida es una rama relativamente nueva de optimización que está recibiendo creciente atención por varias razones. Muchos problemas prácticos en investigación de operaciones y optimización combinatoria pueden ser modelados o aproximados por programas semidefinidos. En teoría de control automático, los PSDs son utilizados en el contexto de desigualdades matriciales lineales. Los PSDs son de hecho un caso especial de programación cónica y pueden ser resueltos eficientemente por métodos de punto interior. Todos los programas lineales y los programas cuadráticos (convexos) pueden ser expresados como PSDs, y vía jerarquías de PSDs, las soluciones de problemas de optimización polinomial pueden ser aproximadas. La programación semidefinida ha sido utilizada en la optimización de sistemas complejos. En años recientes, algunos problemas de complejidad de consulta cuánticos han sido formulados en términos de programas semidefinidos.

Motivación y definición

Motivación inicial

Un problema de programación lineal es uno en el cual deseamos maximizar o minimizar una función objetiva lineal con variables reales sobre un politopo. En cambio, en programación semidefinida utilizamos vectores con entradas reales y podemos tomar el producto punto de vectores; las restricciones de no-negatividad en variables reales en LP (programación lineal) son reemplazadas por restricciones de semidefinición en las variables matriciales en PSD (programación semidefinida). Específicamente, un problema semidefinido general puede ser definido como cualquier problema de programación matemática de la siguiente forma

${\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 toda }}k\\\end{array}}$

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

Formulaciones equivalentes

Decimos que una matriz $M$ de $n\times n$ es positivo semidefinida si es la matriz de Gram de algunos vectores (i.e. si existen vectores $x^{1},\ldots ,x^{n}$ tal que $m_{i,j}=x^{i}\cdot x^{j}$ para todo $i,j$). Si esto es el caso , lo denotamos con $M\succeq 0$. Notemos que hay muchas otras definiciones equivalentes de para que una matriz sea positivo semidefinida; por ejemplo, matrices positivo semidefinidas son matrices auto-adjuntas que tienen únicamente eigenvalores no negativos.

Denotamos por $\mathbb {S} ^{n}$ al espacio de todas las matrices reales simétricas de $n\times n$. El espacio está equipado con el producto interno (dónde ${\rm {tr}}$ denota la traza)$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(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 equivalentemente de la siguiente manera

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

Dónde la entrada $i,j$ en $C$ está dada por ${\frac {c_{i,j}+c_{j,i}}{2}}$ de la sección anterior, y $A_{k}$ es una matriz simétrica de $n\times n$ cuya entrada $i,j$ es igual a ${\frac {a_{i,j,k}+a_{j,i,k}}{2}}$ de la sección anterior. Así, las matrices $C$ y $A_{k}$ son simétricas, y los productos interiores de arriba están bien definidos.

Notemos que si añadimos variables de holgura apropiadamente, este PSD puede ser convertido a uno de la forma

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

Por conveniencia, un PSD puede ser especificado ligeramente diferente, pero forma equivalente. Por ejemplo, las expresiones lineales que tienen variables escalares no negativas pueden ser añadidas a la especificación del programa. Esto sigue siendo un PSD porque cada variable puede ser incorporada a la matriz $X$ como entrada diagonal ($X_{ii}$ para algunos $i$). Para asegurar que $X_{ii}\geq 0$, las restricciones $X_{ij}=0$ pueden ser añadidas para todo $j\neq i$. Por otro ejemplo, nota que para cualquier matriz positivo semidefinida $X$, existe un conjunto de vectores $\{v_{i}\}$ tal que la entrada $i$, $j$ de $X$ es $X_{ij}=(v_{i},v_{j})$, el producto escalar de $v_{i}$ y $v_{j}$. Por lo tanto, los PSDs a menudo son formulados en términos de expresiones lineales en productos escalares de vectores. Dada la solución al PSD en forma estándar, los vectores $\{v_{i}\}$ pueden ser recuperados en tiempo $O(n^{3})$ (p. ej., por utilizando una factorización de Cholesky incompleta de X).

Teoría de dualidad

Definiciones

Análogamente a programación lineal, dado un PSD general de la forma

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

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

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{sujeto a}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}$

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{sujeto a}}&\sum _{i=1}^{m}y_{i},A_{i}\preceq C\end{array}}$

donde para cualesquiera dos matrices $P$ y $Q$, $P\succeq Q$ significa que $P-Q\succeq 0$.

Dualidad débil

El teorema de la dualidad débil declara que el valor del PSD primal es al menos el valor del PSD dual. Por tanto, cualquier solución factible al PSD dual es una cuota inferior para el valor primal del PSD, y conversamente, cualquier solución factible al PSD primal es una cuota superior para el valor del PSD dual. Esto es porque

$\langle C,X\rangle -\langle b,y\rangle =\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 es porque ambas matrices son positivas semidefinidas, y el resultado de esta función es a veces referido como brecha de dualidad.

Dualidad fuerte

Bajo una condición conocida como la condición de Slater, el valor del PSD primal y dual es igual. esto se le llama dualidad fuerte. Diferente que para programas lineales, sin embargo, no cualquier PSD satisface dualidad fuerte; en general, el valor del PSD dual puede ser estrictamente menor al valor del programa primal.

(i) Supongamos que el problema primal (P-SDP) está acotado abajo y es estrictamente viable (i.e., existe $X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0$ tal que $\langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_{i}$, $i=1,\ldots ,m$). Entonces hay un solución óptima $y^{*}$ para (D-SDP) y

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}.$

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

Ejemplos

Ejemplo 1

Considera tres variables aleatorias $A$, $B$, y $C$. Por definición, sus coeficientes de correlación $\rho _{AB},\ \rho _{AC},\rho _{BC}$ son válidos sí y sólo si

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

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

${\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{sujeto a}}&-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}}$

Pusimos $\rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}$ para obtener la respuesta. Esto puede ser formulado por un PSD. Manejamos las restricciones de desigualdad aumentando la matriz variable e introduciendo variables de holgura, por ejemplo

$\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 PSD nos da los valores mínimos y máximos de $\rho _{AC}=x_{13}\$como $-0.978$ y $0.872$, respectivamente.

Ejemplo 2

Considera el problema

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

sujeto a que $Ax+b\geq 0$

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

Introduciendo una variable auxiliar $t$, el problema puede ser reformulado como lo siguiente:

Minimiza $t$

sujeto a$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 en las variables $x,t$.

La primera restricción puede ser escrita como

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

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

La segunda restricción puede ser escrita como

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

Definiendo a $D$ como sigue

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

Podemos utilizar la teoría de Complementos de Schur para ver que

$D\succeq 0$

(Boyd y Vandenberghe, 1996)

El programa semidefinido asociado con este problema es

Minimiza $t$

Sujeto a $\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$

Ejemplo 3 (Algoritmo de aproximación de máximo corte de Goemans–Williamson)

Los programas semidefinidos son herramientas importantes para desarrollar algoritmos de aproximación problemas de maximización NP-difíciles.

El primer algoritmo de aproximación basado en un PSD se debe a Michel Goemans y David P. Williamson (JACM, 1995). Estudiaron el problema de corte máximo: Dado un grafo G = (V, E), queremos producir una partición de los vértices V con el objetivo de maximizar el número de aristas que cruzan de un lado al otro. Este problema puede ser expresado como un programa entero cuadrático:

Maximiza $\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},$ Tal que cada $v_{i}\in \{1,-1\}$.

A no ser que P = NP, no podemos solucionar este problema de maximización eficientemente. Aun así, Goemans y Williamson observaron un procedimiento general de tres pasos para atacar esta clase de problema:

1. Relaja el programa entero cuadrático a un PSD.
2. Soluciona el PSD (dentro de un error aditivo arbitrariamente pequeño $\epsilon$).
3. Redondea la solución del PSD para obtener una solución aproximada al programa entero cuadrático original.

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

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

Esto es un PSD porque la función objetiva y las restricciones son todas funciones lineales de productos interiores de vectores. Solucionar el SDP nos da un conjunto de vectores unitarios en $\mathbf {R^{n}}$; ya que no se requiere que los vectores sean colineales, el valor óptimo de este programa relajado sólo puede ser mayor que el valor del programa entero cuadrático original. Finalmente, un procedimiento de redondeo se necesita para obtener una partición. Goemans y Williamson sencillamente escogen un hiperplano de manera uniformemente aleatoria que pase a través del origen y dividen los vértices según el lado del hiperplano en el que sus vectores correspondientes yacen. Un análisis directo muestra que este procedimiento consigue una proporción de aproximación esperada (garantía de rendimiento) de 0.87856 - ε. (el valor esperado del corte es la suma sobre las aristas de la probabilidad que esta arista sea cortada, la cual es proporcional al ángulo $\cos ^{-1}\langle v_{i},v_{j}\rangle$ entre los vectores que delimitan la arista, sobre $\pi$. Comparando esta probabilidad con $(1-\langle v_{i},v_{j}\rangle )/{2}$, en esperanza la proporción es siempre al menos 0.87856.). Asumiendo que la conjetura de juegos única es cierta, se puede mostrar que esta proporción de aproximación es esencialmente optimal.

Desde la publicación original de Goemans y Williamson, los PSDs han sido aplicados para desarrollar numerosos algoritmos de aproximación. Recientemente, Prasad Raghavendra ha desarrollado un marco general para problemas de satisfacción del restricción basado en la conjetura de juegos única.​

Algoritmos

Hay varios tipos de algoritmos para solucionar PSDs. Estos algoritmos producen el valor del PSD hasta un error aditivo de $\epsilon$ en un tiempo que es polinomial con respecto al tamaño de la descripción del programa y $\log(1/\epsilon )$.

Hay también algoritmos de reducción facial que pueden ser utilizados para preprocesar problemas PSDs por medio de la inspección de las restricciones del problema. Estos pueden ser usados para detectar falta de viabilidad estricta, para eliminar columnas y filas redundantes, y también para reducir la medida de la matriz variable.​

Métodos de punto interior

La mayoría de los códigos están basados en métodos de punto interior (CSDP, MOSEK, SeDuMi, SDPT3, DSDP, SDPA). Estos métodos son robustos y eficaces para problemas PSD lineales generales. Están limitados por el hecho que los algoritmos son métodos de segundo orden y necesitan almacenar y factorizar una matriz grande (y a menudo densa).

Métodos de primer orden

Métodos de primer orden para la optimización cónica evitan la computación, almacenando y factorizando una matriz Hessiana grande y escalan a problemas mucho más grandes que métodos de punto interior, bajo algún coste en exactitud. Un método de primer orden está implementado en el Solucionador por medio de Partición (Splitting Cone Solver, SCS).​ Otro método de primer orden es el método de dirección alterna de multiplicadores (ADMM).​ Este método requiere en cada paso la proyección hacia el cono de matrices semidefinidas.

Método de manojo

El código ConicBundle formula el problema de la PSD como un problema de optimización no-suave, y lo soluciona por medio del método de Manojo Espectral de optimización no suave. Esta heurística es muy eficiente para una clase especial de problemas PSD lineares.

Otros métodos de solución

Los algoritmos basados en el Método Lagrangiano Aumentado (PENSDP) son similares en comportamiento a los métodos de punto interior y pueden ser especializados a algunos problemas de gran escala. Otros algoritmos utilizan información de bajo rango, y la reformulación del PSD como un problema de programación no lineal (SDPLR).​

Métodos aproximados

Se han propuesto también algoritmos que solucionan PSDs aproximadamente. El objetivo principal de tales métodos es conseguir una menor complejidad en aplicaciones donde las soluciones aproximadas son suficientes y la complejidad tiene que ser mínima. Un método prominente que ha sido 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 Triangular Aproximada (TASER), la cual opera en los factores de la descomposición de Cholesky de la matriz semidefinida en vez de en la matriz semidefinida.​ Este método calcula soluciones aproximadas para un problema de tipo corte máximo (max-cut) que son a menudo comparables a las soluciones de solucionadores exactos solvers pero tan sólo 10-20 iteraciones del algoritmo.

Aplicaciones

La programación semidefinida ha sido aplicada para encontrar soluciones aproximadas a problemas de optimización combinatoria, como la solución del problema de corte máximo con una proporción de aproximación de 0.87856. Los PSDs también son usados en geometría para determinar grafos de tensegridad, y surgen en teoría de control como DMLs(desigualdades de matrices lineares), y en problemas de coeficiente elípticos inversos como restricciones convexas y no-lineales, de semidefinición.​ .

 Otras lecturas

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp. 49–95. Pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. Optimización-on-line
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, ISBN 1-4020-0547-4 .
• Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introducción

Enlaces externos

• Enlaces a introducciones y acontecimientos en el campo
• Notas de conferencia Archivado el 14 de marzo de 2017 en Wayback Machine. de László Lovász en Programación Semidefinida.

• Datos: Q2269096