Programación semidefinida

Subcampo de optimización convexa

La programación semidefinida ( SDP ) es un subcampo de la programación matemática 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 espectroedro . ^[1]

La programación semidefinida es un campo de optimización relativamente nuevo que resulta de creciente interés por varias razones. Muchos problemas prácticos de la investigación de operaciones y la optimización combinatoria pueden modelarse o aproximarse como problemas de programación semidefinida. En la teoría del control automático, los SDP se utilizan en el contexto de desigualdades matriciales lineales . De hecho, los SDP son un caso especial de programación de conos y pueden resolverse eficientemente mediante métodos de puntos interiores . Todos los programas lineales y los programas cuadráticos (convexos) se pueden expresar como SDP y, mediante jerarquías de SDP, se pueden aproximar las soluciones de problemas de optimización polinómica. La programación semidefinida se ha utilizado en la optimización de sistemas complejos. En los últimos años, algunos problemas de complejidad de consultas cuánticas se han formulado 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 programación semidefinida, utilizamos vectores de valores reales y se nos permite tomar el producto escalar de los vectores; Las restricciones de no negatividad sobre variables reales en LP ( programación lineal ) se reemplazan por restricciones de semidefinición sobre variables matriciales en SDP ( programación semidefinida ). Específicamente, un problema general de programación semidefinida se puede definir 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{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}k\\\end{array}}}$

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

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 este es el caso, lo denotamos como . Tenga en cuenta que existen varias otras definiciones equivalentes de ser semidefinido positivo, por ejemplo, las matrices semidefinidas positivas son matrices autoadjuntas que solo tienen valores propios no negativos . ${\displaystyle n\times n}$ ${\displaystyle M}$ ${\displaystyle x^{1},\ldots ,x^{n}}$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j}}$ ${\displaystyle i,j}$ ${\displaystyle M\succeq 0}$

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

${\displaystyle \langle A,B\rangle :={\rm {trace}}(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 manera equivalente como

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

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

Tenga en cuenta que si agregamos variables de holgura de manera adecuada, 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{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

Por conveniencia, un SDP puede especificarse en una forma ligeramente diferente, pero equivalente. Por ejemplo, se pueden agregar a la especificación del programa expresiones lineales que involucran variables escalares no negativas. Esto sigue siendo un SDP porque cada variable se puede incorporar a la matriz como una entrada diagonal ( para algunos ). Para garantizar esto , se pueden agregar restricciones para todos . Como otro ejemplo, observe que para cualquier matriz semidefinida positiva , existe un conjunto de vectores tal que la 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 del SDP en la forma estándar, los vectores se pueden recuperar a tiempo (por ejemplo, utilizando una descomposición de Cholesky incompleta de X). ${\displaystyle X}$ ${\displaystyle X_{ii}}$ ${\displaystyle i}$ ${\displaystyle X_{ii}\geq 0}$ ${\displaystyle X_{ij}=0}$ ${\displaystyle j\neq i}$ ${\displaystyle X}$ ${\displaystyle \{v_{i}\}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle X}$ ${\displaystyle X_{ij}=(v_{i},v_{j})}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle \{v_{i}\}}$ ${\displaystyle O(n^{3})}$

Relaciones con otros problemas de optimización.

El espacio de matrices semidefinidas es un cono convexo . Por lo tanto, SDP es un caso especial de optimización cónica , que es un caso especial de optimización convexa.

Cuando la matriz C es diagonal, los productos internos < C , X > equivalen a un producto vectorial de la diagonal de C y la diagonal de X . De manera análoga, cuando las matrices A _k son diagonales, los productos internos correspondientes son equivalentes a productos vectoriales. En estos productos vectoriales, solo se utilizan los elementos diagonales de X , por lo que podemos agregar restricciones que igualen los elementos no diagonales de X a 0. La condición es entonces equivalente a la condición de que todos los elementos diagonales de X no sean negativos. Entonces, el SDP resultante se convierte en un programa lineal en el que las variables son los elementos diagonales de X. ${\displaystyle X\succeq 0}$

Teoría de la dualidad

Definiciones

De manera 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{subject to}}&\langle A_{i},X\rangle =b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}}$

(el problema primario 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 dos matrices cualesquiera y , significa . ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P\succeq Q}$ ${\displaystyle P-Q\succeq 0}$

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 del SDP primario y, a la inversa, cualquier solución factible para el SDP primario limita el valor del SDP dual. Esto es porque

${\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.

Fuerte dualidad

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

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

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

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

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

Ejemplos

Ejemplo 1

Considere tres variables aleatorias , y . Un conjunto dado de coeficientes de correlación es posible si y sólo si ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle \rho _{AB},\ \rho _{AC},\rho _{BC}}$

${\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 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 se pueden tomar viene dado por: ${\displaystyle -0.2\leq \rho _{AB}\leq -0.1}$ ${\displaystyle 0.4\leq \rho _{BC}\leq 0.5}$ ${\displaystyle \rho _{AC}\ }$

${\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}}}$

Nos dispusimos a 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 ${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}}$

${\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}$

Al resolver este SDP se obtienen los valores mínimo y máximo de as y respectivamente. ${\displaystyle \rho _{AC}=x_{13}\ }$ ${\displaystyle -0.978}$ ${\displaystyle 0.872}$

Ejemplo 2

Considere el problema

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

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

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

Introduciendo una variable auxiliar el problema se puede reformular: ${\displaystyle t}$

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 es la matriz cuadrada con valores en la diagonal iguales a los elementos del vector . ${\displaystyle {\textbf {diag}}(Ax+b)}$ ${\displaystyle Ax+b}$

La segunda restricción se puede escribir como

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

Definiendo de la siguiente manera ${\displaystyle D}$

${\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 con 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}$

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-duro. El primer algoritmo de aproximación basado en un SDP se debe a Michel Goemans y David P. Williamson (JACM, 1995). ^{[1] : Capítulo} 1 Estudiaron el problema de corte máximo : Dado un gráfico G = ( V , E ), genera una partición de los vértices V para maximizar el número de aristas que se cruzan de un lado al otro. Este problema se puede expresar como un programa cuadrático entero :

Maximice de manera que cada . ${\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},}$ ${\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 atacar este tipo de problema:

1. Relaje el programa cuadrático entero en un SDP.
2. Resuelva el SDP (dentro de 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}},}$tal que , donde la maximización es sobre vectores en lugar de escalares enteros. ${\displaystyle \lVert v_{i}\rVert ^{2}=1}$ ${\displaystyle \{v_{i}\}}$

Este es un SDP porque la función objetivo y las restricciones son todas funciones lineales de productos internos vectoriales. Al resolver el SDP se obtiene un conjunto de vectores unitarios en ; dado que no es necesario que los vectores sean colineales, el valor de este programa relajado sólo puede ser mayor que el valor del programa entero cuadrático original. Finalmente, es necesario un procedimiento de redondeo para obtener una partición. Goemans y Williamson simplemente eligen un hiperplano uniformemente aleatorio 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 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 , en la expectativa la relación siempre está en menos 0,87856.) Suponiendo la conjetura de los juegos únicos , se puede demostrar que esta relación de aproximación es esencialmente óptima. ${\displaystyle \mathbf {R^{n}} }$ ${\displaystyle \cos ^{-1}\langle v_{i},v_{j}\rangle }$ ${\displaystyle \pi }$ ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}}$

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 los juegos únicos . ^[4]

Otras aplicaciones

Se ha aplicado 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 y en problemas de coeficientes elípticos inversos como restricciones de semidefinición convexas, no lineales. ^[5] También se usa ampliamente en física para restringir las teorías de campos conformes con el bootstrap conforme . ^[6]

Complejidad del tiempo de ejecución

El problema de viabilidad semidefinido (SDF) es el siguiente problema de decisión : dado un SDP, decida si tiene al menos una solución factible. Se desconoce la complejidad exacta del tiempo de ejecución de este problema (hasta 1997). Sin embargo, Ramana demostró lo siguiente: ^[2]

• En el modelo de máquina de Turing , SDF está en NP si está en co-NP. Por lo tanto, SDF no es NP completo a menos que NP = coNP.
• En el modelo de máquina Blum-Shub-Smale , SDF está en la intersección de NP y co-NP.

Algoritmos para resolver SDP

Existen varios tipos de algoritmos para resolver SDP. Estos algoritmos generan el valor del SDP hasta un error aditivo en el tiempo que es polinómico en el tamaño de la descripción del programa y . ${\displaystyle \epsilon }$ ${\displaystyle \log(1/\epsilon )}$

método elipsoide

El método del elipsoide es un método general para la programación convexa y puede usarse en particular para resolver SDP. En el contexto de los SDP, el método del elipsoide proporciona la siguiente garantía. ^{[1] : Thm.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 ecuacionales; entonces el SDP se puede escribir como: . Supongamos que todos los coeficientes del SDP son números racionales. Sea R un límite superior dado explícitamente en la norma máxima de Frobenius de una solución factible, y ε> 0 una constante. Una matriz X en S ⁿ se llama ε-profunda si cada matriz Y en L con una distancia de Frobenius como máximo ε de X satisface la condición de viabilidad . Denotar . El elipsoide devuelve una de las siguientes salidas: ${\displaystyle \max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0}$ ${\displaystyle Y\succeq 0}$ ${\displaystyle v_{deep}:=\sup\{\langle C,X\rangle :X{\text{ is }}\epsilon {\text{-deep}}\}}$

• Una matriz X* en L (es decir, que satisface exactamente todas las restricciones de igualdad lineal), 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 ), y (es decir, valor objetivo aproximadamente óptimo). ${\displaystyle X\succeq 0}$ ${\displaystyle \langle C,X^{*}\rangle \geq v_{deep}-\epsilon }$
• Un certificado de que el problema no tiene soluciones ε-profundas (es decir, el problema es aproximadamente inviable).

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

Tenga en cuenta 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.

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). Estos son robustos y eficientes para problemas SDP lineales generales, pero están restringidos 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). Teóricamente, los algoritmos SDP de alta precisión más modernos ^{[7] [8]} se basan en este enfoque.

Métodos de primer orden

Los métodos de primer orden para la optimización cónica evitan calcular, almacenar y factorizar una matriz de Hesse grande y escalar a problemas mucho más grandes que los métodos de puntos interiores, con cierto costo en precisión. Se implementa un método de primer orden en Splitting Cone Solver (SCS). ^[9] Otro método de primer orden es el método de multiplicadores de dirección alterna (ADMM). ^[10] 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 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 eficiente 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 muy 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]

Métodos aproximados

También se han propuesto algoritmos que resuelven aproximadamente los SDP. 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 múltiples entradas y múltiples salidas (MIMO) es la relajación semidefinida aproximada triangular (TASER), ^[12] que opera con 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 de corte máximo que a menudo son comparables a las soluciones de solucionadores exactos, pero en solo 10 a 20 iteraciones de 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.

Algoritmos de preprocesamiento

Los algoritmos de reducción facial son algoritmos que se utilizan para preprocesar problemas de SDP mediante la inspección de las restricciones del problema. Estos pueden usarse para

• Detectar falta de viabilidad estricta;
• Eliminar filas y columnas redundantes;
• Reducir el tamaño de la matriz variable. ^[14]

Ver también

• Problema de suma de raíces cuadradas : un caso especial de un problema de viabilidad del SDP.

Referencias

1. Gärtner, Bernd; Matoušek, Jiří (2012), Gärtner, Bernd; Matousek, Jiri (eds.), "Programación semidefinida", Algoritmos de aproximación y programación semidefinida , Berlín, Heidelberg: Springer, págs. 15-25, doi :10.1007/978-3-642-22015-9_2, ISBN 978-3-642-22015-9, recuperado el 31 de diciembre de 2023
2. Ramana, Motakuri V. (1997). "Una teoría de la dualidad exacta para la programación semidefinida y sus implicaciones de complejidad". Programación Matemática . 77 (1): 129–162. doi :10.1007/BF02614433. ISSN  0025-5610. S2CID  12886462.
3. Vandenberghe, Lieven; Boyd, Stephen (1996). "Programación semidefinida". Revisión SIAM . 38 (1): 49–95. doi :10.1137/1038003. ISSN  0036-1445.
4. Raghavendra, Prasad (2008). "¿Algoritmos óptimos y resultados de inaccesibilidad para cada CSP?". Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática . págs. 245-254. doi :10.1145/1374376.1374414. ISBN 9781605580470. S2CID  15075197.
5. Harrach, Bastian (2021), "Resolver un problema de coeficiente elíptico inverso mediante programación semidefinida no lineal convexa", Optimization Letters , 16 (5): 1599–1609, arXiv : 2105.11440 , doi : 10.1007/s11590-021-01802- 4, S2CID  235166806
6. Simmons-Duffin, David (6 de febrero de 2015). "Un solucionador de programas semidefinido para Bootstrap conforme". Revista de Física de Altas Energías . 2015 (6): 174. arXiv : 1502.02033 . Código Bib : 2015JHEP...06..174S. doi :10.1007/JHEP06(2015)174. S2CID  256009551.
7. Jiang, Haotian; Kathuria, Tarún; Lee, Yin Tat; Padmanabhan, Swati; Song, Zhao (noviembre de 2020). "Un método de punto interior más rápido para programación semidefinida". 2020 61.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) . Durham, Carolina del Norte, Estados Unidos: IEEE. págs. 910–918. arXiv : 2009.10217 . doi :10.1109/FOCS46700.2020.00089. ISBN 978-1-7281-9621-3. S2CID  221836388.
8. Huang, Baihe; Jiang, Shunhua; Canción, Zhao; Tao, Runzhou; Zhang, Ruizhe (18 de noviembre de 2021). "Resolver SDP más rápido: un marco IPM sólido e implementación eficiente". arXiv : 2101.08208 [matemáticas.OC].
9. Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Optimización cónica mediante división de operadores e incrustación autodual homogénea", Revista de teoría y aplicaciones de optimización, 2016, págs. 1042--1068, https://web. stanford.edu/~boyd/papers/pdf/scs.pdf.
10. Wen, Zaiwen, Donald Goldfarb y Wotao Yin. "Métodos lagrangianos aumentados de dirección alterna para programación semidefinida". Computación de programación matemática 2.3-4 (2010): 203-230.
11. Burer, Samuel; Monteiro, Renato DC (2003), "Un algoritmo de programación no lineal para resolver programas semidefinidos mediante factorización de rango bajo", 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 
12. 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 semidefinida aproximada". Transacciones IEEE sobre circuitos y sistemas I: artículos habituales . 63 (12): 2334–2346. arXiv : 1609.01797 . doi : 10.1109/TCSI.2016.2607198 . hdl : 20.500.11850/448631. ISSN  1558-0806.
13. Hazán, Elad (2008). Laber, Eduardo Sany; Bornstein, Claudson; Nogueira, Loana Tito; Faria, Luerbio (eds.). "Escasas soluciones aproximadas para programas semidefinidos". LATINO 2008: Informática Teórica . Apuntes de conferencias sobre informática. Berlín, Heidelberg: Springer: 306–316. doi :10.1007/978-3-540-78773-0_27. ISBN 978-3-540-78773-0.
14. 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

• Lieven Vandenberghe, Stephen Boyd, "Programación semidefinida", SIAM Review 38, marzo de 1996, págs. pdf
• Monique Laurent, Franz Rendl, "Programación semidefinida y programación entera", Informe PNA-R0210, CWI, Amsterdam, abril de 2002. optimización en línea
• E. de Klerk, "Aspectos de la programación semidefinida: 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 en el campo.
• Apuntes de conferencias de László Lovász sobre programación semidefinida