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.