Optimización (matemática)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

La optimización matemática o programación matemática es la selección de un mejor elemento, con respecto a algún criterio, de algún conjunto de alternativas disponibles. 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 hasta la investigación de operaciones y la economía, y el desarrollo de métodos de solución ha sido de interés para las matemáticas durante siglos.

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 una gran área 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 definido (o entrada), 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 se debe encontrar a partir de un conjunto contable.
Un problema con variables continuas se conoce como optimización continua, en el que se debe encontrar un valor óptimo de una función continua. 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 → ℝ de algún conjunto A a los números realesBuscado: 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").

Tal 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 de computadoras, pero que todavía se usa, por ejemplo, en la programación lineal; consulte la Historia a continuación). Muchos problemas teóricos y del mundo real se pueden modelar 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}),}$

es suficiente para resolver solo problemas de minimización. Sin embargo, la perspectiva opuesta de considerar solo problemas de maximización también sería válida.

Los problemas formulados usando 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 representando 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 (más bajo).

Por lo general, A es un 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.

La función f se denomina, de diversas formas, función objetivo, función de pérdida o función de costo (minimización), 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, si ese es el objetivo) la función objetivo se llama solución óptima.

En matemáticas, los problemas de optimización convencionales generalmente se expresan en términos de minimización.

Un mínimo local x * se define como un elemento para el que existe algún δ > 0 tal que ${displaystyle forall mathbf {x} in A;{text{where}};leftVert mathbf {x} -mathbf {x} ^{ast }rightVert 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.

Una gran cantidad de algoritmos propuestos para resolver problemas no convexos, incluida la mayoría de los solucionadores disponibles comercialmente, no son capaces de distinguir entre soluciones óptimas localmente y soluciones óptimas globalmente, 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 son 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 a menudo se expresan con una notación especial. Aquí hay unos ejemplos:

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

Considere la siguiente notación: ${displaystyle min _{xin mathbb {R} };left(x^{2}+1right)}$

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.

Del mismo modo, la notación $max _{xin mathbb {R} };2x$

pide 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: ${underset {xin (-infty,-1]}{operatorname {arg,min} }};x^{2}+1,$

o equivalente ${underset {x}{operatorname {arg,min} }};x^{2}+1,;{text{sujeto a:}};xin (-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 {xin [-5,5],;yin mathbb {R} }{operatorname {arg,max} }};xcos y,}$

o equivalente ${displaystyle {underset {x,;y}{operatorname {arg,max} }};xcos y,;{text{sujeto a:}};xin [-5,5],;yen 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 varía sobre todos los 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 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 debe 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 programas de entrenamiento y logística propuestos, que eran los problemas que estudiaba Dantzig en ese momento). Dantzig publicó el algoritmo Simplex en 1947, y John von Neumann desarrolló la teoría de la dualidad en el mismo año.

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

Richard Bellman
dimitri bertsekas
michel bierlaire
Roger Fletcher
ronald a. howard
Juan Fritz
Narendra Karmarkar
Guillermo Karush
leonid jachiyán
bernard koopman
Harold Kuhn
László Lovász
Arkadi Nemirovski
Yuri Nésterov
Lev Pontriagin
R. Tyrrell Rockafellar
Naum Z. Shor
Alberto Tucker

Subcampos principales

La programación convexa estudia el caso cuando 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 solo igualdades y desigualdades lineales. Tal conjunto de restricciones se llama 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 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 pueden transformarse en un programa convexo.
La programación entera estudia programas lineales en los que algunas o todas las variables están restringidas para tomar valores enteros. Esto no es convexo y, en general, mucho más difícil que la programación lineal regular.
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 proporciones 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 o las restricciones o ambas contienen partes no lineales. Esto puede o no ser 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, como 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 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 una discreta.
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 cuando el conjunto de soluciones factibles es un subconjunto de un espacio de dimensión infinita, como un espacio de funciones.
Las heurísticas y las metaheurísticas hacen pocas o ninguna suposición sobre el problema que se está optimizando. Por lo general, las heurísticas no garantizan que sea necesario encontrar 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 usa 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 el modelado y la optimización de un sistema de ingeniería con precisión de modelo de alta fidelidad (fino) que explota un modelo sustituto o aproximado físicamente significativo adecuado.

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):

Cálculo de variaciones 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 llama 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

Agregar más de un objetivo a un problema de optimización agrega complejidad. Por ejemplo, para optimizar un diseño estructural, uno desearía un diseño que sea 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 son un compromiso de peso y rigidez. El conjunto de diseños de compensación que mejoran un criterio a expensas de otro se conoce como el conjunto de Pareto. La curva creada al graficar el peso contra la rigidez de los mejores diseños se conoce como la frontera de Pareto.

Se considera que un diseño es "óptimo de Pareto" (equivalentemente, "eficiente en términos 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 es mejor en ningún aspecto, entonces es dominado y no es óptimo de Pareto.

La elección entre las soluciones "óptimas de Pareto" para determinar la "solución favorita" se delega al tomador de decisiones. En otras palabras, definir el problema como una optimización multiobjetivo indica que falta cierta información: se dan objetivos deseables pero las combinaciones de ellos no se clasifican entre sí. En algunos casos, la información que falta puede derivarse de sesiones interactivas con el tomador 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 está dado por el ordenamiento de Pareto.

Optimización multimodal o global

Los problemas de optimización suelen ser multimodales; es decir, poseen múltiples buenas soluciones. Todos podrían ser globalmente buenos (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 obtendrán 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 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 en el que el valor objetivo es el mismo para todas las soluciones y, por lo tanto, cualquier solución es óptima.

Muchos algoritmos de optimización necesitan comenzar desde un punto factible. Una forma de obtener tal 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 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. Más generalmente, una función semicontinua inferior en un conjunto compacto alcanza su mínimo; una función semicontinua superior sobre 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 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 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 la(s) primera(s) derivada(s) es(n) igual(es) a cero en un óptimo interior se denomina "condición de primer orden" o conjunto de condiciones de primer orden.

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

Condiciones suficientes para la optimalidad

Mientras que 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 lo es. Cuando la función objetivo es dos veces diferenciable, estos casos se pueden distinguir verificando 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 bordeada. Hessian en problemas restringidos. Las condiciones que distinguen 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,

Sensibilidad y continuidad de optima

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 diferenciables dos veces, 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). Más generalmente, un subgradiente cero certifica que se ha encontrado un mínimo local para problemas de minimización con funciones convexas y otras funciones locales de Lipschitz.

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 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 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, cualquier mínimo local será también un mínimo global. Existen técnicas numéricas eficientes para minimizar las funciones convexas, como los métodos de punto interior.

Convergencia mundial

Más generalmente, si la función objetivo no es una función cuadrática, entonces muchos métodos de optimización usan otros métodos para asegurar que alguna subsecuencia de iteraciones converja a una solución óptima. El primer y todavía popular método 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 lineales como las regiones de confianza se utilizan en los 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 usar 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ñado 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 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 que existen estas cantidades 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 solo la cantidad 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 dichos optimizadores, pero son incluso más difíciles de calcular, por ejemplo, la aproximación del gradiente requiere al menos N+1 evaluaciones de función. Para aproximaciones de las segundas derivadas (recogidas en la matriz Hessiana), el número de evaluaciones de funciones 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.

Métodos que evalúan Hessians (o Hessians aproximados, usando diferencias finitas):
- 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 la optimización restringida, algunos de los cuales usan solo información de (sub)gradiente y otros requieren la evaluación de Hessians.
Métodos que evalúan gradientes, o gradientes aproximados 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 tenido un interés renovado para encontrar soluciones aproximadas de problemas enormes.
- 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 locales de Lipschitz, 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, 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 perturbaciones simultáneas (SPSA) para la optimización estocástica; utiliza una aproximación de gradiente aleatoria (eficiente).
Métodos que evalúan solo valores de función: si un problema es continuamente diferenciable, 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 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 está garantizado (matemáticamente) para encontrar la solución, pero que sin embargo es útil en ciertas situaciones prácticas. Lista de algunas heurísticas bien conocidas:

Evolución diferencial
relajación dinámica
Algoritmos evolutivos
Algoritmos genéticos
Subir 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 los gradientes)
Optimización de Enjambre de partículas
recocido simulado
Tunelización estocástica
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 puede ver la dinámica de cuerpos rígidos como un intento de resolver una ecuación diferencial ordinaria en una variedad de restricciones; las restricciones son varias restricciones geométricas no lineales como "estos dos puntos siempre deben coincidir", "esta superficie no debe penetrar en 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 se puede ver 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 ingeniería, y otro subconjunto reciente y creciente de este campo es la optimización de 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.

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 los fines y los medios escasos" con usos alternativos. 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 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 comporten de manera consistente, se supone que los consumidores maximizan su utilidad, mientras que se supone que las empresas maximizan sus ganancias. Además, los agentes a menudo se modelan como reacios al riesgo, por lo que prefieren evitar el riesgo. 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. Por ejemplo, los modelos de búsqueda dinámica se utilizan para estudiar el comportamiento del mercado laboral. Una distinción crucial es entre modelos deterministas y estocásticos. Los macroeconomistas construyen modelos de equilibrio general estocástico dinámico (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.

Ingenieria Eléctrica

Algunas aplicaciones comunes de las técnicas de optimización en ingeniería eléctrica incluyen el diseño de filtros activos, la reducción de campos dispersos en sistemas de almacenamiento de energía magnética superconductora, el diseño de mapeo espacial de estructuras de microondas, antenas de teléfonos móviles, diseño basado en electromagnética. 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 metodologías de mapeo espacial desde el descubrimiento del mapeo espacial en 1993.

Ingeniería civil

La optimización ha sido ampliamente utilizada 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, la nivelación de recursos, la asignación de recursos hídricos, la gestión del tráfico y la optimización de horarios.

La investigación de operaciones

Otro campo que utiliza ampliamente las técnicas de optimización es la investigación de operaciones. 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; tales problemas se pueden resolver con métodos de optimización a gran escala y 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 la optimización matemática. Estos algoritmos se ejecutan en línea y determinan repetidamente los valores de las variables de decisión, como las aberturas de estrangulamiento en una planta de proceso, resolviendo iterativamente 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 regularmente en problemas de estimación de parámetros geofísicos. Dado un conjunto de medidas geofísicas, por ejemplo, registros sísmicos, es común resolver 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 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. La programación lineal se ha aplicado para calcular los rendimientos máximos posibles de los productos de fermentación y para inferir redes reguladoras de genes a partir de múltiples conjuntos de datos de micromatrices, así como redes reguladoras transcripcionales a partir de datos de alto rendimiento. La programación no lineal se ha utilizado para analizar el metabolismo energético y se ha aplicado a la ingeniería metabólica y la estimación de parámetros en rutas bioquímicas.

Contenido relacionado

Más resultados...