Programación no lineal

En matemáticas, programación no lineal ()NLP) es el proceso de resolver un problema de optimización donde algunas de las limitaciones o la función objetiva no son lineales. Un problema de optimización es uno de los cálculos de los extremos (maxima, minima o puntos estacionarios) de una función objetiva sobre un conjunto de variables reales desconocidas y condicional a la satisfacción de un sistema de igualdades y desigualdades, restricciones colectivamente llamadas. Es el subcampo de optimización matemática que se ocupa de problemas que no son lineales.

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 limitaciones 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, se pueden realizar algunos análisis simples de datos (como la fijación de un espectro con una suma de picos de localización y forma conocida pero de magnitud desconocida) con métodos lineales, pero en general estos problemas también son no lineales. Típicamente, uno tiene un modelo teórico del sistema bajo estudio con parámetros variables en él y un modelo el experimento o experimentos, que también pueden tener parámetros desconocidos. Uno trata de encontrar un mejor ajuste numérico. En este caso uno a menudo quiere una medida de la precisión del resultado, así como el mejor ajuste en sí mismo.

Definición

Sean n, m y p números enteros positivos. Sea X un subconjunto de Rⁿ, sea f, g_i y h_j sean funciones de valor real en X para cada i en { 1, …, m} y cada j en {1, …, p}, con al menos uno de f, g_i y h_j ser no lineal.

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

${displaystyle {begin{aligned}{minimize } {f(x)\\\text{subject to }} {g_{i}(x)leq 0{text{ for each }iin{1,dotsigncm\\\p} {j}{=0}{inc} {c}}}} {cc}cccccccccccc}cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc$

Un problema de maximización no lineal se define de manera similar.

Posibles tipos de restricciones

Hay varias posibilidades para la naturaleza del conjunto de restricciones, también conocido como conjunto factible o región factible.

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 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 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.

Casos especiales

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

• Si la función objetiva es concave (problema de máximaización), o convex (problema de minimización) y el conjunto de restricciones es convex, entonces el programa se llama convex y los métodos generales de optimización convexa se pueden utilizar en la mayoría de los casos.

• Si la función objetiva es cuadrática y las limitaciones son técnicas lineales de programación cuadrática.
• Si la función objetiva es una relación de concave y una función convexa (en el caso de maximización) y las limitaciones son convexas, entonces el problema se puede transformar a un problema de optimización convexa utilizando técnicas de programación fraccional.

Métodos para resolver un programa no lineal general

Métodos analíticos

Bajo las 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).

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.

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:

• Las rutinas de orden cero sólo utilizan los valores de las funciones de función objetiva y limitación en el momento actual;
• rutinas de primer orden - utilizar también los valores de los gradientes de estas funciones;
• Las rutinas de segundo orden - utilizar también los valores de los hesianos de estas funciones.

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

Rama y atada

Otro método implica el uso de técnicas de rama y enlace, 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.

Ejemplos numéricos

Ejemplo bidimensional

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

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

con una función objetivo a maximizar

f()x) x₁ + x₂

donde x = (x₁, x₂).

Ejemplo tridimensional

Otro problema simple (ver diagrama) se puede definir mediante las restricciones

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

con una función objetiva a maximizar

f()x) x₁x₂ + x₂x₃

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