Programación no lineal

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

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

${\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.

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.

• Optimización
• Ajuste de curvas
• Método de mínimos cuadrados
• Programación lineal

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