Inicio · Parte 12 — Optimización matemática y computacional

258 — Optimización cuadrática

avanzado clase 18 de 20 4 horas demostración quadratic_programming

Un programa cuadrático con Q definida positiva se resuelve por un solo sistema lineal.

Fórmulas

min (1/2)xᵀQx + cᵀx  sujeto a  Ax = b
sistema KKT: [[Q, Aᵀ], [A, 0]]·[x; λ] = [−c; b]
convexo si Q es semidefinida positiva

Desarrollo

La programación cuadrática es la clase de problemas con objetivo cuadrático y restricciones lineales. Es la siguiente en complejidad después de la lineal, y sigue siendo tratable: si Q es semidefinida positiva el problema es convexo y tiene solución global.

Con restricciones de igualdad, las condiciones KKT son lineales en las incógnitas, y el problema entero se reduce a resolver un único sistema que agrupa variables y multiplicadores. No hace falta iterar: se plantea el sistema aumentado y se resuelve con los métodos de la parte 11.

Con restricciones de desigualdad aparece la dificultad combinatoria de decidir qué restricciones están activas en el óptimo. Los algoritmos de conjunto activo prueban combinaciones sistemáticamente; los de punto interior siguen una trayectoria por el interior de la región factible y son los que mejor escalan.

Los programas cuadráticos aparecen en sitios importantes: la formulación dual de las SVM es exactamente uno, la optimización de carteras de Markowitz es otro, y el control predictivo por modelo resuelve uno en cada instante de muestreo. Reconocer que un problema es un QP es reconocer que se puede resolver de forma fiable y rápida.

Ejemplo trabajado

QP de dos variables con una restricción de igualdad.

minimizar  x² + y² − 2x − 5y
sujeto a   x + y = 3

Q = [[2, 0]      c = (−2, −5)      A = [1  1]     b = 3
     [0, 2]]

Q definida positiva → problema convexo                ✓

Sistema KKT:
  [[2  0  1]   [x]     [ 2]
   [0  2  1] · [y]  =  [ 5]
   [1  1  0]]  [λ]     [ 3]

solución: x = 1,25   y = 1,75   λ = −0,5

Comprobación: 1,25 + 1,75 = 3                         ✓
El óptimo sin restricción sería (1 ; 2,5), que suma 3,5:
la restricción sí aprieta.

Qué calcula el laboratorio

Programa cuadrático resuelto por su sistema KKT.

python classes/part-12-optimizacion-matematica-y-computacional/258-optimizacion-cuadratica/lab.py
compmath run 258

Salidas del laboratorio (11)

Q
c
A
b
Q_definida_positiva
sistema_KKT
solucion_x
multiplicador_lambda
restriccion_satisfecha
valor_objetivo
problema_convexo

Muestra de la ejecución real

{
  "Q": [
    [
      2.0,
      0.0
    ],
    [
      0.0,
      2.0
    ]
  ],
  "c": [
    -2.0,
    -5.0
  ],
  "A": [
    [
      1.0,
      1.0
    ]
  ],
  "b": [
    3.0
  ],
  "Q_definida_positiva": true,
  "sistema_KKT": [
    [
      2.0,
      0.0,
      1.0
    ],
    [
      0.0,
      2.0,
      1.0
    ],
    [
      1.0,
      1.0,
      0.0
    ]
  ]
}

Errores comunes

Aplicar la solución directa cuando hay restricciones de desigualdad.
No comprobar que Q es semidefinida positiva antes de suponer convexidad.
Formar el sistema KKT con los signos cambiados.

Dónde se usa

SVM, optimización de carteras, control predictivo por modelo, ajuste con restricciones y problemas de mínimos cuadrados restringidos.

Idea rectora de la parte

Momentum promedia gradientes; Adam además normaliza por su escala.

Error a evitar

Declarar convergencia por número de épocas y no por criterio numérico.

Conexión con IA

AdamW es el optimizador por defecto del entrenamiento moderno; entender su actualización explica el weight decay, el warmup y el gradient clipping.

Bibliografía de la clase

Nocedal, J.; Wright, S. Numerical Optimization, 2ª ed., Springer, 2006, cap. 16 — Optimización: el tema de esta clase · ISBN-13 9780387400655 verificado en International ISBN Agency (2026-08-19).
Boyd, S.; Vandenberghe, L. Convex Optimization, Cambridge, 2004, cap. 4 — Optimización: el tema de esta clase · ISBN-13 9780511804441 verificado en International ISBN Agency (2026-08-19).

Archivos de la clase

← 257 Condiciones KKT 259 Optimización evolutiva →