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

editar

Motivación inicial

editar

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

 

donde el  , y los   son números reales y   es el producto punto de   y  .

Formulaciones equivalentes

editar

Decimos que una matriz   de   es positivo semidefinida si es la matriz de Gram de algunos vectores (i.e. si existen vectores   tal que   para todo  ). Si esto es el caso , lo denotamos con  . 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   al espacio de todas las matrices reales simétricas de  . El espacio está equipado con el producto interno (dónde   denota la traza) 

Podemos reescribir el programa matemático dado en la sección anterior equivalentemente de la siguiente manera

 

Dónde la entrada   en   está dada por   de la sección anterior, y   es una matriz simétrica de   cuya entrada   es igual a   de la sección anterior. Así, las matrices   y   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

 

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   como entrada diagonal (  para algunos  ). Para asegurar que  , las restricciones   pueden ser añadidas para todo  . Por otro ejemplo, nota que para cualquier matriz positivo semidefinida  , existe un conjunto de vectores   tal que la entrada  ,   de   es  , el producto escalar de   y  . 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   pueden ser recuperados en tiempo   (p. ej., por utilizando una factorización de Cholesky incompleta de X).

Teoría de dualidad

editar

Definiciones

editar

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

 

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

 

 

donde para cualesquiera dos matrices   y  ,   significa que  .

Dualidad débil

editar

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

 

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

editar

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   tal que  ,  ). Entonces hay un solución óptima   para (D-SDP) y

 

(ii) Supongamos que el problema dual (D-SDP) está acotado por arriba y es estrictamente factible (i.e.,   para algunos  ). Entonces hay una solución óptima   a (P-SDP) y la forma de igualdad de (i) se cumple.

Ejemplos

editar

Ejemplo 1

editar

Considera tres variables aleatorias  ,  , y  . Por definición, sus coeficientes de correlación   son válidos sí y sólo si

 

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   y  . El problema de determinar los valores más pequeños y más grandes que   puede tomar está dado por:

 

Pusimos   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

 

Resolver este PSD nos da los valores mínimos y máximos de  como   y  , respectivamente.

Ejemplo 2

editar

Considera el problema

Minimiza 
sujeto a que  

donde asumimos que   siempre que  .

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

Minimiza  
sujeto a 

En esta formulación, el objetivo es una función lineal en las variables  .

La primera restricción puede ser escrita como

 

donde la matriz   es la matriz cuadrada con valores en el diagonales iguales a los elementos del vector  .

La segunda restricción puede ser escrita como

 

Definiendo a   como sigue

 

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

 

(Boyd y Vandenberghe, 1996)

El programa semidefinido asociado con este problema es

Minimiza  
Sujeto a  

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

editar

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   Tal que cada  .

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  ).
  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

  tal que  , donde la maximización se raliza sobre los vectores   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  ; 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   entre los vectores que delimitan la arista, sobre  . Comparando esta probabilidad con  , 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.[1]

Algoritmos

editar

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

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.[2]

Métodos de punto interior

editar

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

editar

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).[3]​ Otro método de primer orden es el método de dirección alterna de multiplicadores (ADMM).[4]​ Este método requiere en cada paso la proyección hacia el cono de matrices semidefinidas.

Método de manojo

editar

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

editar

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).[5]

Métodos aproximados

editar

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.[6]​ 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

editar

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.[7]​ .

Referencias

editar
  1. Raghavendra, P. 2008. Optimal algorithms and inapproximability results for every CSP?. In Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17–20, 2008). STOC '08. ACM, New York, NY, 245-254.
  2. Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019), «Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs», Mathematical Programming Computation (en inglés) 11 (3): 503-586, ISSN 1867-2949, doi:10.1007/s12532-019-00164-4 .
  3. Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding", Journal of Optimization Theory and Applications, 2016, pp 1042--1068, https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.
  4. Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.
  5. Monteiro, Renato D. C.; Burer, Samuel (2003), «A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization», Mathematical Programming (en inglés) 95 (2): 329-357, ISSN 1436-4646, doi:10.1007/s10107-002-0352-8 .
  6. Castañeda, O.; Goldstein, T.; Studer, C. (December 2016). «Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation». IEEE Transactions on Circuits and Systems I: Regular Papers 63 (12): 2334-2346. ISSN 1558-0806. doi:10.1109/TCSI.2016.2607198. 
  7. Harrach, Bastian (2021), «Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming», Optimization Letters (en inglés), doi:10.1007/s11590-021-01802-4 .

 Otras lecturas

editar
  • 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

editar