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.

Aplicabilidad

Un problema típico noconvexo 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 oleoducto, camión cisterna, camión cisterna, barcaza fluvial o buque cisterna costero. Debido al tamaño del lote económico, las funciones de costes pueden presentar discontinuidades además de 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 tiene un modelo teórico del sistema estudiado 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 obtener una medida de la precisión del resultado, así como el mejor ajuste en sí.

Formulación matemática del problema

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

\max _{x\in X}f(x)

maximizar una función objetivo

o

\min _{x\in X}f(x)

minimizar una función objetivo (de coste)

donde

f:R^{n}\to R

X\subseteq R^{n}.

Posibles tipos de conjunto de restricciones

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.

Procedimiento

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 $g(x,y)\leq 0$ designaría la intersección de las esferas $x$ y $y$ , donde con negativo se entiende por penetración una distancia positiva^[3].

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

Métodos de resolución del problema

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.

Ejemplos

Ejemplo bidimensional

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₂)

Ejemplo tridimensional

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₃)

Véase también

Referencias

↑ Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press
↑ Bertsekas, Dimitri P. Nonlinear Programing (en inglés). ISBN 1-886529-00-0.
↑ ^a ^b ^c ^d ^e ^f R. Reinhardt, A. Hoffmann, T. Gerlach: Nichtlineare Optimierung. Springer, 2013, ISBN 978-3-8274-2948-3

Bibliografía

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.

Enlaces externos

Software

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

Datos: Q769909

[1] Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press

[2] Bertsekas, Dimitri P. Nonlinear Programing (en inglés). ISBN 1-886529-00-0.

[UNO-3] ↑ ^a ^b ^c ^d ^e ^f R. Reinhardt, A. Hoffmann, T. Gerlach: Nichtlineare Optimierung. Springer, 2013, ISBN 978-3-8274-2948-3

[1]

[2]

[3]