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

editar

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

editar

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

  maximizar una función objetivo

o

  minimizar una función objetivo (de coste)

donde

 
 

Posibles tipos de conjunto de restricciones

editar

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

editar

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   designaría la intersección de las esferas   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   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   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]

Métodos de resolución del problema

editar

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

editar

Ejemplo bidimensional

editar
 
La intersección de la línea con el espacio de restricciones representa la solución.

Un problema sencillo puede definirse por las restricciones:

x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2

con una función objetivo a ser maximizada

f(x) = x1 + x2

donde x = (x1, x2)

Ejemplo tridimensional

editar
 
La intersección de la superficie superior con el espacio de restricciones en el centro representa la solución.

Otro problema simple se define por la restricciones:x12x22 + x32 ≤ 2

x12 + x22 + x32 ≤ 10

con una función objetivo a ser maximizada

f(x) = x1x2 + x2x3

donde x = (x1, x2, x3)

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 portafolios: los inversionistas buscan maximizar los rendimientos mientras minimizan el riesgo en su portafolio. La relación entre el riesgo del portafolio (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]

Véase también

editar

Referencias

editar
  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. 
  3. a b c d e f R. Reinhardt, A. Hoffmann, T. Gerlach: Nichtlineare Optimierung. Springer, 2013, ISBN 978-3-8274-2948-3
  4. Sunil Chopra, Peter Meindl. Supply Chain Management: Strategy, Planning, and Operation (2019) Pearson 768 pag. ISBN: 978-0134731886
  5. a b William F. Sharpe. Portfolio Theory and Capital Markets (1970) McGraw-Hill 340 pag. ISBN: 978-0070237360
  6. M. S. Ebrahim, A. M. Massoud, A. M. Zoubir. Optimization of Power Generation and Distribution in Smart Grids (2017) Wiley 344 pag. ISBN: 978-1119377196
  7. Carlos A. Smith and Armando B. Sefero. Process Systems Analysis and Control (2005) McGraw-Hill Education 710 pag. ISBN: 978-0071112861
  8. Kenneth A. Solen and John N. Harb. Introduction to Chemical Engineering Computing (2012) Wiley 416 pag. ISBN: 978-0470038597
  9. Charu Aggarwal. Neural Networks and Deep Learning: A Textbook (2018) Springer 393 pag. ISBN: 978-3319944623
  10. Christopher M. Bishop. Pattern Recognition and Machine Learning (2006) Springer 738 pag. ISBN: 978-0387310732

Bibliografía

editar

Enlaces externos

editar

Software

editar