Optimización matemática (alternativamente escrito optimización ) o programación matemática es la selección de un mejor elemento, con respecto a algún criterio, a partir de un conjunto de alternativas disponibles. [1] 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 en las matemáticas durante siglos. [2]
En el caso más simple, 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 valores "mejores disponibles" de alguna función objetivo dado un dominio definido (o entrada), incluyendo una variedad de diferentes tipos de funciones objetivas y diferentes tipos de dominios.
Problemas de optimización
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 reales
- Buscado: un elemento x 0 ∈ A tal que f ( x 0 ) ≤ f ( x ) para todo x ∈ A ("minimización") o tal que f ( x 0 ) ≥ 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 programación lineal ; consulte la Historia a continuación). Muchos problemas teóricos y del mundo real pueden modelarse en este marco general.
Dado que lo siguiente es válido
con
es más conveniente resolver problemas de minimización. Sin embargo, la perspectiva opuesta 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 (el más bajo).
Normalmente, A es un subconjunto del espacio euclidiano ℝ n , 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 opciones , mientras que los elementos de A se denominan soluciones candidatas o soluciones factibles .
La función f se llama, de diversas maneras, una función objetivo , una función de pérdida o función de coste (minimización), [3] una función de utilidad o función de aptitud (maximización), o, en ciertos campos, una función de energía o energía funcional . 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 se suelen plantear 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
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.
Si bien 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 los problemas no convexos, incluida la mayoría de los solucionadores disponibles comercialmente, no son capaces de hacer una distinción entre soluciones óptimas localmente y soluciones óptimas globalmente, 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 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 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:
Esto denota el valor mínimo de la función objetivo x 2 + 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
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 un 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:
o equivalente
Esto representa el valor (o valores) del argumento x en el intervalo (−∞, −1] que minimiza (o minimiza) la función objetivo x 2 + 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 .
Similar,
o equivalente
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 programas de entrenamiento y logística propuestos , que eran los problemas que Dantzig estudió 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. [ cita requerida ]
Otros investigadores notables en optimización matemática incluyen los siguientes:
- Richard Bellman
- Roger Fletcher
- Ronald A. Howard
- Fritz John
- Narendra Karmarkar
- William Karush
- Leonid Khachiyan
- Bernard Koopman
- Harold Kuhn
- László Lovász
- Arkadi Nemirovski
- Yurii Nesterov
- Lev Pontryagin
- R. Tyrrell Rockafellar
- Naum Z. Shor
- Albert 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 únicamente igualdades y desigualdades lineales. Este conjunto de restricciones 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 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 de enteros estudia 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 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 las relaciones 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. Este puede ser un programa convexo o no. 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 subyacentes al problema de optimización. La optimización robusta tiene como objetivo encontrar soluciones que sean válidas en 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.
- La heurística y la metaheurística 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 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 las 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 especial utilidad en la programación.
- El mapeo espacial es un concepto para modelar y optimizar un sistema de ingeniería con precisión de modelo de alta fidelidad (fina) explotando un modelo aproximado 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, la toma de decisiones a lo largo del tiempo):
- El cálculo de variaciones busca optimizar una acción integral en algún espacio hasta un extremo variando una función de las coordenadas.
- 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 fuera 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 comprometen el peso y la 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 .
Un diseño se considera "óptimo de Pareto" (equivalentemente, "Pareto eficiente" 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 está 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 optimización multiobjetivo indica que falta alguna información: se dan los objetivos deseables pero las combinaciones de ellos no se clasifican entre sí. En algunos casos, la información faltante 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 orden (parcial) ya no está 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. Todos podrían ser globalmente buenos (el mismo valor de función de coste) 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 clásicas de optimización 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 se puede considerar 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 deben comenzar desde un punto factible. Una forma de obtener tal punto es relajar las condiciones de factibilidad usando 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 equipo 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 optimalidad
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 opciones. 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 un conjunto de condiciones de primer orden.
El método del multiplicador de Lagrange puede encontrar los valores óptimos de los problemas con restricciones de igualdad . 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 es ninguno. 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 de Hesse ) en problemas no restringidos, o la matriz de segundas derivadas de la función objetivo y las restricciones llamadas bordeadas Arpillera en problemas restringidos. Las condiciones que distinguen los máximos o mínimos de otros puntos estacionarios se denominan "condiciones de segundo orden" (consulte " 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 ó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 no restringidos 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 subgrado cero certifica que se ha encontrado un mínimo local para los problemas de minimización con funciones convexas y otras funciones locales de Lipschitz .
Además, los puntos críticos se pueden clasificar usando la definición de la matriz de Hesse : si el Hesse es definido positivo 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 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 también será un mínimo global. Existen técnicas numéricas eficientes para minimizar las funciones convexas, como los métodos de punto interior .
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 en 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 función. Si bien la evaluación de hessianos (H) y gradientes (G) mejora la tasa de convergencia, para las funciones para las que existen estas cantidades y varían con suficiente fluidez, tales evaluaciones aumentan la complejidad computacional (o costo computacional) de cada iteración. En algunos casos, la complejidad computacional puede ser excesivamente alta.
Un criterio importante para los optimizadores es solo 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, la aproximación del gradiente requiere al menos N + 1 evaluaciones de funciones. Para las aproximaciones de las segundas derivadas (recopiladas en la matriz de Hesse), 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. Cuál es mejor con respecto al número de llamadas a funciones depende del problema en sí.
- Métodos que evalúan hessianos (o hessianos 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 punto interior : esta es una gran clase de métodos para la optimización restringida. Algunos métodos de punto interior usan solo información de (sub) gradiente y otros requieren la evaluación de hessianos.
- 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 objetivas 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 empinado" o "ascenso más empinado"): 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 a nivel local utilizando 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 combinado de descenso: 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 elipsoide : Método iterativo para pequeños problemas con funciones objetivas cuasiconvexas y de gran interés teórico, particularmente en el establecimiento de la complejidad temporal polinomial de algunos problemas de optimización combinatoria. Tiene similitudes con los métodos de 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 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 enumera a continuación.
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 en una solución óptima. El primer y todavía popular método para asegurar 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í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.
Heurísticas
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 está garantizado (matemáticamente) para encontrar la solución, pero que, no obstante, es útil en determinadas situaciones prácticas. Lista de algunas heurísticas conocidas:
- Algoritmo de optimización de Mayfly [4]
- Algoritmo memético
- Evolución diferencial
- Algoritmos evolutivos
- Relajación dinámica
- Algoritmos genéticos
- Escalada de colinas con reinicio aleatorio
- 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
- Algoritmo de búsqueda gravitacional
- Recocido simulado
- Túneles estocásticos
- Búsqueda tabú
- Optimización de búsqueda reactiva (RSO) [5] implementada en LIONsolver
- Algoritmo de optimización forestal
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 restricción; [6] las restricciones son varias restricciones geométricas no lineales tales 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 puede verse como un problema QP (programación cuadrática).
Muchos problemas de diseño también se pueden expresar como programas de optimización. Esta aplicación se llama optimización de 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 los problemas de la ingeniería aeroespacial .
Este enfoque se puede aplicar en cosmología y astrofísica. [7]
Economía y Finanzas
La economía está estrechamente vinculada a la optimización suficiente de agentes que una definición influyente describe relacionado con lo anterior la economía qua la ciencia como el "estudio del comportamiento humano como una relación entre fines y los escasos medios" con usos alternativos. [8] La teoría de la optimización moderna incluye la teoría de la 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 de la Revista de Literatura Económica 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 generalmente 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 optimización, aunque las matemáticas subyacentes se basan en optimizar los procesos estocásticos en lugar de en 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 . [9] Por ejemplo, los modelos de búsqueda dinámica se utilizan para estudiar el comportamiento del mercado laboral . [10] Una distinción crucial es entre modelos deterministas y estocásticos. [11] 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 decisiones de optimización interdependientes de trabajadores, consumidores, inversores y gobiernos. [12] [13]
Ingenieria Eléctrica
Algunas aplicaciones comunes de las técnicas de optimización en la ingeniería eléctrica incluyen el diseño de filtros activos , [14] la reducción del campo disperso en los sistemas de almacenamiento de energía magnética superconductora, el diseño de mapeo espacial de estructuras de microondas , [15] antenas de teléfonos, [16] [17] [18] electromagnéticos -Diseño basado en. La optimización del diseño validado electromagnéticamente de los componentes de microondas y las antenas ha hecho un uso extensivo de un modelo sustituto empírico o basado en la física apropiada y metodologías de cartografía espacial desde el descubrimiento de la cartografía espacial en 1993. [19] [20]
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 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, [21] nivelación de recursos , [22] [23] asignación de recursos hídricos , gestión del tráfico [24] y programación. mejoramiento.
La investigación de operaciones
Otro campo que utiliza ampliamente las técnicas de optimización es la investigación de operaciones . [25] La investigación de operaciones también utiliza modelos y simulación estocásticos 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; Estos problemas se pueden resolver con métodos de optimización estocástica y optimización a gran escala .
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 optimización matemática. Estos algoritmos se ejecutan en línea y determinan repetidamente valores para 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 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 no son 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. [26] Se ha aplicado la programación lineal para calcular los rendimientos máximos posibles de productos de fermentación, [26] y para inferir redes reguladoras de genes a partir de múltiples conjuntos de datos de microarrays [27] , así como redes reguladoras transcripcionales a partir de datos de alto rendimiento. [28] La programación no lineal se ha utilizado para analizar el metabolismo energético [29] y se ha aplicado a la ingeniería metabólica y la estimación de parámetros en las vías bioquímicas. [30]
Aprendizaje automático
Solucionadores
Ver también
- Braquistocrona
- Ajuste de curvas
- Optimización global determinista
- Programación de metas
- 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 variacional
- Problema de ruta del vehículo
Notas
- ^ " La naturaleza de la programación matemática Archivado el 5 de marzo de 2014 en la Wayback Machine ", Glosario de programación matemática , INFORMS Computing Society.
- ^ 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.
- ^ W. Erwin Diewert (2008). "funciones de coste", The New Palgrave Dictionary of Economics , 2ª edición de contenidos .
- ^ Zervoudakis, Konstantinos; Tsafarakis, Stelios (2020). "Un algoritmo de optimización de efímeras". Computación e Ingeniería Industrial . antes de la impresión (antes de la impresión): cabeza de impresión. doi : 10.1016 / j.cie.2020.106559 .
- ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Búsqueda reactiva y optimización inteligente . Springer Verlag . ISBN 978-0-387-09623-0. Archivado desde el original el 16 de marzo de 2012.
- ^ Vereshchagin, AF (1989). "Modelado y control de movimiento de robots de manipulación". Revista soviética de ciencias informáticas y de sistemas . 27 (5): 29–38.
- ^ 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 bibliográfico : 2017GrCo ... 23..236H . doi : 10.1134 / S0202289317030069 . ISSN 1995-0721 . S2CID 125980981 .
- ^ Lionel Robbins (1935, 2ª ed.) Un ensayo sobre la naturaleza y la importancia de la ciencia económica , Macmillan, p. dieciséis.
- ^ Dorfman, Robert (1969). "Una interpretación económica de la teoría del control óptimo". American Economic Review . 59 (5): 817–831. JSTOR 1810679 .
- ^ Sargent, Thomas J. (1987). "Buscar" . Teoría macroeconómica dinámica . Prensa de la Universidad de Harvard. págs. 57–91. ISBN 9780674043084.
- ^ 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 la Wayback Machine .
- ^ 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 .
- ^ De The New Palgrave Dictionary of Economics (2008), segunda edición con enlaces abstractos:
• " 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 . - ^ 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 la optimización del 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 .
- ^ Koziel, Slawomir; Bandler, John W. (enero de 2008). "Mapeo espacial con múltiples modelos gruesos para la optimización de componentes de microondas". Cartas de componentes inalámbricos y de microondas IEEE . 18 (1): 1-3. CiteSeerX 10.1.1.147.5407 . doi : 10.1109 / LMWC.2007.911969 . S2CID 11086218 .
- ^ Tu, Sheng; Cheng, Qingsha S .; Zhang, Yifan; Bandler, John W .; Nikolova, Natalia K. (julio de 2013). "Optimización de mapeo espacial de antenas de teléfonos que utilizan modelos de cable delgado" . Transacciones IEEE sobre antenas y propagación . 61 (7): 3797–3807. Código bibliográfico : 2013ITAP ... 61.3797T . doi : 10.1109 / TAP.2013.2254695 .
- ^ N. Friedrich, "El mapeo espacial supera a la optimización EM en el diseño de antena de teléfono", microondas y radiofrecuencia, 30 de agosto de 2013.
- ^ 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 de mapeo espacial de antenas de teléfonos móviles considerando los efectos EM de los componentes del teléfono móvil 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 .
- ^ Bandler, JW; Biernacki, RM; Chen, Shao Hua; Grobelny, PA; 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 Bibliográfico : 1994ITMTT..42.2536B . doi : 10.1109 / 22.339794 .
- ^ 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 .
- ^ 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 de costes-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 .
- ^ 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) .
- ^ "Piryonesi, SM, Nasseri, M. y Ramezani, A. (2018). Nivelación de recursos en proyectos de construcción con división de actividades y limitaciones 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 .
- ^ 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. doi : 10.1137 / S106482750241459X . ISSN 1064-8275 .
- ^ "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 .
- ^ a b 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 .
- ^ 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 .
- ^ 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 .
- ^ 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 afectada 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 .
- ^ 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 .
Otras lecturas
- 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 . 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.
- Snyman, JA; Wilke, DN (2018). Optimización matemática práctica: teoría básica de optimización y algoritmos basados en gradientes (2ª ed.). Berlín: Springer. ISBN 978-3-319-77585-2.
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: encontrar mínimos de funciones" .