## [Programación Semidefinida](/es/node/59740) Definición 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 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 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 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 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 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 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 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 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.