Programación no lineal

En matemáticas , la programación no lineal ( PNL ) es el proceso de resolver un problema de optimización donde algunas de las restricciones no son igualdades lineales o la función objetivo no es una función lineal . Un problema de optimización es un problema de cálculo de los extremos (máximos, mínimos o puntos estacionarios) de una función objetivo sobre un conjunto de variables reales desconocidas y condicional a la satisfacción de un sistema de igualdades y desigualdades , colectivamente denominadas restricciones . Es el subcampo de la optimización matemática que se ocupa de problemas que no son lineales.

Definición y discusión

Sean n , m y p números enteros positivos. Sea X un subconjunto de R ⁿ (normalmente uno con restricciones de caja), sean f , g i _y h j _funciones de valor real en X para cada i en { 1 , ..., m } y cada j en { 1 , ..., p }, con al menos una de f , g _i y h _j no lineal.

Un problema de programación no lineal es un problema de optimización de la forma

{\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}

Dependiendo del conjunto de restricciones, existen varias posibilidades:

Un problema factible es aquel para el cual existe al menos un conjunto de valores para las variables de elección que satisfacen todas las restricciones.
Un problema inviable es aquel en el que ningún conjunto de valores para las variables de elección satisface todas las restricciones. Es decir, las restricciones son mutuamente contradictorias y no existe ninguna solución; el conjunto factible es el conjunto vacío .
Un problema ilimitado es un problema factible en el que la función objetivo puede ser mejor que cualquier valor finito dado. Por lo tanto, no existe una solución óptima, porque siempre hay una solución factible que da un valor de función objetivo mejor que cualquier solución propuesta dada.

La mayoría de las aplicaciones realistas presentan problemas factibles, mientras que los problemas inviables o ilimitados se consideran un fallo de un modelo subyacente. En algunos casos, los problemas inviables se manejan minimizando una suma de violaciones de viabilidad.

Algunos casos especiales de programación no lineal tienen métodos de solución especializados:

Si la función objetivo es cóncava (problema de maximización) o convexa (problema de minimización) y el conjunto de restricciones es convexo , entonces el programa se llama convexo y se pueden usar métodos generales de optimización convexa en la mayoría de los casos.
Si la función objetivo es cuadrática y las restricciones son lineales, se utilizan técnicas de programación cuadrática .
Si la función objetivo es una relación de una función cóncava y una convexa (en el caso de maximización) y las restricciones son convexas, entonces el problema puede transformarse en un problema de optimización convexa utilizando técnicas de programación fraccionaria .

Aplicabilidad

Un problema típico no convexo es el de optimizar los costos de transporte mediante la selección de un conjunto de métodos de transporte, uno o más de los cuales exhiben economías de escala , con diversas conectividades y restricciones de capacidad. Un ejemplo sería el transporte de productos derivados del petróleo dada una selección o combinación de oleoducto, vagón cisterna, camión cisterna, barcaza fluvial o buque cisterna costero. Debido al tamaño económico del lote, las funciones de costo pueden tener discontinuidades además de cambios suaves.

En la ciencia experimental, algunos análisis de datos simples (como ajustar un espectro con una suma de picos de ubicación y forma conocidas pero magnitud desconocida) se pueden realizar con métodos lineales, pero en general estos problemas también son no lineales. Por lo general, se tiene un modelo teórico del sistema en estudio con parámetros variables y un modelo del experimento o experimentos, que también pueden tener parámetros desconocidos. Se intenta encontrar el mejor ajuste numéricamente. En este caso, a menudo se desea una medida de la precisión del resultado, así como el mejor ajuste en sí.

Métodos para resolver un programa no lineal general

Métodos analíticos

En condiciones de diferenciabilidad y de restricción , las condiciones de Karush–Kuhn–Tucker (KKT) proporcionan las condiciones necesarias para que una solución sea óptima. Si algunas de las funciones no son diferenciables, existen versiones subdiferenciales de las condiciones de Karush–Kuhn–Tucker (KKT) . ^[1]

En condiciones de convexidad, las condiciones KKT son suficientes para un óptimo global . Sin convexidad, estas condiciones son suficientes solo para un óptimo local . En algunos casos, el número de óptimos locales es pequeño, y se pueden encontrar todos analíticamente y encontrar aquel para el cual el valor objetivo es menor. ^[2]

Métodos numéricos

En la mayoría de los casos realistas, es muy difícil resolver las condiciones KKT analíticamente, por lo que los problemas se resuelven utilizando métodos numéricos . Estos métodos son iterativos: comienzan con un punto inicial y luego avanzan hacia puntos que se supone que están más cerca del punto óptimo, utilizando alguna regla de actualización. Hay tres tipos de reglas de actualización: ^[2]^{: 5.1.2}

Rutinas de orden cero: utilizan solo los valores de la función objetivo y las funciones de restricción en el punto actual;
Rutinas de primer orden: utilizan también los valores de los gradientes de estas funciones;
Rutinas de segundo orden: utilizan también los valores de las hessianas de estas funciones.

Las rutinas de tercer orden (y superiores) son teóricamente posibles, pero no se utilizan en la práctica debido a la mayor carga computacional y al escaso beneficio teórico.

Rama y límite

Otro método implica el uso de técnicas de ramificación y acotación , donde el programa se divide en subclases para ser resueltas con aproximaciones convexas (problema de minimización) o lineales que forman un límite inferior en el costo total dentro de la subdivisión. Con divisiones subsiguientes, en algún punto se obtendrá una solución real cuyo costo es igual al mejor límite inferior obtenido para cualquiera de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no única. El algoritmo también puede detenerse antes, con la seguridad de que la mejor solución posible está dentro de una tolerancia desde el mejor punto encontrado; tales puntos se denominan ε-óptimos. La terminación en puntos ε-óptimos suele ser necesaria para asegurar una terminación finita. Esto es especialmente útil para problemas grandes y difíciles y problemas con costos o valores inciertos donde la incertidumbre se puede estimar con una estimación de confiabilidad adecuada.

Implementaciones

Existen numerosos solucionadores de programación no lineal, incluidos los de código abierto:

ALGLIB (C++, C#, Java, API de Python) implementa varios solucionadores de programación no lineal de primer orden y sin derivadas
NLopt (implementación de C/C++, con numerosas interfaces que incluyen Julia, Python, R, MATLAB/Octave), incluye varios solucionadores de programación no lineal
SciPy (el estándar de facto para Python científico) tiene el solucionador scipy.optimize, que incluye varios algoritmos de programación no lineal (de orden cero, primer orden y segundo orden).
IPOPT (implementación de C++, con numerosas interfaces que incluyen C, Fortran, Java, AMPL, R, Python, etc.) es un solucionador de métodos de punto interior (orden cero y, opcionalmente, derivadas de primer y segundo orden).

Ejemplos numéricos

Ejemplo bidimensional

Un problema simple (mostrado en el diagrama) se puede definir mediante las restricciones con una función objetivo a maximizar donde $x$ $= ($ $x$ $1$ $,$ $x$ $2$ $)$ . ${\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}$ $f(\mathbf {x} )=x_{1}+x_{2}$

Ejemplo tridimensional

Otro problema simple (ver diagrama) puede definirse mediante las restricciones con una función objetivo a maximizar donde $x$ $= ($ $x$ $1$ $,$ $x$ $2$ $,$ $x$ $3$ $)$ . ${\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}$ $f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}$

Véase también

Ajuste de curvas
Minimización por mínimos cuadrados
Programación lineal
nl (formato)
Mínimos cuadrados no lineales
Lista de software de optimización
Programación cuadrática con restricciones cuadráticas
Werner Fenchel , quien creó las bases para la programación no lineal

Referencias

^ Ruszczyński, Andrzej (2006). Optimización no lineal . Princeton, NJ: Princeton University Press . pp. xii+454. ISBN 978-0691119151.Sr. 2199043 .
^ ab Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .

Lectura adicional

Avriel, Mordecai (2003). Programación no lineal: análisis y métodos. Dover Publishing. ISBN 0-486-43227-0 .
Bazaraa, Mokhtar S. y Shetty, CM (1979). Programación no lineal. Teoría y algoritmos. John Wiley & Sons. ISBN 0-471-78610-1 .
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: aspectos teóricos y prácticos. Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. pp. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN. 3-540-35445-X.Señor 2265882 .
Luenberger, David G. ; Ye, Yinyu (2008). Programación lineal y no lineal . International Series in Operations Research & Management Science. Vol. 116 (tercera edición). Nueva York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2.Señor 2423726 .
Nocedal, Jorge y Wright, Stephen J. (1999). Optimización numérica. Springer. ISBN 0-387-98793-2 .
Jan Brinkhuis y Vladimir Tikhomirov, Optimización: perspectivas y aplicaciones , 2005, Princeton University Press

Enlaces externos

Glosario de programación matemática