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) está indicado por un punto azul.

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

La optimización matemática (también llamada optimización ) o programación matemática es la selección del mejor elemento, con respecto a ciertos criterios, de un conjunto de alternativas disponibles. ^{[1] [2]} 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 ^[3] 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. ^{[4] [5]}

En un 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 extensa de las matemáticas aplicadas . ^[6]

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 la que un objeto como un entero , una permutación o un gráfico debe encontrarse en un conjunto contable .
• Un problema con variables continuas se conoce como optimización continua , en el que se deben encontrar argumentos óptimos a partir 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").

Este tipo de formulación se denomina problema de optimización o problema de programación matemática (término que no está directamente relacionado con la programación informática , pero que todavía se utiliza, por ejemplo, en la programación lineal ; véase la historia a continuación). Muchos problemas reales y teóricos pueden modelarse en este marco general.

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 únicamente problemas de minimización. Sin embargo, la perspectiva opuesta de considerar únicamente problemas de maximización también sería válida.

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 , ^[7] hablando del valor de la función f como representante 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 un subconjunto del espacio euclidiano , a menudo especificado por un conjunto de restricciones , igualdades o desigualdades que los miembros de A deben 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 de diversas formas: función objetivo , función de criterio , función de pérdida , función de coste (minimización), ^[8] función de utilidad o función de aptitud (maximización) o, en ciertos campos, función de energía o funcional de energía . Una solución factible que minimiza (o maximiza) la función objetivo se denomina solución óptima .

En matemáticas, los problemas de optimización convencionales suelen formularse 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 cada 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 –incluida la mayoría de los solucionadores disponibles comercialmente– no son capaces de hacer una distinción entre soluciones óptimas locales y soluciones óptimas globales, y tratarán 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 capaces de garantizar la convergencia en tiempo finito a la solución óptima real de un problema no convexo.

Notación

Los problemas de optimización suelen expresarse con una notación especial. A continuación se ofrecen algunos 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}$

Pregunta por 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 valor máximo ya que la función objetivo no tiene límites, 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 equivalentemente

${\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 el 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 equivalentemente

${\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 añadida de que x se encuentra en el intervalo [−5,5] (de nuevo, el valor máximo real 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. ( Programación en este contexto no se refiere a la programación informática , sino que proviene del uso de programa por parte del ejército de los Estados Unidos para referirse a los cronogramas de entrenamiento y logística propuestos , 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 ) en la misma época. ^[9]

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

• Richard Bellman
• Dimitri Bertsekas
• Michel Bierlaire
• Stephen P. Boyd
• Roger Fletcher
• Martín Großtschel
• Ronald A. Howard
• Fritz Juan
• Narendra Karmarkar
• William Karush
• Leonid Khachiyan
• Bernard Koopman
• Harold Kuhn
• Laszló Lovász
• David Luenberger
• Arkadi Nemirovski
• Yuri Nesterov
• Lev Pontryagin
• R. Tyrrell Rockafellar
• Naum Z. Shor
• Albert 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 considerarse un caso particular de programación no lineal o una generalización de la programación cuadrática lineal o convexa.
  • La programación lineal (PL), 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 cono 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 la 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 considerarse 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 posinomiales y las restricciones de igualdad como monomios se pueden transformar en un programa convexo.
• La programación entera estudia los programas lineales en los que algunas o todas las variables están limitadas 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 fraccionaria estudia la optimización de las proporciones de dos funciones no lineales. La clase especial de programas fraccionarios cóncavos se puede transformar en un problema de optimización convexa.
• La programación no lineal estudia el caso general en el que la función objetivo o las restricciones, o ambas, contienen partes no lineales. Puede tratarse o no de un programa convexo. En general, el hecho de que el programa sea convexo o no 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 que subyacen al problema de optimización. La optimización robusta tiene como objetivo encontrar soluciones que sean válidas en todas las posibles realizaciones 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, las heurísticas no garantizan que se encuentre una solución óptima. Por otro lado, las heurísticas se utilizan para encontrar soluciones aproximadas para 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 el razonamiento automatizado ).
  • La programación con 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 especialmente útil en la planificación.
• El mapeo espacial es un concepto para modelar y optimizar un sistema de ingeniería para lograr una precisión de modelo de alta fidelidad (fina) explotando un modelo grueso o sustituto físicamente significativo y adecuado .

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

• El cálculo de variaciones es una rama de la optimización de dimensión infinita que se ocupa de encontrar la mejor manera de lograr algún objetivo, como 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. 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 denomina ecuación de Bellman .
• La programación matemática con restricciones de equilibrio es donde las restricciones incluyen desigualdades variacionales o complementariedades .

Optimización multiobjetivo

Añadir más de un objetivo a un problema de optimización añade complejidad. Por ejemplo, para optimizar un diseño estructural, se desearía un diseño que fuera ligero y rígido. Cuando dos objetivos entran en conflicto, se debe crear un equilibrio. Puede haber un diseño más ligero, un diseño más rígido y una cantidad infinita de diseños que sean un compromiso entre peso y rigidez. El conjunto de diseños con equilibrio que mejoran un criterio a expensas de otro se conoce como el conjunto de Pareto . La curva creada al representar gráficamente el peso frente a la rigidez de los mejores diseños se conoce como la frontera de Pareto .

Un diseño se considera "óptimo de Pareto" (equivalentemente, "eficiente en términos de Pareto" o perteneciente al 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 el responsable de la toma de decisiones. En otras palabras, definir el problema como una optimización multiobjetivo indica que falta cierta información: se dan los objetivos deseables, pero no se evalúan las combinaciones de ellos en relación con los demás. En algunos casos, la información faltante se puede obtener mediante sesiones interactivas con el responsable de la toma de 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 ordenamiento de Pareto.

Optimización multimodal o global

Los problemas de optimización suelen ser multimodales, es decir, poseen múltiples soluciones buenas. Todas ellas pueden ser globalmente buenas (el mismo valor de la función de costos) o puede 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 soluciones diferentes incluso con diferentes puntos de partida en múltiples ejecuciones del algoritmo.

Los enfoques comunes para 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 factibilidad , 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 lo tanto, cualquier solución es óptima.

Muchos algoritmos de optimización necesitan comenzar desde un punto factible. Una forma de obtener dicho punto es relajar las condiciones de factibilidad 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 de los valores extremos de Karl Weierstrass establece que una función continua de valor real en un conjunto compacto alcanza su valor máximo y mínimo. En términos más generales, 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 máximo o vista.

Condiciones necesarias para la optimalidad

Uno de los teoremas de Fermat establece que los óptimos de los problemas sin restricciones 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 el gradiente de la función objetivo es cero o no está definido, o en el límite del conjunto de elección. Una ecuación (o conjunto de ecuaciones) que establece que la(s) primera(s) derivada(s) es(son) igual(es) a cero en un óptimo interior se denomina "condición de primer orden" o un conjunto de condiciones de primer orden.

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

Condiciones suficientes para la optimalidad

Aunque la prueba de la primera derivada identifica puntos que podrían ser extremos, esta prueba no distingue un punto que es un mínimo de uno que es un máximo o uno que no es ninguno de los dos. 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 hessiana ) en problemas sin restricciones, o la matriz de segundas derivadas de la función objetivo y las restricciones llamada matriz hessiana acotada en problemas con restricciones. Las condiciones que distinguen los máximos o mínimos de otros puntos estacionarios se denominan "condiciones de segundo orden" (véase " 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 optimalidad local.

Sensibilidad y continuidad de los ó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 denomina 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 al encontrar 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 Lipschitz locales , que se encuentran en la minimización de la función de pérdida de la red neuronal. La estimación del momento positivo-negativo permite evitar el mínimo local y converge en el mínimo global de la función objetivo. ^[10]

Además, los puntos críticos se pueden clasificar utilizando la definición de la matriz hessiana : si la hessiana es definida positiva en un punto crítico, entonces el punto es un mínimo local; si la matriz hessiana 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 silla .

Los problemas restringidos pueden transformarse a menudo en problemas sin restricciones con la ayuda de los 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 puntos interiores .

Convergencia global

En términos más generales, 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 a una solución óptima. El primer método, que sigue siendo popular, para garantizar la convergencia se basa en búsquedas de línea , 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ínea 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 a 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 necesitan 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 para 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 hessianos , gradientes o solo valores de funciones. Si bien la evaluación de hessianos (H) y gradientes (G) mejora la tasa de convergencia, para funciones para las que estas cantidades existen y varían con suficiente suavidad, 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 es un gran esfuerzo computacional, generalmente mucho más esfuerzo que dentro del propio optimizador, que principalmente tiene que operar sobre las N variables. Las derivadas proporcionan información detallada para tales optimizadores, pero son aún más difíciles de calcular, por ejemplo, aproximar el gradiente requiere al menos N + 1 evaluaciones de función. Para las aproximaciones de las derivadas de segundo orden (recopiladas en la matriz de Hesse), el número de evaluaciones de función es del orden de N². El método de Newton requiere las derivadas de segundo orden, por lo que para cada iteración, el número de llamadas de función 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 de función depende del problema en sí.

• Métodos que evalúan hessianos (o hessianos aproximados, utilizando diferencias finitas ):
  • El método de Newton
  • Programación cuadrática secuencial : un método basado en Newton para problemas restringidos de escala pequeña y mediana . Algunas versiones pueden manejar problemas de grandes dimensiones.
  • Métodos de puntos interiores : se trata de una amplia clase de métodos para la optimización restringida, algunos de los cuales utilizan solo información de (sub)gradiente y otros requieren la evaluación de hessianos.
• Métodos que evalúan gradientes o aproximan gradientes de alguna manera (o incluso subgradientes):
  • Métodos de descenso de coordenadas : algoritmos que actualizan una sola 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 de 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 despertado un renovado interés por encontrar soluciones aproximadas a enormes problemas.
  • Métodos de subgradiente : un método iterativo para funciones de Lipschitz locales grandes 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 de tamaño pequeño a mediano con funciones de Lipschitz locales, particularmente para problemas de minimización convexa (similar a los métodos de gradiente conjugado).
  • Método del elipsoide : método iterativo para pequeños problemas con funciones objetivo cuasiconvexas y de gran interés teórico, en particular para establecer la complejidad temporal polinómica 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 en 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 aproximación de gradiente aleatorio (eficiente).
• Métodos que evalúan sólo valores de función: si un problema es continuamente diferenciable, entonces los gradientes se pueden aproximar utilizando diferencias finitas, en cuyo caso se puede utilizar 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 enumeran a continuación.
  • Descenso del espejo

Heurística

Además de los algoritmos (de terminación finita) y los métodos iterativos (convergentes) , existen las heurísticas . Una heurística es cualquier algoritmo que no garantiza (matemáticamente) que encuentre la solución, pero que, no obstante, es útil en ciertas 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 simple 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 dinámica de cuerpos rígidos (en particular, dinámica de cuerpos rígidos articulados) a menudo requieren técnicas de programación matemática, ya que puede ver la dinámica de cuerpos rígidos como un intento de resolver una ecuación diferencial ordinaria en una variedad de restricciones; ^[11] 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 de QP (programación cuadrática).

Muchos problemas de diseño también pueden expresarse como programas de optimización. Esta aplicación se denomina optimización del diseño. Un subconjunto es la optimización de ingeniería , y otro subconjunto reciente y en crecimiento 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 los problemas de ingeniería aeroespacial .

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

Economía y finanzas

La economía está tan estrechamente vinculada a la optimización de agentes que una definición influyente describe a la economía como ciencia como el "estudio del comportamiento humano como una relación entre fines y medios escasos " con usos alternativos. ^[13] 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 bajo 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 comporten de manera consistente, se supone que los consumidores maximizan su utilidad , mientras que las empresas suelen asumir que maximizan sus ganancias . Además, los agentes suelen modelarse como reacios 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 . ^[14] Por ejemplo, los modelos de búsqueda dinámica se utilizan para estudiar el comportamiento del mercado laboral . ^[15] Una distinción crucial es entre modelos deterministas y estocásticos. ^[16] Los macroeconomistas construyen modelos de equilibrio general dinámico y estocástico (DSGE) que describen la dinámica de toda la economía como resultado de las decisiones de optimización interdependientes de trabajadores, consumidores, inversores y gobiernos ^[17] . ^{[18] [19]}

Electrotecnia

Algunas aplicaciones comunes de las técnicas de optimización en ingeniería eléctrica incluyen el diseño de filtros activos , ^[20] la reducción de campos dispersos en sistemas superconductores de almacenamiento de energía magnética, el diseño de mapeo espacial de estructuras de microondas , ^[21] antenas de teléfonos móviles, ^{[22] [23] [24] diseño basado en electromagnetismo. La optimización del diseño validada 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 metodologías de mapeo espacial desde el descubrimiento del mapeo espacial en 1993. ^{[25] [26]} Las técnicas de optimización también se utilizan en el análisis de flujo de potencia . ^[27]

Ingeniería civil

La optimización se ha utilizado ampliamente en ingeniería civil. La gestión de la construcción y la ingeniería de 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, ^[28] la nivelación de recursos , ^{[29] [30]} la asignación de recursos hídricos , la gestión del tráfico ^[31] y la optimización de cronogramas.

Investigación de operaciones

Otro campo que utiliza ampliamente las técnicas de optimización es la investigación de operaciones . ^[32] 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 la programación estocástica para modelar decisiones dinámicas que se adaptan a los eventos; dichos 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 muchos diseños de controladores modernos. Los controladores de alto nivel, como el control predictivo de modelos (MPC) o la optimización en tiempo real (RTO), emplean la optimización matemática. Estos algoritmos se ejecutan en línea y determinan repetidamente valores para variables de decisión, como las aberturas de estrangulamiento en una planta de proceso, mediante la resolución iterativa de un problema de optimización matemática que incluye restricciones y un modelo del sistema que se va a controlar.

Geofísica

Las técnicas de optimización se utilizan con regularidad en los problemas de estimación de parámetros geofísicos . Dado un conjunto de mediciones geofísicas, por ejemplo, registros sísmicos , es habitual calcular las propiedades físicas y las formas geométricas de las rocas y los fluidos subyacentes. La mayoría de los problemas en geofísica son no lineales y se utilizan ampliamente tanto métodos 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. ^[33] La programación lineal se ha aplicado para calcular los rendimientos máximos posibles de los productos de fermentación, ^[33] y para inferir redes reguladoras de genes a partir de múltiples conjuntos de datos de microarrays ^[34], así como redes reguladoras transcripcionales a partir de datos de alto rendimiento. ^[35] La programación no lineal se ha utilizado para analizar el metabolismo energético ^[36] y se ha aplicado a la ingeniería metabólica y la estimación de parámetros en vías bioquímicas. ^[37]

Aprendizaje automático

Solucionadores

Véase también

• Curva braquistócrona
• 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
• Cálculo de variaciones
• Problema de ruta del vehículo

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. "Programación matemática: una descripción general" (PDF) . Consultado el 26 de abril de 2024 .
3. Martins, Joaquim RRA; Ning, Andrew (1 de octubre de 2021). Optimización del diseño de ingeniería. Cambridge University Press. ISBN 978-1108833417.
4. Du, DZ; Pardalos, PM; Wu, W. (2008). "Historia de la optimización". En Floudas, C. ; Pardalos, P. (eds.). Enciclopedia de optimización . Boston: Springer. págs. 1538–1542.
5. "Optimización matemática". Engati . Consultado el 24 de agosto de 2024 .
6. "Open Journal of Mathematical Optimization". ojmo.centre-mersenne.org . Consultado el 24 de agosto de 2024 .
7. Hartmann, Alejandro K; Rieger, Heiko (2002). Algoritmos de optimización en física . Citéseeer.
8. Erwin Diewert, W. (2017), "Funciones de costos", The New Palgrave Dictionary of Economics , Londres: Palgrave Macmillan UK, págs. 1–12, doi :10.1057/978-1-349-95121-5_659-2, ISBN 978-1-349-95121-5, consultado el 18 de agosto de 2024
9. Bixby, Robert E (2012). "Una breve historia de la computación con programación lineal y entera mixta" (PDF) . Documenta Mathematica . Serie Documenta Mathematica. 2012 : 107–121. doi :10.4171/dms/6/16. ISBN 978-3-936609-58-5.
10. Abdulkadirov, R.; Lyakhov, P.; Bergerman, M.; Reznikov, D. (febrero de 2024). "Reconocimiento de imágenes satelitales utilizando redes neuronales de conjunto y momento positivo-negativo de gradiente de diferencia". Chaos, Solitons & Fractals . 179 : 114432. Bibcode :2024CSF...17914432A. doi :10.1016/j.chaos.2023.114432.
11. Vereshchagin, AF (1989). "Modelado y control del movimiento de robots de manipulación". Revista soviética de informática y ciencias de sistemas . 27 (5): 29–38.
12. Haggag, S.; Desokey, F.; Ramadan, M. (2017). "Un modelo inflacionario cosmológico usando control óptimo". Gravitación y cosmología . 23 (3): 236–239. Bibcode :2017GrCo...23..236H. doi :10.1134/S0202289317030069. ISSN  1995-0721. S2CID  125980981.
13. Lionel Robbins (1935, 2.ª ed.) Un ensayo sobre la naturaleza y la importancia de la ciencia económica , Macmillan, pág. 16.
14. Dorfman, Robert (1969). "Una interpretación económica de la teoría del control óptimo". American Economic Review . 59 (5): 817–831. JSTOR  1810679.
15. Sargent, Thomas J. (1987). "Search". Teoría macroeconómica dinámica . Harvard University Press. págs. 57-91. ISBN 9780674043084.
16. AG Malliaris (2008). "control óptimo estocástico", The New Palgrave Dictionary of Economics , 2.ª edición. Resumen Archivado el 18 de octubre de 2017 en Wayback Machine .
17. Chaves Maza, Manuel; Fedriani, Eugenio M.; Ordaz Sanz, José Antonio (2018-07-01). "Factores relevantes para optimizar los servicios públicos de apoyo a los emprendedores y la tasa de supervivencia de las empresas". Innovar . 28 (69): 9–24. doi : 10.15446/innovar.v28n69.71693. ISSN  2248-6968.
18. Rotemberg, Julio ; Woodford, Michael (1997). "Un marco econométrico basado en la optimización para la evaluación de la política monetaria" (PDF) . NBER Macroeconomics Annual . 12 : 297–346. doi : 10.2307/3585236 . JSTOR  3585236.
19. Del Diccionario de Economía The New Palgrave (2008), 2.ª edición con enlaces a resúmenes:
    • "métodos de optimización numérica en economía" por Karl Schmedders
    • "programación convexa" por Lawrence E. Blume
    • "modelo Arrow-Debreu de equilibrio general" por John Geanakoplos .
20. 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.
21. Koziel, Slawomir; Bandler, John W. (enero de 2008). "Mapeo espacial con múltiples modelos aproximados para la optimización de componentes de microondas". IEEE Microwave and Wireless Components Letters . 18 (1): 1–3. CiteSeerX 10.1.1.147.5407 . doi :10.1109/LMWC.2007.911969. S2CID  11086218. 
22. 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 móviles que explotan modelos de cable delgado". IEEE Transactions on Antennas and Propagation . 61 (7): 3797–3807. Bibcode :2013ITAP...61.3797T. doi : 10.1109/TAP.2013.2254695 .
23. N. Friedrich, “El mapeo espacial supera la optimización EM en el diseño de antenas de teléfonos móviles”, Microwaves&Rf, 30 de agosto de 2013.
24. 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.
25. Bandler, JW; Biernacki, RM; Chen, Shao Hua; Grobelny, PA; Hemmers, RH (1994). "Técnica de mapeo espacial para optimización electromagnética". IEEE Transactions on Microwave Theory and Techniques . 42 (12): 2536–2544. Bibcode :1994ITMTT..42.2536B. doi :10.1109/22.339794.
26. Bandler, JW; Biernacki, RM; Shao Hua Chen; Hemmers, RH; Madsen, K. (1995). "Optimización electromagnética que explota el mapeo espacial agresivo". IEEE Transactions on Microwave Theory and Techniques . 43 (12): 2874–2882. Bibcode :1995ITMTT..43.2874B. doi :10.1109/22.475649.
27. Relajación convexa del flujo de potencia óptimo: un tutorial. Simposio iREP 2013 sobre dinámica y control de sistemas de potencia a granel. doi :10.1109/IREP.2013.6629391.
28. Piryonesi, Sayed Madeh; Tavakolan, Mehdi (9 de enero de 2017). "Un modelo de programación matemática para resolver problemas de optimización de costo-seguridad (CSO) en el mantenimiento de estructuras". KSCE Journal of Civil Engineering . 21 (6): 2226–2234. Bibcode :2017KSJCE..21.2226P. doi :10.1007/s12205-017-0531-z. S2CID  113616284.
29. Hegazy, Tarek (junio de 1999). "Optimización de la asignación y nivelación de recursos mediante algoritmos genéticos". Journal of Construction Engineering and Management . 125 (3): 167–175. doi :10.1061/(ASCE)0733-9364(1999)125:3(167).
30. 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 de recocido simulado". Revista Canadiense de Ingeniería Civil . 46 : 81–86. doi :10.1139/cjce-2017-0670. hdl : 1807/93364 . S2CID  116480238.
31. 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 informática científica . 25 (3): 1066–1087. Bibcode :2003SJSC...25.1066H. doi :10.1137/S106482750241459X. ISSN  1064-8275.
32. "Una nueva fuerza en la escena política: los seofonistas". Archivado desde el original el 18 de diciembre de 2014. Consultado el 14 de septiembre de 2013 .
33. Papoutsakis, Eleftherios Terry (febrero de 1984). "Ecuaciones y cálculos para fermentaciones de bacterias de ácido butírico". Biotecnología y bioingeniería . 26 (2): 174–187. doi :10.1002/bit.260260210. ISSN  0006-3592. PMID  18551704. S2CID  25023799.
34. 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/bioinformatics/btl396. ISSN  1460-2059. PMID  16864593.
35. 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/bioinformatics/btm465 . ISSN  1460-2059. PMID  17890736.
36. 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.
37. 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/bioinformatics/14.10.869 . ISSN  1367-4803. PMID  9927716.

Lectura adicional

• Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimización convexa. Cambridge: Cambridge University Press. 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 de optimización combinatoria . Cambridge University Press. 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".