Una clase de problemas de optimización convexa en la que se optimiza un objetivo lineal sujeto a restricciones afines y a que una variable matriz simétrica sea semidefinida positiva.

Principio

Sustituir restricciones matriciales no convexas por el cono convexo de matrices semidefinidas positivas; expresar desigualdades matriciales lineales y objetivos lineales para obtener un problema resoluble por métodos de puntos interiores o métodos convexos de primer orden.

Demostración

Minimizar tr(CX) sujeto a tr(A_i X) = b_i para i = 1..m y X >= 0 (X semidefinida positiva); esta formulación capta relajaciones de problemas combinatorios y problemas de diseño en control y procesamiento de señales.

Aplicación incorrecta

Tratar relajaciones SDP como soluciones exactas sin comprobar condiciones de rango o integridad puede conducir a conclusiones demasiado optimistas; aplicar solucionadores SDP densos a problemas muy grandes y dispersos sin explotar la estructura resulta impracticable.

Consecuencia

Usada apropiadamente, la SDP proporciona relajaciones convexas ajustadas para muchos problemas difíciles, permite solvencia en tiempo polinómico en el sentido de métodos de punto interior y ofrece certificados de optimalidad o de inviabilidad vía soluciones duales.

Inversión

La inversión es restringir al programa lineal imponiendo matrices diagonales o suprimiendo las restricciones PSD, lo que simplifica el cálculo pero pierde expresividad para modelar correlaciones y formas cuadráticas.

Límite

Se aplica a problemas expresables mediante desigualdades matriciales lineales y variables matriciales simétricas PSD; excluye objetivos o restricciones intrínsecamente no convexas y casos en los que las restricciones enteras son obligatorias sin relajación.

Tensión semántica

Tensión entre la precisión de la solución (ajuste de la relajación SDP) y la viabilidad computacional (tamaño y explotación de la dispersidad), y entre solucionadores densos de punto interior (alta precisión) y métodos de primer orden (escalabilidad pero garantías de parada más débiles).

Síntesis

La programación semidefinida enmarca problemas con variables matriciales y restricciones PSD como programas convexos: objetivos lineales y desigualdades matriciales lineales definen una optimización de cono convexo que equilibra potencia de modelado y complejidad algorítmica.