Programación no lineal

La programación no lineal optimiza un objetivo no lineal suave sujeto a restricciones no lineales, abarcando tanto la teoría de la optimalidad como los algoritmos que calculan soluciones.

Definition

Un programa no lineal minimiza un objetivo posiblemente no lineal sobre un conjunto factible definido por restricciones de igualdad y desigualdad no lineales; a diferencia de los problemas convexos, puede poseer múltiples óptimos locales, por lo que la mayoría de los métodos buscan puntos que satisfagan las condiciones de optimalidad necesarias.

Scope

Este tema cubre la minimización sin restricciones, las estrategias de búsqueda de línea y región de confianza, los métodos de gradiente, Newton y cuasi-Newton, las condiciones de optimalidad de primer y segundo orden, las condiciones de Karush-Kuhn-Tucker y las cualificaciones de restricción, y los métodos restringidos como la penalización, el lagrangiano aumentado y la programación cuadrática secuencial.

Core questions

• ¿Qué condiciones caracterizan un óptimo local de un problema no lineal restringido?
• ¿Cómo encuentran los métodos de descenso un punto estacionario de un problema sin restricciones?
• ¿Cómo se incorporan las restricciones en los algoritmos iterativos?
• ¿Cuándo se puede confiar en que un óptimo local calculado es global?

Key theories

Condiciones de optimalidad

Las condiciones de Karush-Kuhn-Tucker de primer orden y las condiciones de curvatura de segundo orden caracterizan los óptimos locales de problemas restringidos bajo cualificaciones de restricción adecuadas.

Métodos de descenso y tipo Newton

Los métodos de gradiente, Newton y cuasi-Newton generan direcciones de descenso y utilizan búsquedas de línea o regiones de confianza para converger a puntos estacionarios, con actualizaciones cuasi-Newton que aproximan la curvatura de forma económica.

Algoritmos de optimización restringida

Los métodos de penalización, lagrangiano aumentado y programación cuadrática secuencial convierten los problemas restringidos en secuencias de problemas más simples, manejando las restricciones de igualdad y desigualdad de manera sistemática.

Clinical relevance

La programación no lineal se utiliza donde los objetivos o las restricciones no son lineales, incluyendo el ajuste de modelos y el entrenamiento de modelos estadísticos y de aprendizaje automático, el diseño de ingeniería, el control óptimo y la estimación de parámetros en todas las ciencias.

History

Las condiciones de Karush-Kuhn-Tucker, establecidas en 1951 y anticipadas por Karush en 1939, generalizaron los multiplicadores de Lagrange a las restricciones de desigualdad y fundaron la teoría no lineal restringida. Los métodos cuasi-Newton, los lagrangianos aumentados y la programación cuadrática secuencial se desarrollaron a lo largo de la segunda mitad del siglo XX hasta convertirse en el conjunto de herramientas computacionales estándar.

Key figures

• Harold Kuhn
• Albert Tucker
• Isaac Newton
• Magnus Hestenes

Seminal works

• nocedal2006
• bertsekas1999

Frequently asked questions

¿Por qué la programación no lineal es más difícil que la programación lineal?

Los problemas no lineales pueden tener regiones factibles curvas y múltiples óptimos locales, por lo que generalmente no hay garantía de que una solución calculada sea globalmente la mejor, y los óptimos no tienen por qué encontrarse en los vértices. Los algoritmos deben basarse en información local como gradientes y curvatura.

¿Qué es un método cuasi-Newton?

Es un método iterativo que aproxima el paso de Newton sin calcular la matriz completa de la segunda derivada, construyendo información de curvatura a partir de gradientes sucesivos. Métodos como BFGS logran una convergencia rápida con un costo mucho menor que los pasos exactos de Newton.