Optimización matemática

Estudio de algoritmos matemáticos para problemas de optimización.

Gráfica de una superficie dada por z = f( x , y ) = −( x ² + y ²) + 4. El máximo global en ( x, y, z ) = (0, 0, 4) se indica con un azul punto.

Búsqueda mínima de Nelder-Mead de la función de Simionescu . Los vértices simplex están ordenados por sus valores, siendo 1 el valor más bajo (mejor). ${\displaystyle f(x)}$

La optimización matemática ( optimización alternativamente escrita ) o programación matemática es la selección del mejor elemento, con respecto a algún criterio, de algún conjunto de alternativas disponibles. ^[1] Generalmente se divide en dos subcampos: optimización discreta y optimización continua . Los problemas de optimización surgen en todas las disciplinas cuantitativas, desde la informática y la ingeniería ^[2] hasta la investigación de operaciones y la economía , y el desarrollo de métodos de solución ha sido de interés en las matemáticas durante siglos. ^[3]

En el enfoque más general, un problema de optimización consiste en maximizar o minimizar una función real eligiendo sistemáticamente valores de entrada dentro de un conjunto permitido y calculando el valor de la función. La generalización de la teoría y las técnicas de optimización a otras formulaciones constituye un área amplia de las matemáticas aplicadas . De manera más general, la optimización incluye encontrar los "mejores valores disponibles" de alguna función objetivo dado un dominio (o entrada) definido, incluida una variedad de diferentes tipos de funciones objetivo y diferentes tipos de dominios.

Problemas de optimización

Los problemas de optimización se pueden dividir en dos categorías, dependiendo de si las variables son continuas o discretas :

• Un problema de optimización con variables discretas se conoce como optimización discreta , en el que un objeto como un número entero , una permutación o un gráfico debe encontrarse a partir de un conjunto contable .
• Un problema con variables continuas se conoce como optimización continua , en el que se deben encontrar argumentos óptimos de un conjunto continuo. Pueden incluir problemas restringidos y problemas multimodales.

Un problema de optimización se puede representar de la siguiente manera:

Dado: una función f  : A → ${\displaystyle \mathbb {R} }$ de algún conjunto A a los números reales

Se busca: un elemento x ₀ ∈ A tal que f ( x ₀ ) ≤ f ( x ) para todo x ∈ A ("minimización") o tal que f ( x ₀ ) ≥ f ( x ) para todo x ∈ A (" maximización").

Esta formulación se denomina problema de optimización o problema de programación matemática (un término que no está directamente relacionado con la programación informática , pero que todavía se utiliza, por ejemplo, en programación lineal ; consulte la Historia a continuación). En este marco general se pueden modelar muchos problemas teóricos y del mundo real.

Dado que lo siguiente es válido

${\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),}$

basta con resolver sólo problemas de minimización. Sin embargo, también sería válida la perspectiva opuesta de considerar sólo problemas de maximización.

Los problemas formulados utilizando esta técnica en los campos de la física pueden referirse a la técnica como minimización de energía , hablando del valor de la función f como representativa de la energía del sistema que se está modelando . En el aprendizaje automático , siempre es necesario evaluar continuamente la calidad de un modelo de datos mediante el uso de una función de costo donde un mínimo implica un conjunto de parámetros posiblemente óptimos con un error óptimo (el más bajo).

Normalmente, A es algún subconjunto del espacio euclidiano , a menudo especificado por un conjunto de restricciones , igualdades o desigualdades que los miembros de A tienen que satisfacer. El dominio A de f se denomina espacio de búsqueda o conjunto de elección , mientras que los elementos de A se denominan soluciones candidatas o soluciones factibles . ${\displaystyle \mathbb {R} ^{n}}$

La función f se denomina, indistintamente, función objetivo , función de criterio , función de pérdida o función de costos (minimización), ^[4] función de utilidad o función de aptitud (maximización), o, en ciertos campos, función de energía o función energética . Una solución factible que minimiza (o maximiza, si ese es el objetivo) la función objetivo se llama solución óptima .

En matemáticas, los problemas de optimización convencionales suelen plantearse en términos de minimización.

Un mínimo local x * se define como un elemento para el cual existe algún δ > 0 tal que

${\displaystyle \forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,}$

la expresión f ( x *) ≤ f ( x ) se cumple;

es decir, en alguna región alrededor de x * todos los valores de la función son mayores o iguales que el valor en ese elemento. Los máximos locales se definen de manera similar.

Mientras que un mínimo local es al menos tan bueno como cualquier elemento cercano, un mínimo global es al menos tan bueno como cualquier elemento factible. Generalmente, a menos que la función objetivo sea convexa en un problema de minimización, puede haber varios mínimos locales. En un problema convexo , si hay un mínimo local que es interior (no en el borde del conjunto de elementos factibles), también es el mínimo global, pero un problema no convexo puede tener más de un mínimo local, no todos los cuales necesitan ser mínimos globales.

Un gran número de algoritmos propuestos para resolver problemas no convexos –incluyendo la mayoría de los solucionadores disponibles comercialmente– no son capaces de hacer una distinción entre soluciones localmente óptimas y soluciones globalmente óptimas, y tratarán a las primeras como soluciones reales al problema original. La optimización global es la rama de las matemáticas aplicadas y el análisis numérico que se ocupa del desarrollo de algoritmos deterministas que sean capaces de garantizar la convergencia en un tiempo finito a la solución óptima real de un problema no convexo.

Notación

Los problemas de optimización suelen expresarse con notación especial. Aquí hay unos ejemplos:

Valor mínimo y máximo de una función.

Considere la siguiente notación:

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

Esto denota el valor mínimo de la función objetivo x ² + 1 , al elegir x del conjunto de números reales . El valor mínimo en este caso es 1, que ocurre en x = 0 . ${\displaystyle \mathbb {R} }$

De manera similar, la notación

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

solicita el valor máximo de la función objetivo 2 x , donde x puede ser cualquier número real. En este caso, no existe tal máximo ya que la función objetivo es ilimitada, por lo que la respuesta es " infinito " o " indefinido ".

Argumentos de entrada óptimos

Considere la siguiente notación:

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

o equivalente

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

Esto representa el valor (o valores) del argumento x en el intervalo (−∞,−1] que minimiza (o minimiza) la función objetivo x ² + 1 (el valor mínimo real de esa función no es lo que pide el problema ).En este caso, la respuesta es x = −1 , ya que x = 0 es inviable, es decir, no pertenece al conjunto factible .

Similarmente,

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

o equivalente

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

representa el par (o pares) { x , y } que maximiza (o maximiza) el valor de la función objetivo x cos y , con la restricción adicional de que x se encuentra en el intervalo [−5,5] (nuevamente, el máximo real el valor de la expresión no importa). En este caso, las soluciones son los pares de la forma {5, 2 k π } y {−5, (2 k + 1) π } , donde k abarca todos los números enteros .

Los operadores arg min y arg max a veces también se escriben como argmin y argmax y representan el argumento del mínimo y el argumento del máximo .

Historia

Fermat y Lagrange encontraron fórmulas basadas en el cálculo para identificar óptimos, mientras que Newton y Gauss propusieron métodos iterativos para avanzar hacia un óptimo.

El término " programación lineal " para ciertos casos de optimización se debió a George B. Dantzig , aunque gran parte de la teoría había sido introducida por Leonid Kantorovich en 1939. ( La programación en este contexto no se refiere a la programación de computadoras , sino que proviene del uso de programa del ejército de los Estados Unidos para referirse a los cronogramas propuestos de entrenamiento y logística , que eran los problemas que Dantzig estudiaba en ese momento). Dantzig publicó el algoritmo Simplex en 1947, y también John von Neumann y otros investigadores trabajaron en los aspectos teóricos de la programación lineal. (como la teoría de la dualidad ) casi al mismo tiempo. ^[5]

Otros investigadores notables en optimización matemática incluyen los siguientes:

• Richard Bellman
• Dimitri Bertsekas
• Michel Bierlaire
• Esteban P. Boyd
• Roger Fletcher
• Martín Grötschel
• Ronald Howard
• Fritz Juan
• Narendra Karmarkar
• William Karush
• Leonid Khachiyan
• Bernardo Koopman
• Harold Kuhn
• László Lovász
• David Lüenberger
• Arkadi Nemirovski
• Yuri Nesterov
• Lev Pontryagin
• R. Tyrrell Rockafellar
• Naum Z. Shor
• Alberto Tucker

Subcampos principales

• La programación convexa estudia el caso en el que la función objetivo es convexa (minimización) o cóncava (maximización) y el conjunto de restricciones es convexo . Esto puede verse como un caso particular de programación no lineal o como una generalización de la programación cuadrática lineal o convexa.
  • La programación lineal (LP), un tipo de programación convexa, estudia el caso en el que la función objetivo f es lineal y las restricciones se especifican utilizando únicamente igualdades y desigualdades lineales. Un conjunto de restricciones de este tipo se denomina poliedro o politopo si está acotado .
  • La programación de conos de segundo orden (SOCP) es un programa convexo e incluye ciertos tipos de programas cuadráticos.
  • La programación semidefinida (SDP) es un subcampo de optimización convexa donde las variables subyacentes son matrices semidefinidas . Es una generalización de la programación cuadrática lineal y convexa.
  • La programación cónica es una forma general de programación convexa. LP, SOCP y SDP pueden verse como programas cónicos con el tipo de cono apropiado.
  • La programación geométrica es una técnica mediante la cual las restricciones objetivas y de desigualdad expresadas como posinomios y las restricciones de igualdad como monomios se pueden transformar en un programa convexo.
• La programación entera estudia programas lineales en los que algunas o todas las variables están obligadas a tomar valores enteros . Esto no es convexo y, en general, es mucho más difícil que la programación lineal normal.
• La programación cuadrática permite que la función objetivo tenga términos cuadráticos, mientras que el conjunto factible debe especificarse con igualdades y desigualdades lineales. Para formas específicas del término cuadrático, este es un tipo de programación convexa.
• La programación fraccionada estudia la optimización de ratios de dos funciones no lineales. La clase especial de programas fraccionarios cóncavos se puede transformar en un problema de optimización convexo.
• La programación no lineal estudia el caso general en el que la función objetivo, las restricciones o ambas contienen partes no lineales. Este puede ser o no un programa convexo. En general, si el programa es convexo afecta la dificultad de resolverlo.
• La programación estocástica estudia el caso en el que algunas de las restricciones o parámetros dependen de variables aleatorias .
• La optimización robusta es, al igual que la programación estocástica, un intento de capturar la incertidumbre en los datos subyacentes al problema de optimización. La optimización robusta tiene como objetivo encontrar soluciones que sean válidas bajo todas las realizaciones posibles de las incertidumbres definidas por un conjunto de incertidumbres.
• La optimización combinatoria se ocupa de problemas en los que el conjunto de soluciones factibles es discreto o puede reducirse a uno discreto .
• La optimización estocástica se utiliza con mediciones de funciones aleatorias (ruidosas) o entradas aleatorias en el proceso de búsqueda.
• La optimización de dimensión infinita estudia el caso en el que el conjunto de soluciones factibles es un subconjunto de un espacio de dimensión infinita , como un espacio de funciones.
• Las heurísticas y metaheurísticas hacen pocas o ninguna suposición sobre el problema que se está optimizando. Por lo general, la heurística no garantiza que sea necesario encontrar una solución óptima. Por otro lado, la heurística se utiliza para encontrar soluciones aproximadas a muchos problemas de optimización complicados.
• La satisfacción de restricciones estudia el caso en el que la función objetivo f es constante (esto se utiliza en inteligencia artificial , particularmente en razonamiento automatizado ).
  • La programación de restricciones es un paradigma de programación en el que las relaciones entre variables se establecen en forma de restricciones.
• La programación disyuntiva se utiliza cuando se debe satisfacer al menos una restricción, pero no todas. Es de particular utilidad en la programación.
• El mapeo espacial es un concepto para modelar y optimizar un sistema de ingeniería con una precisión de modelo de alta fidelidad (fina) que explota un modelo aproximado o sustituto adecuado y físicamente significativo .

En varios subcampos, las técnicas están diseñadas principalmente para la optimización en contextos dinámicos (es decir, la toma de decisiones a lo largo del tiempo):

• El cálculo de variaciones se ocupa de encontrar la mejor manera de lograr algún objetivo, como por ejemplo encontrar una superficie cuyo límite sea una curva específica, pero con la menor área posible.
• La teoría del control óptimo es una generalización del cálculo de variaciones que introduce políticas de control.
• La programación dinámica es el enfoque para resolver el problema de optimización estocástica con parámetros de modelo estocásticos, aleatorios y desconocidos. Se estudia el caso en el que la estrategia de optimización se basa en dividir el problema en subproblemas más pequeños. La ecuación que describe la relación entre estos subproblemas se llama ecuación de Bellman .
• La programación matemática con restricciones de equilibrio es aquella en la que las restricciones incluyen desigualdades variacionales o complementariedades .

Optimización multiobjetivo

Agregar más de un objetivo a un problema de optimización agrega complejidad. Por ejemplo, para optimizar un diseño estructural, se desearía un diseño que fuera a la vez ligero y rígido. Cuando dos objetivos entran en conflicto, se debe crear una compensación. Puede haber un diseño más ligero, un diseño más rígido y un número infinito de diseños que suponen algún compromiso entre peso y rigidez. El conjunto de diseños de compensación que mejoran un criterio a expensas de otro se conoce como conjunto de Pareto . La curva creada que traza el peso frente a la rigidez de los mejores diseños se conoce como frontera de Pareto .

Se considera que un diseño es "óptimo de Pareto" (equivalentemente, "eficiente de Pareto" o en el conjunto de Pareto) si no está dominado por ningún otro diseño: si es peor que otro diseño en algunos aspectos y no mejor en ningún aspecto, entonces está dominado y no es óptimo de Pareto.

La elección entre soluciones "óptimas de Pareto" para determinar la "solución favorita" se delega en quien toma las decisiones. En otras palabras, definir el problema como optimización multiobjetivo indica que falta algo de información: se dan objetivos deseables pero las combinaciones de ellos no se califican entre sí. En algunos casos, la información que falta puede obtenerse mediante sesiones interactivas con quien toma las decisiones.

Los problemas de optimización multiobjetivo se han generalizado aún más en problemas de optimización vectorial donde el ordenamiento (parcial) ya no viene dado por el orden de Pareto.

Optimización multimodal o global

Los problemas de optimización suelen ser multimodales; es decir, poseen múltiples buenas soluciones. Todas ellas podrían ser globalmente buenas (mismo valor de función de costo) o podría haber una combinación de soluciones globalmente buenas y localmente buenas. Obtener todas (o al menos algunas de) las múltiples soluciones es el objetivo de un optimizador multimodal.

Las técnicas de optimización clásicas debido a su enfoque iterativo no funcionan satisfactoriamente cuando se utilizan para obtener múltiples soluciones, ya que no se garantiza que se obtengan diferentes soluciones incluso con diferentes puntos de partida en múltiples ejecuciones del algoritmo.

Los enfoques comunes a los problemas de optimización global , donde pueden estar presentes múltiples extremos locales, incluyen algoritmos evolutivos , optimización bayesiana y recocido simulado .

Clasificación de puntos críticos y extremos.

problema de viabilidad

El problema de satisfacibilidad , también llamado problema de viabilidad , es simplemente el problema de encontrar cualquier solución factible sin tener en cuenta el valor objetivo. Esto puede considerarse como el caso especial de optimización matemática donde el valor objetivo es el mismo para cada solución y, por tanto, cualquier solución es óptima.

Muchos algoritmos de optimización deben comenzar desde un punto factible. Una forma de obtener ese punto es relajar las condiciones de viabilidad utilizando una variable de holgura ; con suficiente holgura, cualquier punto de partida es factible. Luego, minimice esa variable de holgura hasta que la holgura sea nula o negativa.

Existencia

El teorema del valor extremo de Karl Weierstrass establece que una función continua de valor real en un conjunto compacto alcanza su valor máximo y mínimo. De manera más general, una función semicontinua inferior en un conjunto compacto alcanza su mínimo; una función semicontinua superior en un conjunto compacto alcanza su punto o vista máximo.

Condiciones necesarias para la optimización.

Uno de los teoremas de Fermat establece que los óptimos de problemas no restringidos se encuentran en puntos estacionarios , donde la primera derivada o el gradiente de la función objetivo es cero (ver prueba de la primera derivada ). De manera más general, se pueden encontrar en puntos críticos , donde la primera derivada o gradiente de la función objetivo es cero o no está definida, o en el límite del conjunto de elección. Una ecuación (o conjunto de ecuaciones) que establece que las primeras derivadas son iguales a cero en un óptimo interior se denomina "condición de primer orden" o conjunto de condiciones de primer orden.

Los óptimos de problemas restringidos por igualdad se pueden encontrar mediante el método del multiplicador de Lagrange . Los óptimos de problemas con restricciones de igualdad y/o desigualdad se pueden encontrar utilizando las ' condiciones de Karush-Kuhn-Tucker '.

Condiciones suficientes para la optimización.

Si bien la prueba de la primera derivada identifica puntos que podrían ser extremos, esta prueba no distingue un punto que es mínimo de uno que es máximo o uno que no lo es. Cuando la función objetivo es dos veces diferenciable, estos casos se pueden distinguir comprobando la segunda derivada o la matriz de segundas derivadas (llamada matriz de Hesse ) en problemas no restringidos, o la matriz de segundas derivadas de la función objetivo y las restricciones llamada matriz bordeada. Hesse en problemas restringidos. Las condiciones que distinguen los máximos o mínimos de otros puntos estacionarios se denominan "condiciones de segundo orden" (ver " Prueba de la segunda derivada "). Si una solución candidata satisface las condiciones de primer orden, entonces la satisfacción de las condiciones de segundo orden también es suficiente para establecer al menos la optimización local.

Sensibilidad y continuidad de óptimos.

El teorema de la envolvente describe cómo cambia el valor de una solución óptima cuando cambia un parámetro subyacente . El proceso de calcular este cambio se llama estática comparativa .

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

Cálculo de optimización

Para problemas sin restricciones con funciones dos veces diferenciables, se pueden encontrar algunos puntos críticos encontrando los puntos donde el gradiente de la función objetivo es cero (es decir, los puntos estacionarios). De manera más general, un subgradiente cero certifica que se ha encontrado un mínimo local para problemas de minimización con funciones convexas y otras funciones de Lipschitz locales , que se encuentran en la minimización de la función de pérdida de la red neuronal. La estimación del impulso positivo-negativo permite evitar el mínimo local y converge al mínimo global de la función objetivo. ^[6]

Además, los puntos críticos se pueden clasificar utilizando la precisión de la matriz de Hesse : si la matriz de Hesse es positiva definida en un punto crítico, entonces el punto es un mínimo local; si la matriz de Hesse es definida negativa, entonces el punto es un máximo local; finalmente, si es indefinido, entonces el punto es una especie de punto de silla .

Los problemas restringidos a menudo se pueden transformar en problemas no restringidos con la ayuda de multiplicadores de Lagrange . La relajación lagrangiana también puede proporcionar soluciones aproximadas a problemas restringidos difíciles.

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

Convergencia global

De manera más general, si la función objetivo no es una función cuadrática, muchos métodos de optimización utilizan otros métodos para garantizar que alguna subsecuencia de iteraciones converja hacia una solución óptima. El primer método, y aún popular, para garantizar la convergencia se basa en búsquedas de líneas , que optimizan una función a lo largo de una dimensión. Un segundo método, cada vez más popular, para garantizar la convergencia utiliza regiones de confianza . Tanto las búsquedas de líneas como las regiones de confianza se utilizan en métodos modernos de optimización no diferenciable . Por lo general, un optimizador global es mucho más lento que los optimizadores locales avanzados (como BFGS ), por lo que a menudo se puede construir un optimizador global eficiente iniciando el optimizador local desde diferentes puntos de partida.

Técnicas de optimización computacional.

Para resolver problemas, los investigadores pueden utilizar algoritmos que terminan en un número finito de pasos, o métodos iterativos que convergen hacia una solución (en alguna clase específica de problemas), o heurísticas que pueden proporcionar soluciones aproximadas a algunos problemas (aunque sus iteraciones no necesariamente converger).

Algoritmos de optimización

• Algoritmo simplex de George Dantzig , diseñado para programación lineal
• Extensiones del algoritmo simplex, diseñadas para programación cuadrática y programación lineal-fraccional
• Variantes del algoritmo simplex que son especialmente adecuadas para la optimización de redes
• Algoritmos combinatorios
• Algoritmos de optimización cuántica

Métodos iterativos

Los métodos iterativos utilizados para resolver problemas de programación no lineal difieren según evalúen hessianas , gradientes o solo valores de funciones. Si bien la evaluación de Hessianas (H) y gradientes (G) mejora la tasa de convergencia, para funciones para las cuales estas cantidades existen y varían con suficiente fluidez, dichas evaluaciones aumentan la complejidad computacional (o el costo computacional) de cada iteración. En algunos casos, la complejidad computacional puede ser excesivamente alta.

Un criterio importante para los optimizadores es simplemente el número de evaluaciones de funciones requeridas, ya que esto a menudo ya supone un gran esfuerzo computacional, normalmente mucho más esfuerzo que dentro del propio optimizador, que tiene que operar principalmente sobre las N variables. Las derivadas proporcionan información detallada para dichos optimizadores, pero son aún más difíciles de calcular; por ejemplo, aproximar el gradiente requiere al menos N+1 evaluaciones de funciones. Para aproximaciones de las segundas derivadas (recogidas en la matriz de Hesse), el número de evaluaciones de funciones es del orden de N². El método de Newton requiere derivadas de segundo orden, por lo que para cada iteración, el número de llamadas a funciones es del orden de N², pero para un optimizador de gradiente puro más simple es solo N. Sin embargo, los optimizadores de gradiente generalmente necesitan más iteraciones que el algoritmo de Newton. Cuál es mejor con respecto al número de llamadas a funciones depende del problema en sí.

• Métodos que evalúan las arpilleras (o las arpilleras aproximadas, utilizando diferencias finitas ):
  • El método de Newton
  • Programación cuadrática secuencial : un método basado en Newton para problemas restringidos de pequeña y mediana escala . Algunas versiones pueden manejar problemas de grandes dimensiones.
  • Métodos de puntos interiores : esta es una gran clase de métodos para optimización restringida, algunos de los cuales utilizan solo información de (sub)gradiente y otros requieren la evaluación de Hessianas.
• Métodos que evalúan gradientes, o se aproximan a ellos de alguna manera (o incluso subgradientes):
  • Métodos de descenso de coordenadas : algoritmos que actualizan una única coordenada en cada iteración.
  • 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).
  • Descenso en gradiente (alternativamente, "descenso más pronunciado" o "ascenso más pronunciado"): un método (lento) de interés histórico y teórico, que ha tenido un interés renovado por encontrar soluciones aproximadas a problemas enormes.
  • Métodos de subgradiente : un método iterativo para grandes funciones de Lipschitz locales que utilizan gradientes generalizados . Siguiendo a Boris T. Polyak, los métodos de proyección de subgradiente son similares a los métodos de gradiente conjugado.
  • Método de descenso de paquetes: un método iterativo para problemas pequeños y medianos con funciones de Lipschitz localmente, particularmente para problemas de minimización convexa (similar a los métodos de gradiente conjugado).
  • Método elipsoide : Un método iterativo para pequeños problemas con funciones objetivo cuasiconvexas y de gran interés teórico, particularmente para establecer la complejidad temporal polinomial de algunos problemas de optimización combinatoria. Tiene similitudes con los métodos Quasi-Newton.
  • Método de gradiente condicional (Frank-Wolfe) para la minimización aproximada de problemas especialmente estructurados con restricciones lineales, especialmente con redes de tráfico. Para problemas generales sin restricciones, este método se reduce al método de gradiente, que se considera obsoleto (para casi todos los problemas).
  • Métodos cuasi-Newton : métodos iterativos para problemas medianos-grandes (por ejemplo, N<1000).
  • Método de aproximación estocástica de perturbación simultánea (SPSA) para optimización estocástica; utiliza una aproximación de gradiente aleatoria (eficiente).
• Métodos que evalúan solo valores de funciones: si un problema es continuamente diferenciable, entonces los gradientes se pueden aproximar usando diferencias finitas, en cuyo caso se puede usar un método basado en gradientes.
  • Métodos de interpolación
  • Métodos de búsqueda de patrones , que tienen mejores propiedades de convergencia que la heurística de Nelder-Mead (con simples) , que se enumera a continuación.
  • descenso del espejo

Heurística

Además de los algoritmos (de terminación finita) y los métodos iterativos (convergentes) , existen heurísticas . Una heurística es cualquier algoritmo que no garantiza (matemáticamente) que encontrará la solución, pero que, sin embargo, es útil en determinadas situaciones prácticas. Lista de algunas heurísticas conocidas:

• Evolución diferencial
• Relajación dinámica
• Algoritmos evolutivos
• Algoritmos genéticos
• Subida de colinas con reinicio aleatorio
• Algoritmo memético
• Heurística simplicial de Nelder-Mead : una heurística popular para la minimización aproximada (sin llamar a gradientes)
• Optimización de Enjambre de partículas
• Recocido simulado
• Túnel estocástico
• búsqueda tabú

Aplicaciones

Mecánica

Los problemas en la dinámica de cuerpos rígidos (en particular la dinámica de cuerpos rígidos articulados) a menudo requieren técnicas de programación matemática, ya que se puede ver la dinámica de cuerpos rígidos como un intento de resolver una ecuación diferencial ordinaria en una variedad de restricciones; ^[7] las restricciones son varias restricciones geométricas no lineales, como "estos dos puntos siempre deben coincidir", "esta superficie no debe penetrar ninguna otra" o "este punto siempre debe estar en algún lugar de esta curva". Además, el problema de calcular las fuerzas de contacto se puede resolver resolviendo un problema de complementariedad lineal , que también puede verse como un problema QP (programación cuadrática).

Muchos problemas de diseño también pueden expresarse como programas de optimización. Esta aplicación se llama optimización del diseño. Un subconjunto es la optimización de la ingeniería , y otro subconjunto reciente y creciente de este campo es la optimización del diseño multidisciplinario , que, si bien es útil en muchos problemas, se ha aplicado en particular a problemas de ingeniería aeroespacial .

Este enfoque puede aplicarse en cosmología y astrofísica. ^[8]

Economía y Finanzas

La economía está tan estrechamente vinculada a la optimización de los agentes que una definición influyente describe la economía como ciencia como el "estudio del comportamiento humano como una relación entre fines y medios escasos " con usos alternativos. ^[9] La teoría de optimización moderna incluye la teoría de optimización tradicional pero también se superpone con la teoría de juegos y el estudio de los equilibrios económicos . Los códigos del Journal of Economic Literature clasifican la programación matemática, las técnicas de optimización y los temas relacionados en JEL:C61-C63 .

En microeconomía, el problema de maximización de la utilidad y su problema dual , el problema de minimización del gasto , son problemas de optimización económica. En la medida en que se comportan de manera consistente, se supone que los consumidores maximizan su utilidad , mientras que generalmente se supone que las empresas maximizan sus ganancias . Además, a menudo se modela a los agentes como aversos al riesgo , por lo que prefieren evitarlo. Los precios de los activos también se modelan utilizando la teoría de la optimización, aunque las matemáticas subyacentes se basan en la optimización de procesos estocásticos en lugar de la optimización estática. La teoría del comercio internacional también utiliza la optimización para explicar los patrones comerciales entre naciones. La optimización de carteras es un ejemplo de optimización multiobjetivo en economía.

Desde la década de 1970, los economistas han modelado decisiones dinámicas a lo largo del tiempo utilizando la teoría del control . ^{[10] Por ejemplo,} los modelos de búsqueda dinámica se utilizan para estudiar el comportamiento del mercado laboral . ^[11] Una distinción crucial es entre modelos deterministas y estocásticos. ^[12] Los macroeconomistas construyen modelos dinámicos de equilibrio general estocástico (DSGE) que describen la dinámica de toda la economía como resultado de las decisiones optimizadoras interdependientes de trabajadores, consumidores, inversores y gobiernos. ^{[13] [14]}

Ingenieria Eléctrica

Algunas aplicaciones comunes de técnicas de optimización en ingeniería eléctrica incluyen el diseño de filtros activos , ^[15] reducción de campos parásitos en sistemas de almacenamiento de energía magnética superconductora, diseño de mapeo espacial de estructuras de microondas , ^[16] antenas de teléfonos, ^{[17] [18] [19]} electromagnetismo. -diseño basado en. La optimización del diseño validado electromagnéticamente de componentes y antenas de microondas ha hecho un uso extensivo de un modelo sustituto empírico o basado en la física apropiado y de metodologías de mapeo espacial desde el descubrimiento del mapeo espacial en 1993. ^{[20] [21]} Las técnicas de optimización también se utilizan en energía. análisis de flujo . ^[22]

Ingeniería civil

La optimización se ha utilizado ampliamente en la ingeniería civil. La gestión de la construcción y la ingeniería del transporte se encuentran entre las principales ramas de la ingeniería civil que dependen en gran medida de la optimización. Los problemas de ingeniería civil más comunes que se resuelven mediante la optimización son el corte y relleno de carreteras, el análisis del ciclo de vida de estructuras e infraestructuras, ^[23] nivelación de recursos , ^{[24] [25]} asignación de recursos hídricos , gestión del tráfico ^[26] y programación. mejoramiento.

La investigación de operaciones

Otro campo que utiliza ampliamente técnicas de optimización es la investigación de operaciones . ^[27] La ​​investigación de operaciones también utiliza modelos estocásticos y simulación para respaldar una mejor toma de decisiones. Cada vez más, la investigación de operaciones utiliza programación estocástica para modelar decisiones dinámicas que se adaptan a los eventos; Estos problemas se pueden resolver con optimización a gran escala y métodos de optimización estocástica .

Ingeniería de control

La optimización matemática se utiliza en gran parte del diseño de controladores modernos. Los controladores de alto nivel, como el control predictivo de modelos (MPC) o la optimización en tiempo real (RTO), emplean optimización matemática. Estos algoritmos se ejecutan en línea y determinan repetidamente valores para variables de decisión, como aperturas de estranguladores en una planta de proceso, resolviendo iterativamente un problema de optimización matemática que incluye restricciones y un modelo del sistema a controlar.

Geofísica

Las técnicas de optimización se utilizan habitualmente en problemas de estimación de parámetros geofísicos . Dado un conjunto de mediciones geofísicas, por ejemplo, registros sísmicos , es común resolver las propiedades físicas y las formas geométricas de las rocas y fluidos subyacentes. La mayoría de los problemas en geofísica son no lineales y se utilizan ampliamente métodos tanto deterministas como estocásticos.

Modelado molecular

Los métodos de optimización no lineal se utilizan ampliamente en el análisis conformacional .

Biología de sistemas computacionales

Las técnicas de optimización se utilizan en muchas facetas de la biología de sistemas computacionales, como la construcción de modelos, el diseño experimental óptimo, la ingeniería metabólica y la biología sintética. ^[28] Se ha aplicado programación lineal para calcular los rendimientos máximos posibles de productos de fermentación, ^[28] y para inferir redes reguladoras de genes a partir de múltiples conjuntos de datos de microarrays ^[29] , así como redes reguladoras transcripcionales a partir de datos de alto rendimiento. ^[30] La programación no lineal se ha utilizado para analizar el metabolismo energético ^[31] y se ha aplicado a la ingeniería metabólica y la estimación de parámetros en vías bioquímicas. ^[32]

Aprendizaje automático

Solucionadores

Ver también

• Curva braquistocrona
• Ajuste de curvas
• Optimización global determinista
• Programación de objetivos
• Publicaciones importantes en optimización.
• mínimos cuadrados
• Sociedad de Optimización Matemática (anteriormente Sociedad de Programación Matemática)
• Algoritmos de optimización matemática
• Software de optimización matemática
• Optimización de procesos
• Optimización basada en simulación
• Funciones de prueba para optimización.
• calculo variacional
• Problema de ruta de vehículos

Notas

1. "La naturaleza de la programación matemática Archivado el 5 de marzo de 2014 en Wayback Machine ", Glosario de programación matemática , INFORMS Computing Society.
2. Martíns, Joaquim RRA; Ning, Andrés (1 de octubre de 2021). Optimización del diseño de ingeniería. Prensa de la Universidad de Cambridge. ISBN 978-1108833417.
3. Du, DZ; Pardalos, PM; Wu, W. (2008). "Historia de la optimización". En Fluudas, C .; Pardalos, P. (eds.). Enciclopedia de optimización . Boston: Springer. págs. 1538-1542.
4. W. Erwin Diewert (2008). "funciones de costos", Diccionario de economía New Palgrave , contenidos de la segunda edición.
5. Bixby, Robert E. (2012). "Una breve historia del cálculo de programación lineal y de enteros mixtos" (PDF) . Documenta Matemática . 2012 : 107–121.
6. Abdulkadirov, R.; Lyakhov, P.; Bergerman, M.; Reznikov, D. (febrero de 2024). "Reconocimiento de imágenes de satélite mediante redes neuronales de conjunto y impulso positivo-negativo de gradiente de diferencia". Caos, solitones y fractales . 179 : 114432. doi : 10.1016/j.chaos.2023.114432.
7. Vereshchagin, AF (1989). "Modelado y control del movimiento de robots de manipulación". Revista soviética de ciencias informáticas y de sistemas . 27 (5): 29–38.
8. Haggag, S.; Desokey, F.; Ramadán, M. (2017). "Un modelo inflacionario cosmológico que utiliza un control óptimo". Gravitación y cosmología . 23 (3): 236–239. Código Bib : 2017GrCo...23..236H. doi :10.1134/S0202289317030069. ISSN  1995-0721. S2CID  125980981.
9. Lionel Robbins (1935, 2ª ed.) Ensayo sobre la naturaleza y la importancia de la ciencia económica , Macmillan, p. dieciséis.
10. Dorfman, Robert (1969). "Una interpretación económica de la teoría del control óptimo". Revista económica estadounidense . 59 (5): 817–831. JSTOR  1810679.
11. Sargent, Thomas J. (1987). "Buscar". Teoría Macroeconómica Dinámica . Prensa de la Universidad de Harvard. págs. 57–91. ISBN 9780674043084.
12. AG Malliaris (2008). "control óptimo estocástico", Diccionario de economía New Palgrave , segunda edición. Resumen Archivado el 18 de octubre de 2017 en Wayback Machine .
13. Rotemberg, Julio ; Woodford, Michael (1997). "Un marco econométrico basado en la optimización para la evaluación de la política monetaria" (PDF) . Anual de Macroeconomía del NBER . 12 : 297–346. doi : 10.2307/3585236 . JSTOR  3585236.
14. Del Diccionario de Economía New Palgrave (2008), segunda edición con enlaces abstractos:
    • "métodos de optimización numérica en economía" de Karl Schmedders
    • "programación convexa" de Lawrence E. Blume
    • "Modelo de equilibrio general Arrow-Debreu" de Juan Geanakoplos .
15. De, Bishnu Prasad; Kar, R.; Mandal, D.; Ghoshal, SP (27 de septiembre de 2014). "Selección óptima del valor de los componentes para el diseño de filtros activos analógicos mediante optimización de enjambre de partículas simplex". Revista Internacional de Aprendizaje Automático y Cibernética . 6 (4): 621–636. doi :10.1007/s13042-014-0299-0. ISSN  1868-8071. S2CID  13071135.
16. Koziel, Slawomir; Bandler, John W. (enero de 2008). "Mapeo espacial con múltiples modelos aproximados para la optimización de componentes de microondas". Cartas IEEE de componentes inalámbricos y de microondas . 18 (1): 1–3. CiteSeerX 10.1.1.147.5407 . doi :10.1109/LMWC.2007.911969. S2CID  11086218. 
17. Tu, Sheng; Cheng, Qingsha S.; Zhang, Yifan; Bandler, John W.; Nikolova, Natalia K. (julio de 2013). "Optimización del mapeo espacial de antenas de teléfonos que explotan modelos de cable fino". Transacciones IEEE sobre antenas y propagación . 61 (7): 3797–3807. Código Bib : 2013ITAP...61.3797T. doi : 10.1109/TAP.2013.2254695 .
18. N. Friedrich, “La cartografía espacial supera la optimización EM en el diseño de antenas de teléfonos móviles”, microondas & rf, 30 de agosto de 2013.
19. Cervantes-González, Juan C.; Rayas-Sánchez, José E.; López, Carlos A.; Camacho-Pérez, José R.; Brito-Brito, Zabdiel; Chávez-Hurtado, José L. (febrero de 2016). "Optimización del mapeo espacial de antenas de teléfonos considerando los efectos EM de los componentes de los teléfonos móviles y el cuerpo humano". Revista internacional de ingeniería asistida por computadora de RF y microondas . 26 (2): 121-128. doi : 10.1002/mmce.20945 . S2CID  110195165.
20. Bandler, JW; Biernacki, RM; Chen, Shao Hua; Grobelny, Pensilvania; Hemmers, RH (1994). "Técnica de mapeo espacial para optimización electromagnética". Transacciones IEEE sobre teoría y técnicas de microondas . 42 (12): 2536–2544. Código Bib : 1994ITMTT..42.2536B. doi : 10.1109/22.339794.
21. Bandler, JW; Biernacki, RM; Shao Hua Chen; Hemmers, RH; Madsen, K. (1995). "Optimización electromagnética aprovechando el mapeo espacial agresivo". Transacciones IEEE sobre teoría y técnicas de microondas . 43 (12): 2874–2882. Código bibliográfico : 1995ITMTT..43.2874B. doi : 10.1109/22.475649.
22. Relajación convexa del flujo de potencia óptimo: un tutorial. Simposio iREP 2013 sobre dinámica y control de sistemas de energía a granel. doi :10.1109/IREP.2013.6629391.
23. Piryonesi, Sayed Madeh; Tavakolan, Mehdi (9 de enero de 2017). "Un modelo de programación matemática para la resolución de problemas de optimización coste-seguridad (CSO) en el mantenimiento de estructuras". Revista KSCE de Ingeniería Civil . 21 (6): 2226–2234. doi :10.1007/s12205-017-0531-z. S2CID  113616284.
24. Hegazy, Tarek (junio de 1999). "Optimización de la asignación y nivelación de recursos mediante algoritmos genéticos". Revista de Ingeniería y Gestión de la Construcción . 125 (3): 167-175. doi :10.1061/(ASCE)0733-9364(1999)125:3(167).
25. Piryonesi, S. Madeh; Nasseri, Mehran; Ramezani, Abdollah (9 de julio de 2018). "Piryonesi, SM, Nasseri, M. y Ramezani, A. (2018). Nivelación de recursos en proyectos de construcción con división de actividades y restricciones de recursos: una optimización del recocido simulado". Revista Canadiense de Ingeniería Civil . 46 : 81–86. doi :10.1139/cjce-2017-0670. hdl : 1807/93364 . S2CID  116480238.
26. Herty, M.; Klar, A. (1 de enero de 2003). "Modelado, simulación y optimización de redes de flujo de tráfico". Revista SIAM de Computación Científica . 25 (3): 1066–1087. Código Bib : 2003SJSC...25.1066H. doi :10.1137/S106482750241459X. ISSN  1064-8275.
27. "Nueva fuerza en la escena política: los Seophonisten". Archivado desde el original el 18 de diciembre de 2014 . Consultado el 14 de septiembre de 2013 .
28. Papoutsakis, Eleftherios Terry (febrero de 1984). "Ecuaciones y cálculos para fermentaciones de bacterias del ácido butírico". Biotecnología y Bioingeniería . 26 (2): 174–187. doi : 10.1002/bit.260260210. ISSN  0006-3592. PMID  18551704. S2CID  25023799.
29. Wang, Yong; Joshi, Trupti; Zhang, Xiang-Sun; Xu, Dong; Chen, Luonan (24 de julio de 2006). "Inferir redes reguladoras de genes a partir de múltiples conjuntos de datos de microarrays". Bioinformática . 22 (19): 2413–2420. doi : 10.1093/bioinformática/btl396. ISSN  1460-2059. PMID  16864593.
30. Wang, Rui-Sheng; Wang, Yong; Zhang, Xiang-Sun; Chen, Luonan (22 de septiembre de 2007). "Inferir redes reguladoras transcripcionales a partir de datos de alto rendimiento". Bioinformática . 23 (22): 3056–3064. doi : 10.1093/bioinformática/btm465 . ISSN  1460-2059. PMID  17890736.
31. Vo, Thuy D.; Paul Lee, WN; Palsson, Bernhard O. (mayo de 2007). "El análisis de sistemas del metabolismo energético aclara el complejo de la cadena respiratoria afectado en el síndrome de Leigh". Genética molecular y metabolismo . 91 (1): 15-22. doi : 10.1016/j.ymgme.2007.01.012. ISSN  1096-7192. PMID  17336115.
32. Mendes, P .; Kell, D. (1998). "Optimización no lineal de vías bioquímicas: aplicaciones a la ingeniería metabólica y estimación de parámetros". Bioinformática . 14 (10): 869–883. doi : 10.1093/bioinformática/14.10.869 . ISSN  1367-4803. PMID  9927716.

Otras lecturas

• Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimizacion convexa. Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-83378-7.
• Gill, PE; Murray, W.; Wright, MH (1982). Optimización práctica . Londres: Academic Press. ISBN 0-12-283952-8.
• Lee, Jon (2004). Un primer curso en optimización combinatoria . Prensa de la Universidad de Cambridge. ISBN 0-521-01012-8.
• Nocedal, Jorge ; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín: Springer. ISBN 0-387-30303-0.

enlaces externos

• "Árbol de decisiones para software de optimización".Enlaces a códigos fuente de optimización
• "Optimización global".
• "EE364a: Optimización convexa I". Curso de la Universidad de Stanford .
• Varoquaux, Gaël. "Optimización matemática: búsqueda de mínimos de funciones".