Programación semidefinida

La programación semidefinida (o SDP del inglés. Programación semidefinida ) es una subsección de la programación convexa , que se ocupa de la optimización de una función objetivo lineal (la función objetivo es una función especificada por el usuario cuyo valor el usuario desea minimizar o maximizar) en el intersección de conos de matrices semidefinidas positivas con espacio afín .

La programación semidefinida es un área relativamente nueva de optimización que está creciendo en interés por varias razones. Muchos problemas prácticos en los campos de la investigación de operaciones y la optimización combinatoria se pueden modelar o aproximar como problemas de programación semidefinidos. En la teoría del control automático, los problemas SDP se utilizan en el contexto de las desigualdades de matrices lineales . Los problemas SDP son, de hecho, un caso especial de programación cónica y pueden resolverse eficientemente mediante el método del punto interior . Todos los problemas de programación lineal se pueden expresar como problemas SDP y, utilizando las jerarquías de problemas SDP, se pueden aproximar las soluciones a los problemas de optimización polinomial. La programación semidefinida se utiliza en la optimización de sistemas complejos . En los últimos años, se han formulado algunos problemas de complejidad de consultas cuánticas en términos de programación semidefinida.

Motivación y definición

Motivaciones iniciales

Un problema de programación lineal es un problema en el que necesita maximizar o minimizar una función objetivo lineal de variables reales en un poliedro . En la programación semidefinida, usamos vectores reales y se nos permite usar el producto escalar de vectores. La condición de no negatividad de las variables reales del problema PL se reemplaza por restricciones de semidefinición en la matriz de variables del problema SDP. En particular, un problema general de programación semidefinida se puede definir como cualquier problema de programación matemática de la forma

{\min_{x^{1},\ldots,x^{n}\in \mathbb {R} ^{n))}{\sum_{i,j\in [n]}c_ {i,j}(x^{i}\cdot x^{j})}

bajo condiciones

{\sum_{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}\qquad \forall k }.

Formulaciones equivalentes

Se dice que una matriz es semidefinida positiva si es la matriz de Gram de algunos vectores (es decir, si existen vectores tales que para todos ). Si esto es cierto, lo denotaremos como . Tenga en cuenta que hay algunas otras definiciones equivalentes de semidefinición positiva, por ejemplo, las matrices semidefinidas positivas solo tienen valores propios no negativos y tienen una raíz cuadrada semidefinida positiva. $n\veces n$ $METRO$ ${\displaystyle x^{1},\ldots,x^{n))$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j))$ $yo, j$ $M \succeq 0$

Denote por el espacio de todas las matrices simétricas reales. En este espacio hay un producto interior (donde significa rastro ) ${\ matemáticas {S}}^{n}$ $n\veces n$ $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1 }^{n}A_{ij}B_{ij}.$ ${\ estilo de visualización {\ rm {tr}}}$

Podemos reescribir el problema de programación matemática de la sección anterior en la forma equivalente

{\min_{X\in \mathbb {S} ^{n))}\langle C,X\rangle_{\mathbb {S} ^{n))

bajo condiciones

{\begin{array}{ll}{\displaystyle \langle A_{k},X\rangle _{\mathbb {S} ^{n))\leq b_{k},\quad k=1, \ldots,m}\\X\succeq 0\end{matriz}}

donde el elemento de la matriz es igual al del apartado anterior, y es una matriz que tiene como elemento de matriz el valor del apartado anterior. $yo, j$ $C$ ${\ Displaystyle c_ {i, j}}$ $Alaska$ $n\veces n$ $yo, j$ ${\ Displaystyle a_ {i, j, k}}$

Tenga en cuenta que si agregamos variables adicionales correctamente, esta tarea SDP se puede convertir en

{\displaystyle \min _{X\in \mathbb {S} ^{n))}\langle C,X\rangle _{\mathbb {S} ^{n))

bajo condiciones

{\begin{array}{ll}\langle A_{k},X\rangle _{\mathbb {S} ^{n))=b_{k},\quad k=1,\ldots,m \\X\succeq 0\end{matriz}}

Por conveniencia, el problema SDP se puede definir de una forma ligeramente diferente pero equivalente. Por ejemplo, las expresiones lineales que utilizan variables escalares no negativas se pueden agregar a la especificación de la tarea. La tarea sigue siendo SDP, ya que cada variable puede incluirse en la matriz como un elemento diagonal ( para algunos ). Para asegurarse , puede agregar restricciones para todos . Como otro ejemplo, observe que para cualquier matriz semidefinida positiva , existe un conjunto de vectores tal que el elemento de la matriz es igual a, el producto escalar de los vectores y . Por lo tanto, los problemas SDP a menudo se formulan en términos de expresiones lineales de productos escalares de vectores. Dada una solución al problema SDP en forma estándar, los vectores se pueden reconstruir en el tiempo (por ejemplo, usando una descomposición incompleta de la matriz X de Cholesky ). $X$ ${\ Displaystyle X_ {ii}}$ $i$ ${\ Displaystyle X_ {ii} \ geq 0}$ ${\ estilo de visualización X_ {ij} = 0}$ $j\neq i$ $X$ ${\ estilo de visualización \ {v_ {i} \}}$ $i$ $j$ $X$ $X_{ij}=(v_{i},v_{j})$ $v_{i}$ $v_{j}$ ${\ estilo de visualización \ {v_ {i} \}}$ $O(n^{3})$

Teoría de la dualidad

Definiciones

Similar a la programación lineal, si el problema general SDP se da en la forma

\min _{X\in \mathbb {S} ^{n}}\langle C,X\rangle _{\mathbb {S} ^{n}}

bajo condiciones

{\begin{array}{ll}\langle A_{i},X\rangle _{\mathbb {S} ^{n))=b_{i},\quad i=1,\ldots,m \\X\succeq 0\end{matriz}}

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

\max _{y\in \mathbb {R} ^{m}}\langle b,y\rangle _{\mathbb {R} ^{m}}

bajo condiciones

{\begin{array}{ll}{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}

Donde para cualesquiera dos matrices y , significa . $PAGS$ $q$ $P\succeq Q$ $PQ\succeq 0$

Dualidad débil

El teorema de la dualidad débil establece que el SDP primario tiene un valor no menor que el valor del SDP dual. Así, cualquier solución admisible del problema SDP dual limita el valor del SDP directo desde abajo, y viceversa, cualquier valor admisible del problema SDP directo limita el valor del SDP dual desde arriba. Esto sucede 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 refleja el hecho de que ambas matrices son semidefinidas positivas. El valor de esta función a veces se denomina despeje dual.

Fuerte dualidad

Bajo una condición conocida como condición de Slater , los valores de los problemas SDP primal y dual son iguales. Esto se llama dualidad fuerte . A diferencia de los problemas de programación lineal , no todos los problemas SDP tienen dualidad estricta. En el caso general, el valor del problema dual SDP puede ser estrictamente menor que el valor del problema directo.

(i) Suponga que el problema directo (P-SDP) está acotado por abajo y es estrictamente admisible (es decir, existe , tal que , ). Entonces hay una solución óptima para el problema dual (D-SDP) y $X_{0}\en \mathbb {S} ^{n},X_{0}\succ 0$ ${\displaystyle \langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n))=b_{i))$ $i=1,\ldots,m$ $y^{*}$

\langle C,X^{*}\rangle_{\mathbb {S} ^{n))=\langle b,y^{*}\rangle_{\mathbb {R} ^{m)) .

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

Ejemplos

Ejemplo 1

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

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

Supongamos que de algunas fuentes (por ejemplo, de datos empíricos o experimentales) sabemos que y . El problema de determinar los valores más pequeños y más grandes se puede escribir como: ${\ estilo de visualización -0.2 \ leq \ rho _ {AB} \ leq -0.1}$ ${\ estilo de visualización 0,4 \ leq \ rho _ {BC} \ leq 0,5}$ ${\ estilo de visualización \ rho _ {AC} \ }$

minimizar/maximizar

{\ estilo de visualización x_ {13}}

bajo condiciones

-0.2\leq x_{12}\leq -0.1

0.4\leq x_{23}\leq 0.5

x_{11}=x_{22}=x_{33}=1\

{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0

Aquí aceptamos . El problema se puede formular como un problema SDP. Completamos las desigualdades expandiendo la matriz de variables e introduciendo variables adicionales , por ejemplo ${\displaystyle \rho_{AB}=x_{12},\ \rho_{AC}=x_{13},\ \rho_{BC}=x_{23})$

$\mathrm {tr} \left(\left({\begin{matriz}{cccccc}0&1&0&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{matriz}}\right)\cdot \left({\begin{matriz}{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{matriz}}\right)\right)=x_{12}+s_{1}=-0,1$

Después de resolver este problema de SDP, obtenemos los valores mínimo y máximo ( y respectivamente). ${\ estilo de visualización \ rho _ {AC} = x_ {13} \ }$ ${\ estilo de visualización -0.978}$ ${\ estilo de visualización 0,872}$

Ejemplo 2

Considere el problema

minimizar

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

bajo las condiciones

Ax+b\geq 0

donde se supone que en . ${\ estilo de visualización d^{T}x>0}$ $Ax+b\geq 0$

Al introducir una variable adicional , reescribimos el problema en la forma: $t$

minimizar

t

bajo condiciones

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

En esta formulación, la función objetivo es una función lineal de dos variables ( ). ${\ estilo de visualización x, t}$

La primera restricción se puede reescribir como

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

donde matriz es una matriz cuadrada con valores en la diagonal iguales a los elementos del vector . ${\textbf {diag}}(Ax+b)$ ${\ estilo de visualización A + b}$

La segunda restricción se puede escribir como

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

Definimos la matriz de la siguiente manera $D$

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

Podemos usar la teoría del complemento de Schur para demostrar que

D\succeq 0

[una]

El problema de programación semidefinida para este problema será de la forma

minimizar

t

bajo condiciones

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

Ejemplo 3 (Algoritmo de aproximación Goemans-Williamson MAX CUT)

La programación semidefinida es una herramienta importante para crear algoritmos de aproximación para problemas de maximización NP-hard. El primer algoritmo de aproximación basado en SDP fue propuesto por Michel Goemans y David Williamson [2] . Estudiaron el problema MAX CUT : dado un gráfico G = ( V , E ), se requiere dividir los vértices de V en dos partes de tal manera que se maximice el número de aristas que conectan estas dos partes. El problema se puede considerar como un problema de programación cuadrática entera :

Maximizar sujeto a cualquier .

\sum_{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},

v_{i}\in\{1,-1\}

i

A menos que P = NP , no podemos resolver este problema de manera eficiente. Sin embargo, Goemans y Williamson describieron un procedimiento de tres pasos para atacar este tipo de problema:

Debilitamos el problema de programación cuadrática entera al problema SDP.
Resolvemos el problema SDP (con cualquier error arbitrariamente pequeño ). $\epsilon$
Redondeamos la solución del problema SDP para obtener una solución aproximada del problema original de programación cuadrática entera.

Para el problema MAX CUT , la relajación más natural es

\max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle {2)),

para , donde la maximización se realiza sobre vectores en lugar de variables enteras escalares.

\lVert v_{i}\rVert^{2}=1

{\ estilo de visualización \ {v_ {i} \}}

El problema es un problema SDP porque tanto la función objetivo como las restricciones son funciones lineales de los productos escalares de vectores. La solución al problema SDP da un conjunto de vectores unitarios en . Dado que los vectores no son necesariamente colineales, el valor del problema relajado solo puede ser mayor que el valor del problema original de programación cuadrática entera. Se necesita un procedimiento de redondeo final para obtener la división. Goemans y Williamson eligen un hiperplano aleatorio (utilizando una distribución uniforme) a través del origen y dividen los vértices según su ubicación relativa a ese plano. El análisis directo muestra que este procedimiento proporciona el factor de aproximación esperado de 0,87856 - ε. (El valor esperado de un corte es igual a la suma de todas las aristas de las probabilidades de que la arista entre en el corte, y esta expectativa es proporcional al ángulo entre los vectores en los vértices finales de la arista. Si comparamos esta probabilidad con , la expectativa de la relación siempre será al menos 0.87856.) Asumiendo la hipótesis de corrección del juego único , se puede demostrar que el coeficiente de aproximación de esta aproximación es principalmente óptimo. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2))$

Desde la aparición del artículo de Goemans y Williamson, los problemas SDP se han aplicado al desarrollo de un gran número de algoritmos de aproximación. Recientemente, Prasad Raghavendra desarrolló un esquema general para problemas de satisfacción de restricciones basado en la hipótesis del juego único [3] .

Algoritmos

Hay varios tipos de algoritmos para resolver problemas SDP. El resultado de estos algoritmos es el valor del problema SDP hasta , que se obtiene en un tiempo que depende polinomialmente del tamaño del problema y . $\epsilon$ ${\ estilo de visualización \ log (1/\ épsilon)}$

Métodos de puntos interiores

La mayoría de los sistemas de solución se basan en el método del punto interior (CSDP, SeDuMi, SDPT3, DSDP, SDPA), que es robusto y eficiente para problemas SDP lineales generales. El enfoque tiene un uso limitado por el hecho de que los algoritmos son métodos de segundo orden y requieren matrices grandes (ya menudo densas) para ser memorizadas y descompuestas.

Métodos de primer orden

Los métodos de primer orden para la optimización cónica evitan almacenar y descomponer matrices hessianas grandes y son aplicables a problemas mucho más grandes que los métodos de puntos interiores, a costa de una pérdida de precisión. El método se implementa en el sistema "SCS solver".

El método de la viga

El problema SDP se formula como un problema de optimización no uniforme y se resuelve mediante el método del haz espectral. Este enfoque es muy eficiente para clases particulares de problemas SDP lineales.

Otros

Los algoritmos basados en el método Lagrangiano generalizado (PENSDP) tienen un comportamiento similar a los métodos de puntos interiores y se pueden adaptar para algunos problemas muy grandes. Otros algoritmos utilizan información de bajo nivel y reformulan el problema SDP como un problema de programación no lineal (SPDLR).

Aplicaciones

La programación semidefinida se ha utilizado para encontrar soluciones aproximadas a problemas de optimización combinatoria, como resolver el problema de corte máximo con un factor de aproximación de 0,87856. Los problemas SDP también se utilizan en geometría para definir gráficos de tensegridad y aparecen en la teoría de control como desigualdades de matrices lineales .

Literatura

Lieven Vandenberghe, Stephen Boyd. Programación Semidefinida // Revista SIAM 38. - 1996. - Marzo. - S. 49-95 .
Monique Laurent, Franz Rendl. Programación Semidefinida y Programación Entera/Informe PNA-R0210, CWI, Amsterdam . - 2002. - Abril.
E. de Klerk. Aspectos de la Programación Semidefinida: Algoritmos de Punto Interior y Aplicaciones Seleccionadas. - Editores académicos de Kluwer, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. ¿Algoritmos óptimos y resultados de inaproximabilidad para cada CSP? // Actas del 40º Simposio Anual de ACM sobre teoría de la computación (Victoria, Columbia Británica, Canadá, 17 al 20 de mayo de 2008). STOC'08 . - Nueva York, NY: ACM, 2008. - S. 245-254.
Roberto M Freund. Introducción a la Programación Semidefinida (SDP) .
Michel X. Goemans, David P. Williamson. Algoritmos de aproximación mejorados para problemas de máximo corte y satisfacibilidad usando programación semidefinida // JACM. - 1995. - noviembre ( vol. 42 , número 6 ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Enlaces

Enlaces a presentaciones y eventos en el campo.
Apuntes de clase de László Lovász sobre programación semidefinida

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial