Programación no lineal

En matemáticas, la programación no lineal (PNL) es el proceso de resolución de un problema de optimización definido por un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.^[1]​^[2]​ Es un subcampo de la optimización matemática que se ocupa de problemas que no son lineales.

Un problema típico no convexo es el de optimizar los costes 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 conectividades y restricciones de capacidad. Un ejemplo sería el transporte de productos petrolíferos dada una selección o combinación de medios de transporte como oleoducto, camión cisterna, camión cisterna, barcaza fluvial o buque cisterna costero. Debido al tamaño del lote económico, los costes pueden presentar tanto discontinuidades como cambios suaves.

En la ciencia experimental, algunos análisis de datos sencillos (como el ajuste de un espectro con una suma de picos de ubicación y forma conocidas pero de magnitud desconocida) pueden realizarse con métodos lineales, pero en general estos problemas también son no lineales. Normalmente, se utiliza un modelo teórico del sistema estudiado con parámetros variables y también 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 obtener una medida de la precisión del resultado, así como el mejor ajuste en sí.

Un problema de programación no lineal puede enunciarse de una forma muy simple:

Sean n, m y p enteros positivos. Sea X un subconjunto de Rⁿ (generalmente con restricciones de caja), sean f, g_i, y h_j funciones reales 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:

${\displaystyle \max _{x\in X}f(x)}$ maximizar una función objetivo

o

${\displaystyle \min _{x\in X}f(x)}$ minimizar una función objetivo (de coste)

donde

${\displaystyle f:R^{n}\to R}$

${\displaystyle X\subseteq R^{n}.}$

Existen 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 de las variables de elección satisface todas las restricciones. Es decir, las restricciones son mutuamente contradictorias y no existe solución; el conjunto factible es el conjunto vacío.

Un problema factible es aquel para el que 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 la función objetivo puede ser mejor que cualquier valor finito dado. Por tanto, no existe una solución óptima, ya que siempre hay una solución factible que proporciona un valor de la función objetivo mejor que cualquier solución propuesta.

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, el programa se denomina 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 el cociente de una función cóncava y una convexa (en el caso de maximización) y las restricciones son convexas, el problema puede transformarse en un problema de optimización convexa mediante técnicas de programación fraccionaria. La programación fraccionaria es una generalización de la programación lineal-fraccionaria. La función objetivo en un programa fraccionario es el cociente de dos funciones que, en general, son no lineales. El cociente a optimizar suele describir algún tipo de eficiencia de un sistema. A su vez, la programación lineal-fraccionaria (PLF) es una generalización de la programación lineal (PL). Mientras que la función objetivo en un programa lineal es una función lineal, la función objetivo en un programa lineal-fraccionaria es el cociente de dos funciones lineales. Un programa lineal puede considerarse un caso especial de un programa lineal-fraccionaria en el que el denominador es la función constante 1.

El problema se remonta a la optimización de una función auxiliar sin restricciones secundarias (NB) utilizando los métodos que se describen a continuación. Para poder hacer uso de los métodos basados en gradientes, el área a buscar se divide en aquellas en las que la función objetivo es diferenciable. Si es posible, los subdominios deben ser convexos y también la función objetivo en ellos. Luego se puede calcular los extremos globales en las subáreas con los métodos enumerados en Optimización matemática y Optimización convexa y seleccionar el óptimo.^[3]​

La construcción de la función auxiliar se explica con un ejemplo: dos bolas en un canal intentan alcanzar el punto más bajo posible, pero no deben penetrar entre sí. La función objetivo es por lo tanto la energía potencial de las bolas y asume un mínimo en equilibrio. La restricción ${\displaystyle g(x,y)\leq 0}$ designaría la intersección de las esferas ${\displaystyle x}$ y ${\displaystyle y}$, donde con negativo se entiende por penetración una distancia positiva^[3]​.

1. Multiplicadores de Lagrange: Las NB se multiplican por factores reales, los multiplicadores de Lagrange, y se incorporan a la función objetivo de forma que si los multiplicadores de Lagrange son positivos, se penaliza la violación de la NB. La función auxiliar así obtenida se denomina función de Lagrange. Los multiplicadores de Lagrange se introducen en el problema como incógnitas y también deben determinarse. En el caso de las esferas, los multiplicadores de Lagrange no son más que las fuerzas de contacto que las esferas ejercen entre sí cuando se tocan, para que no se penetren.^[3]​
2. Funciones de barrera: Las NB se representan con funciones barrera que toman valores positivos a medida que se aproxima a la frontera del dominio de definición y crecen hasta el infinito en la frontera. Las funciones barrera se multiplican por los parámetros barrera ${\displaystyle r}$ y se incorporan a la función objetivo de forma que se penaliza la aproximación al límite y se evita así la violación de las NB. En la imagen esférica, las esferas tendrían un manto más o menos grueso, que se vuelve más y más rígido cuanto más se comprime al entrar en contacto. De este modo, se evita la violación de la NB a costa de penalizar incluso la aproximación al límite de alcance. El método se utiliza en Procedimiento de puntos interiores.^[3]​
3. Funciones de penalización: Las funciones de penalización se utilizan del mismo modo que las funciones de barrera. Las NB se representan con funciones de penalización que desaparecen en el rango admisible y son positivas cuando se viola el NL. Las funciones de penalización se multiplican por parámetros de penalización ${\displaystyle r}$ y se incorporan a la función objetivo de forma que se penaliza la violación del NL, de ahí su nombre. Aquí pueden violarse NB activas y debe comprobarse la admisibilidad de la solución. En la imagen de la esfera, la función de penalización corresponde a la penetración "real" (que desaparece cuando las esferas están positivamente espaciadas) y el parámetro de penalización corresponde a la rigidez de un muelle. El muelle intenta tirar de los puntos de penetración hacia la superficie. Cuanto más rígido sea el muelle, menor será la penetración.^[3]​
4. Método de Lagrange aumentado: Es una combinación de los multiplicadores de Lagrange y el método de penalización. El multiplicador de Lagrange se determina iterativamente en función de la violación de la NB.
5. Trivial (y por lo tanto a menudo no cubierto en las fuentes), pero aun así vale la pena mencionar y en el uso práctico, es que las NL activas se pueden utilizar para eliminar variables. Las variables se fijan en valores que hacen imposible la violación de la NL. En la imagen de la esfera, se acoplarían los puntos de contacto de las esferas (se igualarían sus coordenadas), de modo que ya no podría producirse una penetración (allí).^[3]​

Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.

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 se puede utilizar el método general de optimización convexa.

Existe una variedad de métodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programación lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes, con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimada en un grado de fiabilidad apropiado.

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.

Se utilizan algoritmos de solución tales como:

• El método de Newton,
• El método cuasi-Newton,
• El método del gradiente conjugado,
• La búsqueda lineal,
• Las regiones de confianza,
• El método Nelder-Mead,

entre otros

Un problema sencillo puede definirse por las restricciones:

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

con una función objetivo a ser maximizada

f(x) = x₁ + x₂

donde x = (x₁, x₂)

Otro problema simple se define por la restricciones:x₁² − x₂² + x₃² ≤ 2

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

con una función objetivo a ser maximizada

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

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

La programación no lineal (PNL) es una herramienta matemática poderosa utilizada para resolver problemas de optimización en los que la función objetivo o algunas de las restricciones son no lineales. Estos problemas surgen en diversos escenarios de la vida real en diferentes industrias, como por ejemplo:

Gestión de la cadena de suministro: en la optimización de una cadena de suministro, las empresas deben determinar la mejor forma de asignar recursos, programar la producción y distribuir productos en varias ubicaciones. A menudo, las funciones de costo relacionadas con el transporte, inventarios y procesos de producción son no lineales debido a factores como los rendimientos decrecientes en la producción o los costos de envío variables en función de la distancia. La PNL se utiliza para minimizar los costos totales mientras se cumplen las demandas y restricciones de producción.^[4]​

Optimización de carteras: los inversionistas buscan maximizar los rendimientos mientras minimizan el riesgo en su cartera de inversiones. La relación entre el riesgo de la cartera (a menudo medido como varianza) y su retorno esperado es no lineal.^[5]​ La PNL ayuda a determinar la combinación óptima de activos que cumpla con restricciones como el presupuesto y la tolerancia al riesgo, mientras busca el rendimiento más alto posible^[5]​.

Optimización de sistemas energéticos: en la generación de energía, especialmente la renovable, optimizar la combinación de generación es un problema no lineal. Por ejemplo, la producción de energía solar y eólica depende de condiciones ambientales, y el almacenamiento de energía tiene costos no lineales asociados con la eficiencia y la capacidad. La PNL puede utilizarse para determinar la mezcla de energía más rentable, satisfaciendo la demanda y minimizando el impacto ambiental.^[6]​

Diseño de procesos químicos: en la industria química, la PNL se utiliza para la optimización de procesos. La relación entre temperatura, presión y las tasas de reacción química suele ser no lineal.^[7]​ Los modelos de NLP ayudan a diseñar reactores, optimizar procesos de separación y reducir el desperdicio, minimizando el consumo de energía o maximizando la producción.^[8]​

Aprendizaje automático y redes neuronales: el entrenamiento de redes neuronales es inherentemente un problema de optimización no lineal.^[9]​ El objetivo es minimizar el error entre las salidas predichas y las reales. Los algoritmos de programación no lineal se utilizan para ajustar los pesos en una red de manera eficiente y lograr el mejor rendimiento.^[10]​

• Optimización
• Ajuste de curvas
• Método de mínimos cuadrados
• Programación lineal
• Werner Fenchel
• Teorema de Brunn-Minkowski
• Conjugada convexa
• Ramificación y poda (Ramificación y acotación)

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
• Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
• Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.

• Programación no lineal. Ejercicios resueltos (enlace roto disponible en este archivo). — PDF
• Programación no lineal con restricciones en desigualdad (enlace roto disponible en este archivo). — PDF
• Programación No Lineal
• Preguntas frecuentes de programación no lineal (en inglés)
• Glosario de programación matemática (en inglés)
• Nonlinear Programming Survey OR/MS Today

• AIMMS Optimization Modeling AIMMS — Incluye programación no lineal en soluciones sectoriales (prueba gratis, licencia de prueba disponible);
• AMPL solver software - Gratis para estudiantes
• Artelys Knitro optimizador especializado en programación no lineal (versión de prueba disponible)
• GAMS – Versión gratis disponible para estudiantes