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 relativamente nuevo de optimización que está despertando un interés creciente por varias razones. Muchos problemas prácticos en 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, las SDP se utilizan en el contexto de las desigualdades matriciales lineales . Las 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 y los programas cuadráticos (convexos) pueden expresarse como SDP, y a través de jerarquías de SDP se pueden aproximar las soluciones de los 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 la programación semidefinida, en cambio, utilizamos vectores de valores reales y se nos permite tomar el producto escalar de vectores; las restricciones de no negatividad sobre variables reales en programación lineal (PL ) se reemplazan por restricciones de semidefinición sobre variables matriciales en programación semidefinida (SDP ). Específicamente, un problema de programación semidefinida general 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 todo ). Si este es el caso, lo denotamos como . Tenga en cuenta que existen otras definiciones equivalentes de ser semidefinida positiva, 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}$

Denotamos por el espacio de todas las matrices simétricas reales. El espacio está dotado del 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 en está dada por de la sección anterior y es una matriz simétrica que tiene la entrada de la sección anterior. Por lo 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, pueden agregarse 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 como una entrada diagonal ( para algunos ). Para asegurar que , se pueden agregar restricciones para todos los . Como otro ejemplo, observe que para cualquier matriz semidefinida positiva , existe un conjunto de vectores tales 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 pueden recuperarse en el 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 a su vez es un caso especial de optimización convexa.

Cuando la matriz C es diagonal, los productos internos < C , X > son equivalentes a un producto vectorial de la diagonal de C y la diagonal de X . Análogamente, 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 sean no 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 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 y , significa . ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P\succeq Q}$ ${\displaystyle P-Q\succeq 0}$

Dualidad débil

El teorema de 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 por debajo el valor del SDP primario y, a la inversa, cualquier solución factible para el SDP primario limita por encima 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.

Fuerte dualidad

Cuando el valor de los SDP primarios y duales son iguales, 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 la 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 primal (P-SDP) está acotado inferiormente y es estrictamente factible (es decir, existe tal que , ). Entonces hay 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 por encima y es estrictamente factible (es decir, para algún ). Entonces existe 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 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 en 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 solo 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 denomina matriz de correlación . Supongamos que sabemos a partir de 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: ${\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 disponemos a obtener la respuesta. Esta se puede formular mediante 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 como 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 que . ${\displaystyle d^{T}x>0}$ ${\displaystyle Ax+b\geq 0}$

Introduciendo una variable auxiliar el problema puede reformularse: ${\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 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}$

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). ^{[1] : Cap.1} Estudiaron el problema del corte máximo : Dado un grafo G = ( V , E ), genere una partición de los vértices V de modo de maximizar el número de aristas que cruzan de un lado al otro. Este problema se puede expresar como un programa cuadrático entero :

Maximizar de tal 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 abordar este tipo de problema:

1. Relajar el programa cuadrático entero en un SDP.
2. Resuelva el SDP (dentro de un error aditivo arbitrariamente pequeño ). ${\displaystyle \epsilon }$
3. Redondee la solución SDP para obtener una solución aproximada del 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 modo 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. 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 en qué lado del hiperplano se encuentran los vectores correspondientes. Un análisis sencillo muestra que este procedimiento logra una relació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 sea cortado, que es proporcional al ángulo entre los vectores en los puntos finales del borde sobre . Comparando esta probabilidad con , en expectativa la razón es siempre al menos 0.87856.) Suponiendo la conjetura de juegos únicos , se puede demostrar que esta razó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. Posteriormente, Prasad Raghavendra desarrolló un marco general para problemas de satisfacción de restricciones basado en la conjetura de juegos únicos . ^[4]

Otras aplicaciones

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 relación de aproximación de 0,87856. Las 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 no lineales y convexas. ^[5] También se utiliza ampliamente en física para restringir las teorías de campos conformes con el bootstrap conforme . ^[6]

Complejidad en tiempo de ejecución

El problema de factibilidad semidefinida (SDF) es el siguiente problema de decisión : dado un SDP, decidir si tiene al menos una solución factible. La complejidad exacta en tiempo de ejecución de este problema es desconocida (a fecha de 1997). Sin embargo, Ramana demostró lo siguiente: ^[2]

• En el modelo de la máquina de Turing , SDF está en NP solo 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 los 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 del elipsoide

El método del elipsoide es un método general para la programación convexa y se puede utilizar en particular para resolver SDP. En el contexto de los SDP, el método del elipsoide proporciona la siguiente garantía. ^{[1] : Teoría 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; por lo tanto, el SDP puede escribirse como: . Suponga que todos los coeficientes en el SDP son números racionales. Sea R un límite superior explícitamente dado 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 distancia de Frobenius a lo sumo ε desde X satisface la condición de factibilidad . Denote . 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 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 el 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 de última generación ^{[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 el cálculo, el almacenamiento y la factorización de una gran matriz hessiana y se adaptan a problemas mucho más grandes que los métodos de puntos interiores, con cierto sacrificio en la precisión. Un método de primer orden se implementa en el solucionador de cono divisorio (SCS). ^[9] Otro método de primer orden es el método de dirección alternada de multiplicadores (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 uniforme y lo resuelve mediante el método Spectral Bundle de optimización no uniforme. Este enfoque es muy eficiente para una clase especial de problemas SDP lineales.

Otros métodos de solución

Los algoritmos basados ​​en el método de Lagrangiano Aumentado (PENSDP) tienen un comportamiento similar al de los métodos de puntos interiores y pueden especializarse para algunos problemas de escala muy grande. Otros algoritmos utilizan información de bajo rango y reformulación del SDP como un problema de programación no lineal (SDPLR, ManiSDP). ^[11]

Métodos aproximados

También se han propuesto algoritmos que resuelven los 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 múltiples entradas y múltiples salidas (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 de 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 los 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 se pueden utilizar para

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

Véase también

• Problema de suma de raíz cuadrada : un caso especial de un problema de viabilidad de 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, consultado el 31 de diciembre de 2023
2. Ramana, Motakuri V. (1997). "Una teoría de dualidad exacta para 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". SIAM Review . 38 (1): 49–95. doi :10.1137/1038003. ISSN  0036-1445.
4. Raghavendra, Prasad (2008). "¿Algoritmos óptimos y resultados de inaproximabilidad para cada CSP?". Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación . págs. 245–254. doi :10.1145/1374376.1374414. ISBN 9781605580470.S2CID15075197  .​
5. Harrach, Bastian (2021), "Resolución de 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 semidefinidos para el bootstrap conforme". Journal of High Energy Physics . 2015 (6): 174. arXiv : 1502.02033 . Bibcode :2015JHEP...06..174S. doi :10.1007/JHEP06(2015)174. S2CID  256009551.
7. Jiang, Haotian; Kathuria, Tarun; 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. Número de identificación del sujeto  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 a través de división de operadores e incrustación autodual homogénea", Journal of Optimization Theory and Applications, 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 con dirección alternada para programación semidefinida". Mathematical Programming Computation 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 bajo rango", Mathematical Programming , 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 multiantena mediante relajación semidefinida aproximada". IEEE Transactions on Circuits and Systems I: Regular Papers . 63 (12): 2334–2346. arXiv : 1609.01797 . doi : 10.1109/TCSI.2016.2607198 . hdl :20.500.11850/448631. ISSN  1558-0806.
13. Hazan, Elad (2008). Laber, Eduardo Sany; Bornstein, Claudson; Nogueira, Loana Tito; Faria, Luerbio (eds.). "Soluciones aproximadas dispersas para programas semidefinidos". LATIN 2008: Informática teórica . Apuntes de clase en 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", Mathematical Programming Computation , 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. 49-95.
• Monique Laurent, Franz Rendl, "Programación semidefinida y programación entera", Informe PNA-R0210, CWI, Amsterdam, abril de 2002. optimización-online
• E. de Klerk, "Aspectos de la programación semidefinida: algoritmos de punto interior 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), Introducción a la SDP

Enlaces externos

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