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 no acotado 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 presentan economías de escala , con diversas conexiones 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 ellos analíticamente y encontrar aquel para el cual el valor objetivo es menor. ^[2]

Métodos numéricos

In most realistic cases, it is very hard to solve the KKT conditions analytically, and so the problems are solved using numerical methods. These methods are iterative: they start with an initial point, and then proceed to points that are supposed to be closer to the optimal point, using some update rule. There are three kinds of update rules:^[2]^: 5.1.2

Zero-order routines - use only the values of the objective function and constraint functions at the current point;
First-order routines - use also the values of the gradients of these functions;
Second-order routines - use also the values of the Hessians of these functions.

Third-order routines (and higher) are theoretically possible, but not used in practice, due to the higher computational load and little theoretical benefit.

Branch and bound

Another method involves the use of branch and bound techniques, where the program is divided into subclasses to be solved with convex (minimization problem) or linear approximations that form a lower bound on the overall cost within the subdivision. With subsequent divisions, at some point an actual solution will be obtained whose cost is equal to the best lower bound obtained for any of the approximate solutions. This solution is optimal, although possibly not unique. The algorithm may also be stopped early, with the assurance that the best possible solution is within a tolerance from the best point found; such points are called ε-optimal. Terminating to ε-optimal points is typically necessary to ensure finite termination. This is especially useful for large, difficult problems and problems with uncertain costs or values where the uncertainty can be estimated with an appropriate reliability estimation.

Implementations

There exist numerous nonlinear programming solvers, including open source:

ALGLIB (C++, C#, Java, Python API) implements several first-order and derivative-free nonlinear programming solvers
NLopt (C/C++ implementation, with numerous interfaces including Julia, Python, R, MATLAB/Octave), includes various nonlinear programming solvers
SciPy (de facto standard for scientific Python) has scipy.optimize solver, which includes several nonlinear programming algorithms (zero-order, first order and second order ones).
IPOPT (C++ implementation, with numerous interfaces including C, Fortran, Java, AMPL, R, Python, etc.) is an interior point method solver (zero-order, and optionally first order and second order derivatives).

Numerical Examples

2-dimensional example

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