Programación no lineal

Proceso de solución de algunos problemas de optimización.

En matemáticas , la programación no lineal ( PNL ) es el proceso de resolver un problema de optimización donde algunas de las restricciones o la función objetivo no son lineales . Un problema de optimización es aquel 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 condicionales a la satisfacción de un sistema de igualdades y desigualdades , denominados colectivamente 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 ⁿ (generalmente uno restringido por 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 }, siendo al menos uno 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

${\displaystyle {\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 para el cual 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 para el cual se puede hacer que la función objetivo sea mejor que cualquier valor finito dado. Por lo tanto, no existe una solución óptima, porque siempre hay una solución factible que proporciona un mejor valor de la función objetivo que cualquier solución propuesta dada.

Las aplicaciones más realistas presentan problemas factibles, y los problemas no factibles o ilimitados se consideran una falla 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 en la mayoría de los casos se pueden utilizar métodos generales de optimización convexa .
• 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 convexa (en el caso de maximización) y las restricciones son convexas, entonces el problema se puede transformar en un problema de optimización convexo 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 petrolíferos, dada una selección o combinación de oleoducto, camión cisterna, camión cisterna, barcaza fluvial o buque tanque costero. Debido al tamaño económico del lote, las funciones de costos pueden tener discontinuidades además de cambios fluidos.

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 de magnitud desconocida) se pueden realizar con métodos lineales, pero en general estos problemas también son no lineales. Por lo general, uno 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 numéricamente el mejor ajuste. En este caso, a menudo se desea medir 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

Bajo calificaciones de diferenciabilidad y restricciones , 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, se encuentran disponibles versiones subdiferenciales de las condiciones de Karush-Kuhn-Tucker (KKT) . ^[1]

Bajo convexidad, las condiciones KKT son suficientes para un óptimo global . Sin convexidad, estas condiciones son suficientes sólo 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 más pequeño. ^{[2] : Sección 5}

Métodos numéricos

En la mayoría de los casos realistas, es muy difícil resolver analíticamente las condiciones KKT, por lo que los problemas se resuelven utilizando métodos numéricos . Estos métodos son iterativos: comienzan con un punto inicial y luego proceden a 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: utilice sólo los valores de la función objetivo y las funciones de restricción en el punto actual;
• Rutinas de primer orden: utilice también los valores de los gradientes de estas funciones;
• Rutinas de segundo orden: utilice 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 atado

Otro método implica el uso de técnicas de rama y límite , donde el programa se divide en subclases que se resolverán 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 posteriores, en algún momento se obtendrá una solución real cuyo coste es igual al mejor cota inferior obtenida para cualquiera de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo también puede detenerse tempranamente, con la seguridad de que la mejor solución posible está dentro de una tolerancia desde el mejor punto encontrado; tales puntos se denominan ε-óptimo. Por lo general, es necesario terminar en puntos ε-óptimos para garantizar 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, incluido el código abierto:

• ALGLIB (C++, C#, Java, Python API) implementa varios solucionadores de programación no lineal de primer orden y sin derivados
• NLopt (implementación C/C++, con numerosas interfaces que incluyen Julia, Python, R, MATLAB/Octave), incluye varios solucionadores de programación no lineal
• SciPy (estándar de facto para Python científico) tiene el solucionador scipy.optimize, que incluye varios algoritmos de programación no lineal (orden cero, primer orden y segundo orden).

Ejemplos numéricos

ejemplo bidimensional

La región azul es la región factible . La tangencia de la recta con la región factible representa la solución. La línea es la mejor curva de nivel alcanzable (lugar con un valor dado de la función objetivo).

Un problema simple (que se muestra en el diagrama) puede definirse mediante las restricciones

$${\displaystyle {\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}}}$$

$${\displaystyle f(\mathbf {x} )=x_{1}+x_{2}}$$

x = ( x ₁ , x ₂ )

ejemplo tridimensional

La tangencia de la superficie superior con el espacio restringido en el centro representa la solución.

Otro problema simple (ver diagrama) puede definirse mediante las restricciones

$${\displaystyle {\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}}}$$

$${\displaystyle f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}}$$

x = ( x ₁ , x ₂ , x ₃ )

Ver también

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

Referencias

1. Ruszczyński, Andrzej (2006). Optimización no lineal . Princeton, Nueva Jersey: Princeton University Press . págs. xii+454. ISBN 978-0691119151. SEÑOR  2199043.
2. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .

Otras lecturas

• Avriel, Mardoqueo (2003). Programación no lineal: análisis y métodos. Publicación de Dover. ISBN 0-486-43227-0 . 
• Bazaraa, Mokhtar S. y Shetty, CM (1979). Programación no lineal. Teoría y algoritmos. John Wiley e hijos. 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. págs. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. SEÑOR  2265882.
• Luenberger, David G .; Sí, Yinyu (2008). Programación lineal y no lineal . Serie internacional en investigación de operaciones y ciencias de la gestión. vol. 116 (Tercera ed.). Nueva York: Springer. págs. xiv+546. ISBN 978-0-387-74502-2. SEÑOR  2423726.
• Nocedal, Jorge y Wright, Stephen J. (1999). Optimización numérica. Saltador. ISBN 0-387-98793-2 . 
• Jan Brinkhuis y Vladimir Tikhomirov, Optimización: conocimientos y aplicaciones , 2005, Princeton University Press

enlaces externos

• Glosario de programación matemática