La programación semidefinida ( SDP ) es un subcampo de optimización convexa que se ocupa de la optimización de una función objetivo lineal (una función especificada por el usuario que el usuario desea minimizar o maximizar) sobre la intersección del cono de matrices semidefinidas positivas con un espacio afín , es decir, un espectraedro .
La programación semidefinida es un campo de optimización relativamente nuevo que tiene un interés creciente por varias razones. Muchos problemas prácticos en 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 SDP se utilizan en el contexto de desigualdades de matrices lineales . Los SDP son, de hecho, un caso especial de programación de cono y pueden resolverse de manera eficiente mediante métodos de puntos interiores . Todos los programas lineales se pueden expresar como SDP y, a través de jerarquías de SDP, se pueden aproximar las soluciones de los problemas de optimización polinomial. La programación semidefinida se ha utilizado en la optimizaciónde sistemas complejos. En los últimos años, se han formulado algunos problemas de complejidad de consultas cuánticas en términos de programas semidefinidos.
Motivación y definición
Motivación inicial
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 su lugar usamos vectores de valor real y se nos permite tomar el producto escalar de los vectores; las restricciones de no negatividad sobre las variables reales en LP ( programación lineal ) se reemplazan por las restricciones de semidefinidad en las variables de matriz en SDP ( programación semidefinida ). Específicamente, un problema de programación semidefinido general se puede definir como cualquier problema de programación matemática de la forma
donde el , y el son números reales y es el producto escalar de y .
Formulaciones equivalentes
Un matriz se dice que es semidefinido positivo si es la matriz de Gramian de algunos vectores (es decir, si existen vectores tal que para todos ). Si este es el caso, lo denotamos como. Tenga en cuenta que hay varias otras definiciones equivalentes de ser semidefinito positivo, por ejemplo, las matrices semidefinidas positivas son matrices autoadjuntas que solo tienen valores propios no negativos .
Denotamos por el espacio de todos matrices simétricas reales. El espacio está equipado con el producto interior (dondedenota el rastro )
Podemos reescribir el programa matemático dado en la sección anterior de manera equivalente como
donde entrada en es dado por de la sección anterior y es simétrico matriz que tiene entonces intenta de la sección anterior. Por tanto, las matrices y son simétricos y los productos internos anteriores están bien definidos.
Tenga en cuenta que si agregamos las variables de holgura de manera adecuada, este SDP se puede convertir a uno de los formatos
Por conveniencia, un SDP puede especificarse en una forma ligeramente diferente, pero equivalente. Por ejemplo, las expresiones lineales que involucran variables escalares no negativas pueden agregarse a la especificación del programa. Esto sigue siendo un SDP porque cada variable se puede incorporar a la matriz. como una entrada diagonal para algunos ). Para asegurar eso, limitaciones se puede agregar para todos . Como otro ejemplo, observe que para cualquier matriz semidefinida positiva, existe un conjunto de vectores tal que el , entrada de es el producto escalar de y . Por lo tanto, los SDP a menudo se formulan en términos de expresiones lineales sobre productos escalares de vectores. Dada la solución al SDP en la forma estándar, los vectores se puede recuperar en tiempo (por ejemplo, utilizando una descomposición Cholesky incompleta de X).
Teoría de la dualidad
Definiciones
De manera análoga a la programación lineal, dado un SDP general de la forma
(el problema primario o P-SDP), definimos el programa semidefinito dual (D-SDP) como
donde para dos matrices cualesquiera y , medio .
Dualidad débil
El teorema de la dualidad débil establece que el valor del SDP primario es al menos el valor del SDP dual. Por lo tanto, cualquier solución factible para el SDP dual limita el valor de SDP primario y, a la inversa, cualquier solución factible para el SDP primario limita los límites superiores del valor de SDP dual. Esto es porque
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.
Fuerte dualidad
Bajo una condición conocida como condición de Slater , el valor de los SDP primarios y duales son iguales. Esto se conoce como dualidad fuerte . Sin embargo, a diferencia de los programas lineales , no todos los SDP satisfacen una fuerte dualidad; en general, el valor del SDP dual puede estar estrictamente por debajo del valor del primario.
(i) Suponga que el problema primario (P-SDP) está delimitado por debajo y es estrictamente factible (es decir, existe tal que , ). Entonces hay una solución óptima a (D-SDP) y
(ii) Suponga que el problema dual (D-SDP) está delimitado por encima y es estrictamente factible (es decir, para algunos ). Entonces hay una solución óptima a (P-SDP) y se mantiene la igualdad de (i).
Ejemplos de
Ejemplo 1
Considere tres variables aleatorias , , y . Por definición, sus coeficientes de correlación son válidos si y solo si
en cuyo caso esta matriz se denomina matriz de correlación . Supongamos que sabemos por algún conocimiento previo (resultados empíricos de un experimento, por ejemplo) que y . El problema de determinar los valores más pequeños y más grandes que puede tomar viene dado por:
- minimizar / maximizar
- sujeto a
Establecimos para obtener la respuesta. Esto puede ser formulado por un SDP. Manejamos las restricciones de desigualdad aumentando la matriz de variables e introduciendo variables de holgura , por ejemplo
Resolver este SDP da los valores mínimo y máximo de como y respectivamente.
Ejemplo 2
Considere el problema
- minimizar
- sujeto a
donde asumimos que cuando sea .
Introduciendo una variable auxiliar el problema se puede reformular:
- minimizar
- sujeto a
En esta formulación, el objetivo es una función lineal de las variables .
La primera restricción se puede escribir como
donde la matriz es la matriz cuadrada con valores en la diagonal iguales a los elementos del vector .
La segunda restricción se puede escribir como
Definiendo como sigue
Podemos usar la teoría de los complementos de Schur para ver que
(Boyd y Vandenberghe, 1996)
El programa semidefinito asociado con este problema es
- minimizar
- sujeto a
Ejemplo 3 (algoritmo de aproximación de corte máximo de Goemans-Williamson)
Los programas semidefinidos son herramientas importantes para desarrollar algoritmos de aproximación para problemas de maximización NP-hard. El primer algoritmo de aproximación basado en un SDP se debe a Michel Goemans y David P. Williamson (JACM, 1995). Estudiaron el problema de corte máximo : dado un gráfico G = ( V , E ), genere una partición de los vértices V para maximizar el número de bordes que se cruzan de un lado al otro. Este problema se puede expresar como un programa cuadrático entero :
- Maximizar tal que cada .
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 atacar este tipo de problema:
- Relaja el programa cuadrático entero en un SDP.
- Resuelva el SDP (dentro de un error aditivo arbitrariamente pequeño ).
- 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
- tal que , donde la maximización está sobre los vectores en lugar de escalares enteros.
Este es un SDP porque la función objetivo y las restricciones son todas funciones lineales de los productos internos del vector. Resolver el SDP da un conjunto de vectores unitarios en; 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 uniformemente aleatorio a través del origen y dividen los vértices según el lado del hiperplano que se encuentran los vectores correspondientes. Un análisis sencillo muestra que este procedimiento logra un índice de aproximación esperado (garantía de desempeño) 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 entre los vectores en los puntos finales del borde sobre . Comparando esta probabilidad con, con la expectativa de que la proporción sea siempre de al menos 0,87856). Suponiendo la conjetura de juegos únicos , se puede demostrar que esta proporció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. Recientemente, Prasad Raghavendra ha desarrollado un marco general para problemas de satisfacción de restricciones basado en la conjetura de juegos únicos . [1]
Algoritmos
Hay varios tipos de algoritmos para resolver SDP. Estos algoritmos generan el valor del SDP hasta un error aditivo en el tiempo que es polinomial en el tamaño de la descripción del programa y .
También existen algoritmos de reducción facial que se pueden utilizar para preprocesar los problemas de SDP mediante la inspección de las limitaciones del problema. Estos se pueden utilizar para detectar la falta de viabilidad estricta, para eliminar filas y columnas redundantes y también para reducir el tamaño de la matriz de variables. [2]
Métodos de puntos interiores
La mayoría de los códigos se basan en métodos de puntos interiores (CSDP, MOSEK , SeDuMi, SDPT3, DSDP, SDPA). Robusto y eficiente para problemas generales de SDP lineal. Restringido por el hecho de 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
Los métodos de primer orden para la optimización cónica evitan calcular, almacenar y factorizar una matriz hessiana grande y escalar a problemas mucho más grandes que los métodos de puntos interiores, con cierto costo en precisión. Un método de primer orden se implementa en Splitting Cone Solver (SCS). [3] Otro método de primer orden es el método de multiplicadores de dirección alterna (ADMM). [4] Este método requiere en cada paso la proyección sobre el cono de matrices semidefinidas.
Método de paquete
El código ConicBundle formula el problema de SDP como un problema de optimización no suave y lo resuelve mediante el método Spectral Bundle de optimización no suave. Este enfoque es muy eficaz para una clase especial de problemas SDP lineales.
Otros métodos de resolución
Los algoritmos basados en el método lagrangiano aumentado (PENSDP) tienen un comportamiento similar a los métodos de puntos interiores y pueden especializarse en algunos problemas de gran escala. Otros algoritmos utilizan información de bajo rango y reformulación del SDP como un problema de programación no lineal (SDPLR). [5]
Métodos aproximados
También se han propuesto algoritmos que resuelven los SDP aproximadamente. El objetivo principal de tales 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 múltiples entradas y múltiples salidas (MIMO) es la relajación triangular aproximada SEmidefinita (TASER), [6] que opera sobre los factores de descomposición de Cholesky de la matriz semidefinita en lugar de la matriz semidefinita. . Este método calcula soluciones aproximadas para un problema similar a un corte máximo que a menudo son comparables a las soluciones de los solucionadores exactos, pero en solo 10-20 iteraciones de algoritmo.
Aplicaciones
Se ha aplicado la programación semidefinida para encontrar soluciones aproximadas a problemas de optimización combinatoria, como la solución del problema de corte máximo con una relación de aproximación de 0,87856. Los SDP también se utilizan en geometría para determinar gráficos de tensegridad y surgen en la teoría de control como LMI .
Referencias
- ^ Raghavendra, P. 2008. ¿ Algoritmos óptimos y resultados inadecuados para cada CSP? . En Actas del 40º Simposio Anual de ACM sobre teoría de la Computación (Victoria, Columbia Británica, Canadá, 17-20 de mayo de 2008). STOC '08. ACM, Nueva York, NY, 245-254.
- ^ Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019), "Sieve-SDP: un algoritmo de reducción facial simple para preprocesar programas semidefinidos" , Computación de programación matemática , 11 (3): 503–586, arXiv : 1710.08954 , doi : 10.1007 / s12532-019- 00164-4 , ISSN 1867-2949 , S2CID 53645581
- ^ Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Optimización cónica a través de la división del operador y la incrustación homogénea de uno mismo-dual", Journal of Optimization Theory and Applications, 2016, pp 1042-1068, https: // web. stanford.edu/~boyd/papers/pdf/scs.pdf .
- ^ Wen, Zaiwen, Donald Goldfarb y Wotao Yin. "La dirección alterna aumentó los métodos lagrangianos para la programación semidefinida". Computación de programación matemática 2.3-4 (2010): 203-230.
- ^ Monteiro, Renato DC; Burer, Samuel (2003), "Un algoritmo de programación no lineal para resolver programas semidefinidos mediante factorización de bajo rango", Programación matemática , 95 (2): 329–357, CiteSeerX 10.1.1.682.1520 , doi : 10.1007 / s10107-002- 0352-8 , ISSN 1436-4646 , S2CID 7691228
- ^ Castañeda, O .; Goldstein, T .; Studer, C. (diciembre de 2016). "Detección de datos en grandes sistemas inalámbricos de múltiples antenas mediante relajación semidefinita aproximada" . IEEE Transactions on Circuits and Systems I: Regular Papers . 63 (12): 2334–2346. doi : 10.1109 / TCSI.2016.2607198 . ISSN 1558-0806 .
- Lieven Vandenberghe, Stephen Boyd, "Programación semidefinita", SIAM Review 38, marzo de 1996, págs. 49–95. pdf
- Monique Laurent, Franz Rendl, "Programación semidefinita y programación entera", Informe PNA-R0210, CWI, Ámsterdam, abril de 2002. optimización-online
- E. de Klerk, "Aspectos de la programación semidefinita: algoritmos de puntos interiores y aplicaciones seleccionadas", Kluwer Academic Publishers, marzo de 2002, ISBN 1-4020-0547-4 .
- Robert M. Freund, "Introducción a la programación semidefinida (SDP), SDP-Introducción
enlaces externos
- Enlaces a presentaciones y eventos sobre el terreno
- Apuntes de la conferencia de László Lovász sobre Programación Semidefinita