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
- Forest Optimization Algorithm
Aplicaciones
Mechanics
Problems in rigid body dynamics (in particular articulated rigid body dynamics) often require mathematical programming techniques, since you can view rigid body dynamics as attempting to solve an ordinary differential equation on a constraint manifold;[6] the constraints are various nonlinear geometric constraints such as "these two points must always coincide", "this surface must not penetrate any other", or "this point must always lie somewhere on this curve". Also, the problem of computing contact forces can be done by solving a linear complementarity problem, which can also be viewed as a QP (quadratic programming) problem.
Many design problems can also be expressed as optimization programs. This application is called design optimization. One subset is the engineering optimization, and another recent and growing subset of this field is multidisciplinary design optimization, which, while useful in many problems, has in particular been applied to aerospace engineering problems.
This approach may be applied in cosmology and astrophysics.[7]
Economics and finance
Economics is closely enough linked to optimization of agents that an influential definition relatedly describes economics qua science as the "study of human behavior as a relationship between ends and scarce means" with alternative uses.[8] Modern optimization theory includes traditional optimization theory but also overlaps with game theory and the study of economic equilibria. The Journal of Economic Literature codes classify mathematical programming, optimization techniques, and related topics under JEL:C61-C63.
In microeconomics, the utility maximization problem and its dual problem, the expenditure minimization problem, are economic optimization problems. Insofar as they behave consistently, consumers are assumed to maximize their utility, while firms are usually assumed to maximize their profit. Also, agents are often modeled as being risk-averse, thereby preferring to avoid risk. Asset prices are also modeled using optimization theory, though the underlying mathematics relies on optimizing stochastic processes rather than on static optimization. International trade theory also uses optimization to explain trade patterns between nations. The optimization of portfolios is an example of multi-objective optimization in economics.
Since the 1970s, economists have modeled dynamic decisions over time using control theory.[9] For example, dynamic search models are used to study labor-market behavior.[10] A crucial distinction is between deterministic and stochastic models.[11] Macroeconomists build dynamic stochastic general equilibrium (DSGE) models that describe the dynamics of the whole economy as the result of the interdependent optimizing decisions of workers, consumers, investors, and governments.[12][13]
Electrical engineering
Some common applications of optimization techniques in electrical engineering include active filter design,[14] stray field reduction in superconducting magnetic energy storage systems, space mapping design of microwave structures,[15] handset antennas,[16][17][18] electromagnetics-based design. Electromagnetically validated design optimization of microwave components and antennas has made extensive use of an appropriate physics-based or empirical surrogate model and space mapping methodologies since the discovery of space mapping in 1993.[19][20]
Civil engineering
Optimization has been widely used in civil engineering. Construction management and transportation engineering are among the main branches of civil engineering that heavily rely on optimization. The most common civil engineering problems that are solved by optimization are cut and fill of roads, life-cycle analysis of structures and infrastructures,[21] resource leveling,[22][23] water resource allocation, traffic management[24] and schedule optimization.
Operations research
Another field that uses optimization techniques extensively is operations research.[25] Operations research also uses stochastic modeling and simulation to support improved decision-making. Increasingly, operations research uses stochastic programming to model dynamic decisions that adapt to events; such problems can be solved with large-scale optimization and stochastic optimization methods.
Control engineering
Mathematical optimization is used in much modern controller design. High-level controllers such as model predictive control (MPC) or real-time optimization (RTO) employ mathematical optimization. These algorithms run online and repeatedly determine values for decision variables, such as choke openings in a process plant, by iteratively solving a mathematical optimization problem including constraints and a model of the system to be controlled.
Geophysics
Optimization techniques are regularly used in geophysical parameter estimation problems. Given a set of geophysical measurements, e.g. seismic recordings, it is common to solve for the physical properties and geometrical shapes of the underlying rocks and fluids. The majority of problems in geophysics are nonlinear with both deterministic and stochastic methods being widely used.
Molecular modeling
Nonlinear optimization methods are widely used in conformational analysis.
Computational systems biology
Optimization techniques are used in many facets of computational systems biology such as model building, optimal experimental design, metabolic engineering, and synthetic biology.[26] Linear programming has been applied to calculate the maximal possible yields of fermentation products,[26] and to infer gene regulatory networks from multiple microarray datasets[27] as well as transcriptional regulatory networks from high-throughput data.[28] Nonlinear programming has been used to analyze energy metabolism[29] and has been applied to metabolic engineering and parameter estimation in biochemical pathways.[30]
Machine learning
Solucionadores
Ver también
- Brachistochrone
- Curve fitting
- Deterministic global optimization
- Goal programming
- Important publications in optimization
- Least squares
- Mathematical Optimization Society (formerly Mathematical Programming Society)
- Mathematical optimization algorithms
- Mathematical optimization software
- Process optimization
- Simulation-based optimization
- Test functions for optimization
- Variational calculus
- Vehicle routing problem
Notas
- ^ "The Nature of Mathematical Programming Archived 2014-03-05 at the Wayback Machine," Mathematical Programming Glossary, INFORMS Computing Society.
- ^ Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). "History of Optimization". In Floudas, C.; Pardalos, P. (eds.). Encyclopedia of Optimization. Boston: Springer. pp. 1538–1542.
- ^ W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents.
- ^ Zervoudakis, Konstantinos; Tsafarakis, Stelios (2020). "A mayfly optimization algorithm". Computers & Industrial Engineering. ahead-of-print (ahead-of-print): head-of-print. doi:10.1016/j.cie.2020.106559.
- ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. Archived from the original on 2012-03-16.
- ^ Vereshchagin, A.F. (1989). "Modelling and control of motion of manipulation robots". Soviet Journal of Computer and Systems Sciences. 27 (5): 29–38.
- ^ Haggag, S.; Desokey, F.; Ramadan, M. (2017). "A cosmological inflationary model using optimal control". Gravitation and Cosmology. 23 (3): 236–239. Bibcode:2017GrCo...23..236H. doi:10.1134/S0202289317030069. ISSN 1995-0721. S2CID 125980981.
- ^ Lionel Robbins (1935, 2nd ed.) An Essay on the Nature and Significance of Economic Science, Macmillan, p. 16.
- ^ Dorfman, Robert (1969). "An Economic Interpretation of Optimal Control Theory". American Economic Review. 59 (5): 817–831. JSTOR 1810679.
- ^ Sargent, Thomas J. (1987). "Search". Dynamic Macroeconomic Theory. Harvard University Press. pp. 57–91. ISBN 9780674043084.
- ^ A.G. Malliaris (2008). "stochastic optimal control," The New Palgrave Dictionary of Economics, 2nd Edition. Abstract Archived 2017-10-18 at the Wayback Machine.
- ^ Rotemberg, Julio; Woodford, Michael (1997). "An Optimization-based Econometric Framework for the Evaluation of Monetary Policy" (PDF). NBER Macroeconomics Annual. 12: 297–346. doi:10.2307/3585236. JSTOR 3585236.
- ^ From The New Palgrave Dictionary of Economics (2008), 2nd Edition with Abstract links:
• "numerical optimization methods in economics" by Karl Schmedders
• "convex programming" by Lawrence E. Blume
• "Arrow–Debreu model of general equilibrium" by John Geanakoplos. - ^ De, Bishnu Prasad; Kar, R.; Mandal, D.; Ghoshal, S.P. (2014-09-27). "Optimal selection of components value for analog active filter design using simplex particle swarm optimization". International Journal of Machine Learning and Cybernetics. 6 (4): 621–636. doi:10.1007/s13042-014-0299-0. ISSN 1868-8071. S2CID 13071135.
- ^ Koziel, Slawomir; Bandler, John W. (January 2008). "Space Mapping With Multiple Coarse Models for Optimization of Microwave Components". IEEE Microwave and Wireless Components Letters. 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. (July 2013). "Space Mapping Optimization of Handset Antennas Exploiting Thin-Wire Models". IEEE Transactions on Antennas and Propagation. 61 (7): 3797–3807. Bibcode:2013ITAP...61.3797T. doi:10.1109/TAP.2013.2254695.
- ^ N. Friedrich, “Space mapping outpaces EM optimization in handset-antenna design,” microwaves&rf, Aug. 30, 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. (February 2016). "Space mapping optimization of handset antennas considering EM effects of mobile phone components and human body". International Journal of RF and Microwave Computer-Aided Engineering. 26 (2): 121–128. doi:10.1002/mmce.20945.
- ^ Bandler, J.W.; Biernacki, R.M.; Chen, Shao Hua; Grobelny, P.A.; Hemmers, R.H. (1994). "Space mapping technique for electromagnetic optimization". IEEE Transactions on Microwave Theory and Techniques. 42 (12): 2536–2544. Bibcode:1994ITMTT..42.2536B. doi:10.1109/22.339794.
- ^ Bandler, J.W.; Biernacki, R.M.; Shao Hua Chen; Hemmers, R.H.; Madsen, K. (1995). "Electromagnetic optimization exploiting aggressive space mapping". IEEE Transactions on Microwave Theory and Techniques. 43 (12): 2874–2882. Bibcode:1995ITMTT..43.2874B. doi:10.1109/22.475649.
- ^ Piryonesi, Sayed Madeh; Tavakolan, Mehdi (9 January 2017). "A mathematical programming model for solving cost-safety optimization (CSO) problems in the maintenance of structures". KSCE Journal of Civil Engineering. 21 (6): 2226–2234. doi:10.1007/s12205-017-0531-z. S2CID 113616284.
- ^ Hegazy, Tarek (June 1999). "Optimization of Resource Allocation and Leveling Using Genetic Algorithms". Journal of Construction Engineering and Management. 125 (3): 167–175. doi:10.1061/(ASCE)0733-9364(1999)125:3(167).
- ^ "Piryonesi, S. M., Nasseri, M., & Ramezani, A. (2018). Resource leveling in construction projects with activity splitting and resource constraints: a simulated annealing optimization". Canadian Journal of Civil Engineering. 46: 81–86. doi:10.1139/cjce-2017-0670. hdl:1807/93364.
- ^ Herty, M.; Klar, A. (2003-01-01). "Modeling, Simulation, and Optimization of Traffic Flow Networks". SIAM Journal on Scientific Computing. 25 (3): 1066–1087. doi:10.1137/S106482750241459X. ISSN 1064-8275.
- ^ "New force on the political scene: the Seophonisten". Archived from the original on 18 December 2014. Retrieved 14 September 2013.
- ^ a b Papoutsakis, Eleftherios Terry (February 1984). "Equations and calculations for fermentations of butyric acid bacteria". Biotechnology and Bioengineering. 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 (2006-07-24). "Inferring gene regulatory networks from multiple microarray datasets". Bioinformatics. 22 (19): 2413–2420. doi:10.1093/bioinformatics/btl396. ISSN 1460-2059. PMID 16864593.
- ^ Wang, Rui-Sheng; Wang, Yong; Zhang, Xiang-Sun; Chen, Luonan (2007-09-22). "Inferring transcriptional regulatory networks from high-throughput data". Bioinformatics. 23 (22): 3056–3064. doi:10.1093/bioinformatics/btm465. ISSN 1460-2059. PMID 17890736.
- ^ Vo, Thuy D.; Paul Lee, W.N.; Palsson, Bernhard O. (May 2007). "Systems analysis of energy metabolism elucidates the affected respiratory chain complex in Leigh's syndrome". Molecular Genetics and Metabolism. 91 (1): 15–22. doi:10.1016/j.ymgme.2007.01.012. ISSN 1096-7192. PMID 17336115.
- ^ Mendes, P.; Kell, D. (1998). "Non-linear optimization of biochemical pathways: applications to metabolic engineering and parameter estimation". Bioinformatics. 14 (10): 869–883. doi:10.1093/bioinformatics/14.10.869. ISSN 1367-4803. PMID 9927716.
Otras lecturas
- Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.
- Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. London: Academic Press. ISBN 0-12-283952-8.
- Lee, Jon (2004). A First Course in Combinatorial Optimization. Cambridge University Press. ISBN 0-521-01012-8.
- Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin: Springer. ISBN 0-387-30303-0.
- Snyman, J. A.; Wilke, D. N. (2018). Practical Mathematical Optimization : Basic Optimization Theory and Gradient-Based Algorithms (2nd ed.). Berlin: Springer. ISBN 978-3-319-77585-2.
enlaces externos
- "Decision Tree for Optimization Software". Links to optimization source codes
- "Global optimization".
- "EE364a: Convex Optimization I". Course from Stanford University.
- Varoquaux, Gaël. "Mathematical Optimization: Finding Minima of Functions".