Optimización (matemática)

Considere la siguiente notación:

${\displaystyle \min _{x\in \mathbb {R} }\;(x^{2}+1)}$

Esta denota el valor mínimo de la función objetivo ${\displaystyle x^{2}+1}$, cuando x se selecciona del conjunto de números reales ${\displaystyle \mathbb {R} }$. El valor mínimo en este caso es ${\displaystyle 1}$ y ocurre para ${\displaystyle x=0}$.

De modo similar, la notación

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

expresa el valor máximo de la función objetivo 2x, siendo x cualquier número real. En este caso, no existe tal máximo, luego no hay un valor óptimo acotado.

Considérese la siguiente expresión:

${\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}$

o de manera equivalente

${\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{sujeto a:}}\;x\in (-\infty ,-1].}$

Esta representa el valor (o valores) del argumento de x en el intervalo ${\displaystyle (-\infty ,-1]}$ que minimizan (o maximizan) la función objetivo x² + 1 (y no el valor mínimo que alcanza la función objetivo para dichos valores). En este caso, la respuesta es x = -1, puesto que x = 0 no es factible, es decir no pertenece al dominio del problema.

De modo similar,

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y),}$

que equivalente a

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{sujeto a:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

representa al par (o pares) (x,y) que minimizan (o maximizan) el valor de la función objetivo xcos(y), con la restricción añadida de que x se encuentra en el intervalo [-5,5] (nuevamente, el valor mínimo de la función no importa). En este caso, las soluciones son los pares de la forma (5, 2kπ) y (−5,(2k+1)π), donde k recorre todos los enteros.

Arg min y arg max a veces aparecen escritos como argmin y argmax, y quieren decir argumento del mínimo y argumento del máximo.

La solubilidad del problema, también llamada factibilidad del problema, es la cuestión de si existe alguna solución factible, al margen de su valor objetivo. Este puede ser considerado como el caso especial de la optimización matemática donde el valor objetivo es el mismo para toda solución, y así cualquier solución es óptima.

Muchos algoritmos de optimización necesitan comenzar a partir de un punto factible. Una vía para obtener tal punto es relajar las condiciones de factibilidad usando una variable de holgura; con suficiente holgura, cualquier punto de partida es factible. Entonces, se minimiza esa variable de holgura hasta que la holgura sea nula o negativa.

El teorema de Weierstrass afirma que una función real y continua en un conjunto compacto alcanza su valor máximo y mínimo. De forma más general, una función semi-continua inferior en un conjunto compacto alcanza su mínimo; una función semi-continua superior en un conjunto compacto alcanza su máximo.

Uno de los teoremas de Fermat asegura que los óptimos de los problemas irrestrictos son encontrados en los puntos estacionarios, donde la primera derivada de la función objetivo es cero (o su gradiente nulo). De forma más general, también pueden ser encontrados en los puntos críticos donde la primera derivada o el gradiente de la función objetivo no está definido, o en la frontera del conjunto de elección. Una ecuación (o conjunto de ecuaciones) indicando que la(s) primera(s) derivada(s) es(son) igual(es) a cero en un óptimo interior se llama una condición de primer orden o un conjunto de condiciones de primer orden.

Los óptimos de los problemas con restricciones de desigualdad son en cambio encontrados mediante el método de los multiplicadores de Lagrange. Este método computa un sistema de desigualdades llamado Condiciones de Karush–Kuhn–Tucker o condiciones de holguras complementarias, las cuales se usan entonces para calcular el óptimo.

Mientras la prueba de la primera derivada identifica los puntos que pueden ser extremos, esta prueba no distingue si un punto es mínimo, máximo, o ninguno de los dos. Cuando la función objetivo es dos veces diferenciable, estos casos pueden ser distinguidos estudiando la segunda derivada o la matriz de las segundas derivadas (llamada matriz Hessiana),en problemas irrestrictos, o la matriz de las segundas derivadas de la función objetivo y las restricciones llamada la matriz Hessiana orlada, en problemas restrictos.

Las condiciones que distinguen a los máximos, o mínimos, de otros puntos estacionarios son llamadas condiciones de segundo orden. Si un candidato a solución satisface las condiciones de primer orden y las condiciones de segundo orden también, es suficiente para establecer, al menos, optimalidad local.

El teorema de la envoltura describe como el valor de una solución óptima cambia cuando un parámetro subyacente cambia. El proceso que computa este cambio es llamado estática comparativa.

El teorema del máximo de Claude Berge (1963) describe la continuidad de una solución óptima como una función de parámetros subyacentes.

Para los problemas irrestrictos con funciones dos veces diferenciables, algunos puntos críticos pueden ser encontrados detectando los puntos donde el gradiente de la función objetivo es cero (es decir, los puntos estacionarios). De forma más general, un subgradiente cero certifica que un mínimo local ha sido encontrado para los problemas de minimización con funciones convexas u otras funciones de Lipschitz.

Además, los puntos críticos pueden ser clasificados usando la definitud de la matriz Hessiana: si es definida positiva en un punto crítico, entonces el punto es un mínimo local; si es definida negativa, entonces el punto es un máximo local; finalmente, si es indefinida, entonces el punto es algún tipo de punto de ensilladura.

Los problemas restrictos pueden con frecuencia ser transformados en problemas irrestrictos con ayuda de los multiplicadores de Lagrange. La relajación Lagrangiana puede también proveer soluciones aproximadas a difíciles problemas restrictos.

Cuando la función objetivo es convexa, entonces cualquier mínimo local será también un mínimo global. Existen técnicas numéricas eficientes para minimizar funciones convexas, por ejemplo los métodos de punto interior.

• Algoritmo Simplex de George Dantzig, diseñado para la programación lineal.
• Extensiones del algoritmo Simplex, diseñados para la programación cuadrática y para la programación lineal-fraccionaria.
• Variantes del algoritmo Simplex que son especialmente apropiadas para la optimización de redes.
• Algoritmos combinatorios.

Los métodos iterativos usados para resolver problemas de programación no lineal difieren según lo que evalúen: Hessianas, gradientes, o solamente valores de función. Mientras que evaluando Hessianas (H) y gradientes (G) mejora la velocidad de convergencia, tales evaluaciones aumentan la complejidad computacional (o costo computacional) de cada iteración. En algunos casos, la complejidad computacional puede ser excesivamente alta.

Un importante criterio para los optimizadores es justo el número de evaluaciones de funciones requerido, como este con frecuencia es de por sí un gran esfuerzo computacional, usualmente mucho más esfuerzo que el del optimizador en sí, ya que en su mayoría tiene que operar sobre N variables. Las derivadas proveen información detallada para los optimizadores, pero son aún más costosas de calcular, por ejemplo aproximando el gradiente toma al menos N+1 evaluaciones de funciones. Para la aproximación de las segundas derivadas (agrupadas en la matriz Hessiana) el número de evaluaciones de funciones es de orden N². El método de Newton requiere las derivadas de Segundo orden, por lo tanto por cada iteración el número de llamadas a función es de orden N², pero para el optimizador de un gradiente puro más simple es de orden N. Sin embargo, los optimizadores de gradiente necesitan usualmente más iteraciones que el algoritmo de Newton. Ser mejor con respecto al número de llamadas a funciones depende del problema en sí.

• Métodos que evalúan Hessianas (o aproximan Hessianas, usando diferencias finitas):
  • Método de Newton.
    • Programación secuencial cuadrática: un método de Newton basado en problemas restrictos de pequeña-mediana escala. Algunas versiones pueden manejar problemas de gran dimensión.
• Métodos que evalúan gradientes o aproximan gradientes usando diferencias finitas (o incluso subgradientes):
  • Métodos Quasi-Newton: métodos iterativos para problemas medianos-grandes (ejemplo N<1000).
  • Métodos de gradiente conjugado: métodos iterativos para problemas grandes. (En teoría, estos métodos terminan en un número finito de pasos con funciones objetivo cuadráticas, pero esta terminación finita no se observa en la práctica en computadoras de precisión finita.)
  • Métodos de punto interior: esta es una gran clase de métodos para la optimización restricta. Algunos métodos de punto interior usan solamente información del subgradiente, y otros requieren la evaluación de las Hessianas.
  • Descenso del gradiente (alternativamente, descenso pronunciado o ascenso pronunciado): un método lento de interés teórico e histórico, el cual ha sido renovado para encontrar soluciones aproximadas de problemas enormes.
  • Método del subgradiente: un método iterativo para grandes funciones de Lipschitz localmente usando gradientes generalizados.
• Métodos que evalúan solamente valores de funciones: si un problema es continuamente diferenciable, entonces los gradientes pueden ser aproximados usando diferencias finitas, en tal caso puede ser usado un método basado en gradiente.
  • Métodos de interpolación.
  • Métodos de búsqueda de patrones, los cuales tienen mejores propiedades de convergencia que la heurística de Nelder-Mead.

De modo general, si la función objetivo no es una función cuadrática, entonces muchos métodos de optimización usan otros métodos para garantizar que alguna subsecuencia de iteraciones converge a una solución óptima. El primer método popular que garantiza convergencia se apoya en búsquedas lineales, el cual optimiza una función en una dimensión. Un segundo y popularizado método para garantizar convergencia usa regiones de confianza. Ambos búsquedas lineales y regiones de confianza son usados en métodos modernos de optimización no diferenciable. Usualmente un optimizador global es mucho más lento que los optimizadores locales avanzados (por ejemplo BFGS), por lo tanto con frecuencia un optimizador global eficiente puede ser construido por el inicio del optimizador local de diferentes puntos de partida.

Además de los algoritmos (terminación finita) y los métodos iterativos (convergentes), existen heurísticas que pueden proveer soluciones aproximadas a algunos problemas de optimización:

• Evolución diferencial.
• Algoritmo de búsqueda diferencial.
• Relajación Dinámica.
• Algoritmos genéticos.
• Ascenso de montañas.
• Nelder-Mead: una heurística popular por aproximar la minimización (sin llamadas a gradientes).
• Optimización por enjambre de partículas.
• Optimización artificial de la colonia de abejas.