Saltar al contenido
Volver a los resultados

Programación no lineal

Propuesto por
Jorge Nocedal & Stephen Wright
Año
2006
Tipo
Continuous mathematical optimization
Familia
Mathematical programming

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La programación no lineal (PNL) es una rama de la optimización matemática que se ocupa de problemas en los que la función objetivo o al menos una restricción es no lineal. Formalizada de manera integral por Jorge Nocedal y Stephen Wright en su texto seminal de 2006, la PNL abarca algoritmos basados en gradientes —incluyendo la programación cuadrática secuencial (SQP), los métodos de punto interior y los enfoques cuasi-Newton— para encontrar soluciones óptimas locales o globales a problemas de decisión continuos que surgen en ingeniería, economía y ciencias físicas.

La intuición detrás del método

Imagine descender por un paisaje montañoso cubierto de niebla, permaneciendo dentro de una zona cercada. No puede ver todo el terreno, por lo que siente la pendiente bajo sus pies (gradiente), ajusta la dirección de su paso para bajar y comprueba en cada movimiento que no ha cruzado la valla (restricciones). Si la valla se curva o las colinas se superponen, las trayectorias rectas simples no funcionarán; debe curvar su trayectoria. La programación no lineal formaliza exactamente este proceso, reemplazando la caminata intuitiva por reglas matemáticamente rigurosas de tamaño de paso y dirección.

Historia

Los fundamentos teóricos de la programación no lineal se remontan a las condiciones KKT derivadas por Karush (1939) y Kuhn y Tucker (1951). Los algoritmos prácticos se aceleraron durante las décadas de 1960-1980 con el desarrollo de métodos SQP, enfoques de Lagrangiano aumentado y actualizaciones cuasi-Newton, incluido BFGS (1970). La segunda edición de Numerical Optimization de Nocedal y Wright en 2006 se convirtió en una referencia definitiva, sintetizando la teoría de convergencia, los marcos de búsqueda de línea y región de confianza, y los métodos de punto interior en un tratamiento moderno coherente.

Cuándo usarlo

Utilice la programación no lineal cuando el objetivo o las restricciones no puedan linealizarse sin una pérdida material de precisión y las variables de decisión sean continuas. Los entornos típicos incluyen el diseño de ingeniería con restricciones de leyes físicas, la optimización de carteras con medidas de riesgo no lineales y la regresión con formas de modelo no lineales. Las suposiciones clave son que f y c son al menos dos veces continuamente diferenciables (para solucionadores basados en gradientes) y que se cumplen las cualificaciones de restricciones. Cuando las variables son de valor entero, se aplican extensiones de programación no lineal de enteros mixtos (MINLP). Para problemas convexos, los métodos de punto interior garantizan la optimalidad global; para problemas no convexos, solo existen garantías locales.

Limitaciones y consideraciones

  • Los problemas no convexos ofrecen solo garantías de optimalidad local; las soluciones globales requieren estrategias de búsqueda global adicionales.
  • Requiere que el objetivo y las restricciones sean suaves (al menos diferenciables); los problemas no suaves necesitan métodos subdiferenciales especializados.
  • El costo computacional crece sustancialmente con el tamaño del problema cuando se requiere la evaluación exacta de la Hessiana.
  • Las cualificaciones de restricciones pueden fallar (por ejemplo, en puntos factibles degenerados), lo que hace que las condiciones KKT pierdan su fundamento teórico.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Maneja una amplia clase de problemas del mundo real donde las aproximaciones lineales o cuadráticas son insuficientes.
  • Teoría algorítmica madura con garantías de convergencia bien estudiadas para instancias convexas.
  • Solucionadores eficientes basados en gradientes (SQP, punto interior) escalan a miles de variables en la práctica.
  • El marco Lagrangiano unificado acomoda de forma natural restricciones mixtas de igualdad y desigualdad.

Aplicaciones

  • Ingeniería estructural y aeroespacial: minimización de peso sujeta a restricciones de tensión y deflexión.
  • Gestión de carteras: maximización del rendimiento esperado sujeta a un presupuesto de varianza (riesgo) no lineal.
  • Diseño de procesos químicos: optimización del rendimiento del reactor sujeta a restricciones termodinámicas y de seguridad.
  • Aprendizaje automático: entrenamiento de redes neuronales y modelos de kernel a través de solucionadores de PNL sin restricciones o con restricciones.
  • Sistemas de energía: problemas de flujo de potencia óptimo en la despacho de redes eléctricas con restricciones físicas no lineales.

Cómo funciona

Cómo funciona

1

El analista define una función escalar objetivo f(x) para minimizar o maximizar sobre variables de decisión x en R^n, junto con restricciones de igualdad c_i(x) = 0 y restricciones de desigualdad c_j(x) >= 0. Identificar qué restricciones están activas en una solución candidata y si se cumplen las condiciones de regularidad (cualificaciones de restricciones) es fundamental en esta etapa y determina qué teoría de optimalidad se aplica.

Fórmula
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

Las condiciones de Karush-Kuhn-Tucker (KKT) proporcionan condiciones necesarias de primer orden para un óptimo local. Requieren la estacionariedad del Lagrangiano, la holgura complementaria para los multiplicadores de desigualdad (lambda_j c_j = 0), la factibilidad dual (lambda_j >= 0) y la factibilidad primal. Los algoritmos construyen iterativamente iteraciones que satisfacen estas condiciones de manera progresivamente más estricta, con condiciones de suficiencia de segundo orden que confirman que un punto estacionario es de hecho un mínimo local.

Fórmula
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

En cada iteración k, un algoritmo calcula una dirección de búsqueda p_k —típicamente a través de una aproximación cuasi-Newton B_k de la Hessiana (por ejemplo, BFGS) o un sistema exacto de segundas derivadas— y una longitud de paso alpha_k que satisface las condiciones de Wolfe o Armijo. Los métodos SQP resuelven un subproblema cuadrático para p_k, mientras que los métodos de punto interior añaden términos de barrera para manejar las restricciones de desigualdad y llevar las iteraciones hacia el interior factible.

Fórmula
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

La terminación ocurre cuando tanto la norma del gradiente del Lagrangiano como la violación máxima de la restricción caen por debajo de tolerancias preestablecidas (epsilon y delta). Debido a que la PNL es generalmente no convexa, los algoritmos pueden converger a óptimos locales; se recomiendan reinicios múltiples desde diferentes puntos de partida o estrategias de búsqueda global (ramificación y acotación, multi-arranque) cuando se requiere optimalidad global.

Fórmula
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

Errores comunes

  • Ignorar las cualificaciones de restricciones y aplicar ciegamente las condiciones KKT en puntos degenerados o infactibles conduce a soluciones espurias.
  • El uso de variables mal escaladas provoca aproximaciones de la Hessiana mal condicionadas y una convergencia lenta o fallida.
  • Aceptar el primer mínimo local encontrado sin reinicios múltiples en entornos no convexos puede omitir significativamente el óptimo global.
  • Las aproximaciones del gradiente por diferencias finitas introducen errores numéricos; se prefiere fuertemente la diferenciación analítica o automática.

Preguntas frecuentes

¿Es todo programa lineal también un programa no lineal?

Sí. La programación lineal es un caso especial de PNL donde tanto el objetivo como todas las restricciones son afines. Sin embargo, la PL admite los algoritmos símplex y de punto interior que explotan la linealidad y son mucho más eficientes que los solucionadores generales de PNL; usar un solucionador general de PNL para una PL es un desperdicio pero matemáticamente válido.

¿Cuándo puedo confiar en que un punto KKT es un mínimo global?

Cuando la PNL es convexa —lo que significa que f es convexa y el conjunto factible es un conjunto convexo— cualquier punto KKT es un mínimo global. Para problemas no convexos, esta garantía no se cumple, y un punto KKT es solo un mínimo local (bajo condiciones de suficiencia de segundo orden). De lo contrario, se necesitan métodos de optimización global como ramificación y acotación o relajaciones convexas.

¿Cuál es la diferencia entre los métodos SQP y de punto interior?

SQP resuelve iterativamente subproblemas de programación cuadrática que aproximan localmente la PNL y a menudo se prefiere para problemas pequeños a medianos con muchas restricciones activas. Los métodos de punto interior (barrera) permanecen estrictamente dentro de la región factible y tienden a escalar mejor para problemas grandes y dispersos. Ambos convergen superlinealmente bajo condiciones de regularidad apropiadas.

Métodos relacionados

Fuentes

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN: 978-0-387-30303-1
    Copiado.