Programación no lineal

Programación no lineal (PNL) es una rama de la programación matemática y la investigación de operaciones que se ocupa de problemas de optimización donde la función objetivo y/o al menos una de las restricciones son funciones no lineales de las variables de decisión.

La PNL es una generalización de la programación lineal y permite modelar una clase más amplia de sistemas y procesos del mundo real, donde las dependencias entre las variables no son estrictamente proporcionales (es decir, se describen mediante curvas en lugar de líneas rectas).

Objeto y propósito

La programación no lineal se utiliza para encontrar soluciones óptimas en situaciones donde:

• La dependencia del indicador objetivo (ganancias, costos, eficiencia, etc.) con respecto a los parámetros controlables no es lineal (por ejemplo, rendimientos decrecientes a escala, costos cuadráticos).
• Las restricciones sobre los recursos o los procesos tecnológicos se describen mediante relaciones no lineales (por ejemplo, reacciones químicas, leyes físicas, dependencias económicas).

Los problemas de PNL surgen en muchas áreas:

• Diseño de ingeniería (optimización de estructuras, procesos).
• Economía y finanzas (optimización de carteras considerando el riesgo, modelización de mercados).
• Tecnología química (optimización de los regímenes de los reactores).
• Aprendizaje automático (entrenamiento de redes neuronales, máquinas de vectores de soporte).
• Gestión de procesos de producción. Logística (considerando costos no lineales).

Formulación matemática del problema de PNL

El problema general de la programación no lineal se formula de la siguiente manera:

Se requiere encontrar un conjunto de valores de las variables de decisión que maximice o minimice una función objetivo no lineal. Al mismo tiempo, los valores de las variables deben satisfacer un sistema de restricciones, que pueden expresarse tanto en forma de desigualdades (por ejemplo, "la cantidad A debe ser menor o igual a B") como en forma de igualdades (por ejemplo, "la cantidad C debe ser exactamente igual a D"). Es importante que al menos una de las funciones que describen el objetivo o las restricciones sea no lineal. A menudo se añaden condiciones de no negatividad a las variables, es decir, el requisito de que sus valores sean mayores o iguales a cero.

El conjunto de todos los valores de las variables que satisfacen las restricciones constituye la región de soluciones factibles.

Diferencias con la programación lineal

La programación no lineal difiere significativamente de la programación lineal (PL):

• No linealidad: La función objetivo o las restricciones (o ambas) contienen dependencias no lineales.
• Propiedades de la región factible: La región de soluciones factibles en la PNL puede ser no convexa (a diferencia de la PL, donde siempre es un poliedro convexo).
• Propiedades del óptimo: La solución óptima en la PNL no se encuentra necesariamente en un vértice de la región factible; puede estar en la frontera o en el interior de la región. En la PNL pueden existir óptimos locales que no son globales.
• Complejidad de la solución: Los problemas de PNL son, por lo general, considerablemente más difíciles de resolver que los problemas de PL. No existe un algoritmo universal único, análogo al método simplex, para todos los problemas de PNL.

Principales dificultades y desafíos de la PNL

La resolución de problemas de programación no lineal conlleva una serie de dificultades:

• Presencia de extremos locales: La mayoría de los métodos de PNL solo garantizan encontrar un óptimo local (una solución que es la mejor en una vecindad determinada). La búsqueda del óptimo global (la mejor solución en toda la región factible) es una tarea compleja, especialmente para problemas no convexos.
• No convexidad: Si el problema no es convexo (la función objetivo o la región factible no son convexas), pueden existir múltiples óptimos locales, y los métodos de gradiente estándar pueden "quedar atrapados" en uno de ellos.
• Complejidad computacional: Los algoritmos para resolver problemas de PNL a menudo requieren recursos computacionales significativamente mayores en comparación con la PL.

Clases importantes de problemas de PNL

A pesar de la complejidad general, existen subclases importantes de problemas de PNL para las cuales se han desarrollado métodos de solución eficientes:

• Programación convexa: El problema de minimizar una función convexa sobre un conjunto de soluciones factibles convexo (o maximizar una función cóncava). Propiedad clave: cualquier mínimo local es también un mínimo global. Esto simplifica considerablemente la búsqueda de la solución óptima.
• Programación cuadrática: La función objetivo es cuadrática y todas las restricciones son lineales.
• Programación separable: La función objetivo y las restricciones pueden representarse como sumas de funciones, donde cada una depende de una sola variable.

Métodos de solución para problemas de PNL

Métodos de solución para problemas de programación no lineal (PNL)

I. Métodos de optimización sin restricciones:

• Métodos de gradiente (método del descenso más pronunciado, método del gradiente conjugado);
• Método de Newton y métodos cuasi-newtonianos (por ejemplo, BFGS);
• Métodos que utilizan la aproximación del Hessiano.

II. Métodos de optimización con restricciones:

• Métodos de transformación:
  • Método de las funciones de penalización (penalty methods);
  • Método de las funciones de barrera (barrier methods).
• Métodos de búsqueda directa de direcciones:
  • Método de las direcciones factibles.
• Métodos basados en condiciones de optimalidad:
  • Métodos de Karush-Kuhn-Tucker (condiciones KKT);
  • Método de los multiplicadores de Lagrange.
• Métodos iterativos:
  • Programación cuadrática secuencial (SQP);
  • Métodos de punto interior.

III. Métodos de optimización global:

• Métodos heurísticos y metaheurísticos:
  • Algoritmos genéticos;
  • Recocido simulado;
  • Búsqueda tabú (tabu search).
• Métodos deterministas:
  • Ramificación y acotación (branch and bound);
  • Algoritmos de optimización global para problemas con estructura especial.

Bibliografía

• Bazaraa, M. S., y Shetty, C. M. Programación no lineal. Teoría y algoritmos. — Moscú: Mir, 1982.
• Fiacco, A. V., y McCormick, G. P. Programación no lineal. Métodos de minimización secuencial sin restricciones. — Moscú: Mir, 1972.
• Himmelblau, D. M. Programación no lineal aplicada. — Moscú: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2.ª ed.)

Véase también

• Investigación de operaciones
• Optimización
• Programación lineal
• Programación convexa
• Función objetivo
• Restricciones
• Región de soluciones factibles