Optimización (matemática)

En las últimas décadas, el término optimización se ha vinculado al mundo de la informática.Sin embargo, es un concepto que también se utiliza en las matemáticas, en la gestión de procesos y la economía.Muchos problemas teóricos y del mundo real pueden ser modelados mediante este esquema general.Típicamente, A es algún subconjunto del espacio euclídeo Rn, con frecuencia delimitado por un conjunto de restricciones, igualdades o desigualdades que los elementos de A tienen que satisfacer.Generalmente, a menos que ambas, la función objetivo y la región factible sean convexas en un problema de minimización, puede haber varios mínimos locales, donde un mínimo local x* se define como un punto para el cual existe algún δ > 0, donde para todo x tal que la expresión es verdadera; es decir, en alguna región alrededor de x*, todos los valores de la función son mayores que o iguales al valor en ese punto.Los problemas de optimización se expresan a menudo con una notación especial.Considere la siguiente notación: Esta denota el valor mínimo de la función objetivoEn este caso, las soluciones son los pares de la forma (5, 2kπ) y (−5,(2k+1)π), donde k recorre todos los enteros.Pierre de Fermat y Joseph Louis Lagrange encontraron fórmulas basadas en el cálculo para identificar valores óptimos, mientras que Isaac Newton y Carl Friedrich Gauss propusieron métodos iterativos para aproximar el óptimo.Históricamente, el término programación lineal para referirse a ciertos problemas de optimización se debe a George B. Dantzig, aunque gran parte de la teoría había sido introducida por Leonid Kantorovich en 1939.Dantzig publicó el Algoritmo símplex en 1947 y John von Neumann desarrolló la teoría de la dualidad en el mismo año.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.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.La relajación Lagrangiana puede también proveer soluciones aproximadas a difíciles problemas restrictos.Existen técnicas numéricas eficientes para minimizar funciones convexas, por ejemplo los métodos de punto interior.Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).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.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.Ser mejor con respecto al número de llamadas a funciones depende del problema en sí.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.