Programación Cuadrática (QP)

La programación cuadrática es la clase de problemas min (1/2) x^T Q x + c^T x s.a. Ax ≤ b, x ≥ 0 en forma canónica, donde Q ∈ R^(n×n) es simétrica, c ∈ R^n es el término lineal y las restricciones son lineales como en LP. El carácter del problema lo determina el signo de Q: (1) si Q es semidefinida positiva el QP es convexo, las condiciones KKT son necesarias y suficientes para la optimalidad y el problema se resuelve en tiempo polinómico mediante métodos de punto interior o de conjunto activo (Kozlov, Tarasov y Khachiyan 1979 demostraron la solubilidad polinómica del QP convexo); (2) si Q es indefinida el problema es no convexo y en general NP-difícil (Sahni 1974). La formulación canónica es el modelo media-varianza de Markowitz (1952): min (1/2) x^T Σ x s.a. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ matriz de covarianzas, μ vector de rendimientos esperados, R rendimiento objetivo; la frontera eficiente se traza variando R. Markowitz recibió el Premio Nobel de Economía en 1990 por este trabajo. La QP sustenta además el entrenamiento de máquinas de vectores soporte (Cortes y Vapnik 1995), el control predictivo basado en modelo (MPC), los mínimos cuadrados con restricciones, la programación cuadrática secuencial (SQP, bucle interior de la optimización no lineal, Wilson 1963 / Han 1976 / Powell 1978) y la optimización de trayectorias. Algoritmos: Wolfe (1959) y Beale (1959) desarrollaron los principios de conjunto activo; los métodos de punto interior predictor-corrector (lógica de Mehrotra 1992 extendida a QP) y los métodos de conjunto activo (primos del simplex LP) dominan los solucionadores prácticos.