Optimización matemática (Mathematical optimization)

Optimización matemática (alternativamente escrita como optimización) o programación matemática es el proceso de seleccionar un elemento óptimo, basándose en criterios específicos, de un conjunto definido de alternativas disponibles. Por lo general, se clasifica en dos subcampos principales: optimización discreta y optimización continua. Los problemas de optimización surgen en varias disciplinas cuantitativas, que van desde la informática y la ingeniería hasta la investigación de operaciones y la economía, y la búsqueda de metodologías de solución efectivas ha sido un enfoque central en las matemáticas durante siglos.

Desde una perspectiva más amplia, un problema de optimización implica maximizar o minimizar una función de valor real mediante la selección sistemática de valores de entrada de un dominio permisible y la posterior evaluación de la salida de la función. Extender la teoría de la optimización y sus técnicas asociadas a diversas formulaciones de problemas representa un dominio importante dentro de las matemáticas aplicadas.

Problemas de optimización

Los problemas de optimización normalmente se clasifican en dos categorías principales, según la naturaleza de sus variables, específicamente si son continuas o discretas:

• Un problema de optimización con variables discretas se denomina optimización discreta, donde el objetivo es identificar un elemento óptimo, como un número entero, una permutación o un gráfico, de un conjunto contable.
• Un problema que involucra variables continuas se conoce como optimización continua y requiere la identificación de argumentos óptimos dentro de un dominio continuo. Esta categoría abarca problemas tanto restringidos como multimodales.

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

Dado: Una función ${\displaystyle f:A\rightarrow \mathbb {R} }$ mapeo de un conjunto A a los números reales.

Buscado: Un elemento x§56§ ∈ A tal que f(x§1516§) ≤ f(x) para todo x ∈ A (que representa la minimización) o tal que f(x§3334§) ≥ f(x) para todo x ∈ A (que representa maximización).

Este tipo de formulación se denomina problema de optimización o problema de programación matemática. Este término, aunque no está directamente asociado con la programación informática, sigue prevaleciendo, por ejemplo, en la programación lineal. Dentro de este marco integral se pueden modelar eficazmente numerosos desafíos teóricos y del mundo real.

Dada la validez de la siguiente equivalencia:

f ( x §1617§ ) ≥ f ( x ) ⇔ − f ( x §5152§ ) ≤ − f ( x ) , {\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),}

es suficiente abordar únicamente los problemas de minimización. Por el contrario, un enfoque igualmente válido implicaría centrarse exclusivamente en problemas de maximización.

En física, los problemas formulados con esta técnica a menudo se denominan minimización de energía, donde el valor de la función f significa la energía del sistema bajo consideración. Dentro del aprendizaje automático, la evaluación continua de la calidad de un modelo de datos es imperativa, lo que generalmente se logra mediante una función de costo donde un valor mínimo indica un conjunto de parámetros potencialmente óptimos asociados con el menor error posible.

El conjunto A normalmente constituye un subconjunto del espacio euclidiano ${\displaystyle \mathbb {R} ^{n}}$. Este subconjunto se define frecuentemente por una serie de restricciones, que pueden ser igualdades o desigualdades que todos los elementos de A deben satisfacer. El dominio A para la función f se conoce como espacio de búsqueda o conjunto de opciones, y sus elementos individuales se designan como soluciones candidatas o soluciones factibles.

La función f se conoce con varios nombres, entre ellos función objetiva, criterio función, función de pérdida o función de costo cuando el objetivo es la minimización. Para problemas de maximización, puede denominarse función de utilidad o función de aptitud. En disciplinas específicas, también se la conoce como función energética o energía funcional. Una solución óptima se define como una solución factible que minimiza o maximiza la función objetivo.

Dentro del campo de las matemáticas, los problemas de optimización estándar generalmente se formulan como tareas de minimización.

Un mínimo local, denotado como x*, se caracteriza como un elemento para el cual un valor positivo δ > 0 existe y satisface la condición de que:

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

la desigualdad f(x*) ≤ f(x) se satisface;

Esto implica que dentro de una vecindad específica de x*, todos los valores de la función son mayores o iguales que el valor en x*. Los máximos locales se caracterizan por una definición análoga.

Aunque un mínimo local representa un valor superior o igual al de sus elementos vecinos inmediatos, un mínimo global supera o iguala el valor de cada elemento factible. Normalmente, en problemas de minimización, pueden existir múltiples mínimos locales a menos que la función objetivo sea convexa. Para un problema convexo, un mínimo local interior (uno que no está ubicado en el límite del conjunto factible) también constituye el mínimo global. Sin embargo, un problema no convexo puede poseer varios mínimos locales, y no todos necesariamente califican como mínimos globales.

Numerosos algoritmos diseñados para abordar problemas no convexos, incluidos la mayoría de los solucionadores comerciales, con frecuencia no pueden diferenciar entre soluciones localmente óptimas y globalmente óptimas, y a menudo tratan los óptimos locales como las verdaderas soluciones al problema. La optimización global es un campo especializado dentro de las matemáticas aplicadas y el análisis numérico dedicado a crear algoritmos deterministas que pueden garantizar la convergencia a la solución óptima real de un problema no convexo dentro de un período de tiempo finito.

Convenciones de notación

Los problemas de optimización se representan frecuentemente utilizando sistemas de notación específicos. Los siguientes ejemplos ilustran esto:

Determinación de los valores mínimo y máximo de una función

Examine la notación siguiente:

min x ∈<!-- ∈ --> R ( x §3132§ + §3738§ ) {\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)}

Esta notación significa el valor más bajo posible de la función objetivo x§34§ + 1, donde x se selecciona del conjunto de números reales ${\displaystyle \mathbb {R} }$. En este caso específico, el valor mínimo es 1, que se logra cuando x es igual a 0.

De manera similar, la notación

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

busca identificar el valor más alto posible de la función objetivo 2x, donde x representa cualquier número real. Sin embargo, en este escenario, no existe un máximo finito porque la función objetivo no está acotada, lo que lleva a un resultado de "infinito" o "indefinido".

Argumentos de entrada óptimos

La siguiente notación ilustra:

a r g m i n x ∈<!-- ∈ --> ( −<!-- − --> ∞<!-- ∞ --> , −<!-- − --> §4344§ ] x §5657§ + §6263§ , {\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}

Alternativamente, esto se puede expresar como:

a r g m i n x x §3435§ + §4041§ , sujeto a: x ∈ ( − ∞ , − §7071§ ] . {\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{sujeto a:}}\;x\in (-\infty ,-1].}

Esta expresión identifica los valores de argumento x dentro del intervalo (−∞,−1] que producen el mínimo para la función objetivo x§78§ + 1. Es importante tener en cuenta que esta consulta no busca el valor mínimo de la función en sí, sino más bien los argumentos que lo producen. En consecuencia, la solución es x = −1, dado que x = 0 es inviable, lo que significa que queda fuera del conjunto factible definido.

De manera análoga,

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

Dicho de forma alternativa,

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

Esto denota el par(es) {x, y} que maximiza(n) el valor de la función objetivo x cos y, sujeto a la restricción de que x esté dentro del intervalo [−5,5]. El valor máximo específico de la expresión no es relevante en este contexto. En consecuencia, las soluciones son pares estructurados como {5, 2kπ} y {−5, (2k + 1)π}, donde k representa cualquier número entero.

Los operadores arg min y arg max se indican alternativamente como argmin y argmax, que significan respectivamente el argumento del mínimo y el argumento del máximo.

Historial

Fermat y Lagrange desarrollaron fórmulas basadas en cálculo para identificar puntos óptimos. Por el contrario, Newton y Gauss introdujeron metodologías iterativas para acercarse a un óptimo.

George B. Dantzig acuñó el término "programación lineal" para describir escenarios de optimización específicos; sin embargo, una parte sustancial de la teoría subyacente había sido establecida previamente por Leonid Kantorovich en 1939. Es importante señalar que Programación, en este contexto, no pertenece a la programación de computadoras; más bien, se origina en el uso por parte del ejército de los Estados Unidos del término programa para denotar programas propuestos de entrenamiento y logística, que constituyeron los problemas que Dantzig investigó durante ese período. Dantzig publicó posteriormente el algoritmo Simplex en 1947. Al mismo tiempo, John von Neumann y otros investigadores contribuyeron a los fundamentos teóricos de la programación lineal, incluida la teoría de la dualidad.

Otros investigadores destacados en el campo de la optimización matemática incluyen:

Subcampos principales

• La programación convexa investiga escenarios donde la función objetivo es convexa para problemas de minimización o cóncava para problemas de maximización, y el conjunto de restricciones en sí es convexo. Este enfoque puede considerarse un ejemplo específico de programación no lineal o una generalización más amplia de programación cuadrática lineal o convexa.
  • La programación lineal (LP), un subconjunto de la programación convexa, se centra en situaciones en las que la función objetivo f es lineal y las restricciones están definidas exclusivamente por igualdades y desigualdades lineales. Cuando está acotado, dicho conjunto de restricciones se denomina poliedro o politopo.
  • La programación de conos de segundo orden (SOCP) constituye una forma de programación convexa que abarca categorías específicas de programas cuadráticos.
  • La programación semidefinida (SDP) representa un subcampo de optimización convexa caracterizado por variables subyacentes que son matrices semidefinidas. Este método sirve como una generalización de la programación cuadrática lineal y convexa.
  • La programación cónica constituye un marco generalizado para la programación convexa. La programación lineal (LP), la programación de conos de segundo orden (SOCP) y la programación semidefinida (SDP) pueden conceptualizarse como programas cónicos cuando se emplea el tipo de cono adecuado.
  • La programación geométrica es una metodología que permite transformar restricciones objetivas y de desigualdad, cuando se expresan como posinomios, y restricciones de igualdad, cuando se expresan como monomios, en un programa convexo.
• La programación entera investiga programas lineales donde un subconjunto o todas las variables están restringidos a valores enteros. Este enfoque es inherentemente no convexo y normalmente presenta desafíos computacionales significativamente mayores en comparación con la programación lineal estándar.
• La programación cuadrática permite que la función objetivo incorpore términos cuadráticos, siempre que el conjunto factible esté definido por igualdades y desigualdades lineales. Bajo ciertas configuraciones del término cuadrático, este método cae dentro del dominio de la programación convexa.
• La programación fraccional investiga la optimización de proporciones entre dos funciones no lineales. Una categoría específica, los programas fraccionarios cóncavos, se pueden transformar en problemas de optimización convexos.
• La programación no lineal aborda escenarios donde la función objetivo, las restricciones o ambas incorporan componentes no lineales. Estos programas pueden ser convexos o no, característica que generalmente influye en la complejidad de su solución.
• La programación estocástica examina situaciones en las que ciertas restricciones o parámetros dependen de variables aleatorias.
• Al igual que la programación estocástica, la optimización sólida intenta tener en cuenta la incertidumbre de los datos dentro de un problema de optimización. Su objetivo es identificar soluciones que sigan siendo válidas en todas las posibles manifestaciones de incertidumbres, según lo delineado por un conjunto de incertidumbres.
• La optimización combinatoria aborda problemas caracterizados por un conjunto discreto de soluciones factibles, o problemas que pueden transformarse en una forma tan discreta.
• La optimización estocástica se aplica cuando el proceso de búsqueda implica mediciones de funciones aleatorias o ruidosas, o entradas aleatorias.
• La optimización de dimensión infinita investiga escenarios donde el conjunto de soluciones factibles constituye un subconjunto de un espacio de dimensión infinita, por ejemplo, un espacio funcional.
• Las heurísticas y metaheurísticas operan con suposiciones mínimas o nulas con respecto al problema de optimización. Si bien las heurísticas normalmente no garantizan el descubrimiento de una solución óptima, con frecuencia se emplean para identificar soluciones aproximadas para numerosos desafíos de optimización complejos.
• La satisfacción de restricciones examina situaciones en las que la función objetivo f permanece constante, un principio aplicado en la inteligencia artificial, particularmente en el razonamiento automatizado.
  • La programación de restricciones representa un paradigma donde las relaciones entre variables se articulan como restricciones.
• La programación disyuntiva se emplea en contextos donde se deben satisfacer al menos una, pero no todas, las restricciones especificadas, lo que resulta particularmente útil en la programación de aplicaciones.
• El mapeo espacial es una metodología para modelar y optimizar sistemas de ingeniería para lograr una precisión de modelo de alta fidelidad aprovechando un modelo aproximado o sustituto apropiado y físicamente significativo.

Varios subcampos desarrollan principalmente técnicas de optimización dentro de contextos dinámicos, que involucran específicamente la toma de decisiones a lo largo del tiempo:

• El cálculo de variaciones se enfoca en identificar caminos óptimos para lograr un objetivo específico, por ejemplo, determinar una superficie con un límite definido que posea el mínimo área posible.
• La teoría del control óptimo amplía el cálculo de variaciones incorporando políticas de control.
• La programación dinámica ofrece un método para resolver problemas de optimización estocástica caracterizados por parámetros de modelo aleatorios o desconocidos. Este enfoque implica una estrategia de optimización que descompone un problema en subproblemas más pequeños, con sus interrelaciones descritas por la ecuación de Bellman.
• La programación matemática con restricciones de equilibrio implica escenarios donde las restricciones abarcan desigualdades variacionales o complementariedades.

Optimización multiobjetivo

La incorporación de múltiples objetivos en un problema de optimización aumenta inherentemente su complejidad. Por ejemplo, la optimización de un diseño estructural normalmente busca tanto ligereza como rigidez. Cuando los objetivos entran en conflicto, se hace necesaria una compensación, lo que potencialmente resulta en un diseño único más liviano, un diseño único más rígido y una gama infinita de diseños que representan compromisos entre peso y rigidez. El conjunto de diseños de compensación que mejoran un criterio y potencialmente disminuyen otro se denomina conjunto de Pareto. La representación gráfica del peso versus la rigidez para estos diseños óptimos forma la frontera de Pareto.

Un diseño se considera "óptimo de Pareto" (también conocido como "eficiente de Pareto" o perteneciente al conjunto de Pareto) si ningún otro diseño lo domina. La dominación ocurre cuando un diseño es inferior en algunos aspectos y superior en ninguno en comparación con otro diseño, lo que lo hace no óptimo de Pareto.

La selección de una "solución favorita" de un conjunto de soluciones "óptimas de Pareto" generalmente se asigna a quien toma las decisiones. Esto implica que formular un problema como optimización multiobjetivo indica una falta de información, específicamente con respecto a la priorización relativa de los objetivos deseables. En ciertos escenarios, esta información faltante se puede obtener a través de sesiones interactivas con quien toma las decisiones.

Los problemas de optimización multiobjetivo se han generalizado aún más a problemas de optimización vectorial, en los que el orden parcial no está necesariamente definido por el criterio de Pareto.

Optimización multimodal y global

Los problemas de optimización frecuentemente presentan multimodalidad, lo que significa que abarcan varias soluciones efectivas. Estas soluciones pueden ser uniformemente óptimas a nivel global (con valores de función de costos idénticos) o comprender una combinación de resultados óptimos a nivel global y local. El objetivo principal de un optimizador multimodal es identificar todas, o al menos un subconjunto significativo, de estas múltiples soluciones.

Las técnicas de optimización tradicionales, debido a su naturaleza iterativa, a menudo resultan inadecuadas para identificar múltiples soluciones. Esta limitación surge porque incluso con puntos de partida variados en múltiples ejecuciones de algoritmos, no hay seguridad de descubrir soluciones distintas.

Las metodologías destacadas para abordar problemas de optimización global, particularmente aquellos caracterizados por la presencia de múltiples extremos locales, incluyen algoritmos evolutivos, optimización bayesiana y recocido simulado.

Clasificación de Puntos Críticos y Extremos

El problema de la viabilidad

El problema de satisfacibilidad, también conocido como problema de viabilidad, implica identificar cualquier solución viable sin considerar su valor objetivo. Este escenario se puede conceptualizar como un caso específico de optimización matemática donde todas las soluciones factibles comparten un valor objetivo idéntico, lo que hace que cada solución sea óptima.

Numerosos algoritmos de optimización necesitan un punto factible inicial. Una estrategia común para lograrlo implica relajar las condiciones de viabilidad mediante la introducción de una variable de holgura; una holgura suficiente garantiza que cualquier punto de partida sea factible. Posteriormente, esta variable de holgura se minimiza hasta alcanzar un valor nulo o negativo.

Existencia de Optima

El teorema del valor extremo de Karl Weierstrass postula que una función continua de valor real definida en un conjunto compacto alcanzará sus valores máximo y mínimo. En términos más generales, una función semicontinua inferior en un conjunto compacto alcanzará su mínimo, mientras que una función semicontinua superior en un conjunto compacto alcanzará su máximo.

Condiciones necesarias para la optimización

Un teorema de Fermat afirma que los óptimos para problemas no restringidos ocurren en puntos estacionarios, caracterizados por una primera derivada cero o gradiente de la función objetivo. De manera más integral, los óptimos pueden ubicarse en puntos críticos donde la primera derivada o gradiente es cero o no está definido, o a lo largo del límite de la región factible. Una ecuación o sistema de ecuaciones que especifica 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 se puede emplear para identificar óptimos en problemas sujetos a restricciones de igualdad. Para los problemas que incorporan restricciones de igualdad y/o desigualdad, las 'condiciones de Karush-Kuhn-Tucker' proporcionan un marco para localizar los óptimos.

Condiciones suficientes para la optimización

Aunque la prueba de la primera derivada puede señalar extremos potenciales, no diferencia entre un mínimo, un máximo o un punto de silla. Para funciones objetivas que son dos veces diferenciables, estas distinciones se pueden hacer examinando la segunda derivada o la matriz de Hesse (la matriz de segundas derivadas) en problemas sin restricciones. En problemas restringidos, se utiliza el Hessiano bordeado, que incluye segundas derivadas tanto de la función objetivo como de las restricciones. Los criterios que distinguen los máximos o mínimos de otros puntos estacionarios se denominan "condiciones de segundo orden". Si una posible solución cumple las condiciones de primer orden, entonces su cumplimiento de las condiciones de segundo orden es suficiente para confirmar al menos la optimización local.

Sensibilidad y Continuidad de Optima

El teorema de la envolvente aclara la alteración en el valor de una solución óptima en respuesta a un cambio en un parámetro subyacente. El procedimiento analítico para cuantificar este cambio se denomina estática comparativa.

El teorema del máximo de Claude Berge, introducido en 1963, aclara la continuidad de una solución óptima en relación con sus parámetros subyacentes.

Cálculo de optimización

En problemas de optimización sin restricciones que involucran funciones dos veces diferenciables, los puntos críticos son identificables como puntos estacionarios donde el gradiente de la función objetivo es cero. En términos más generales, para problemas de minimización con funciones de Lipschitz convexas o localmente (como las que se encuentran en la minimización de funciones de pérdida de redes neuronales), un subgradiente cero confirma la identificación de un mínimo local. Además, la estimación del impulso positivo-negativo puede facilitar escapar de los mínimos locales y lograr la convergencia al mínimo global de la función objetivo.

Los puntos críticos se pueden categorizar aún más en función de la precisión de la matriz de Hesse: una hessiana definida positiva en un punto crítico indica un mínimo local; un hessiano definido negativo significa un máximo local; y un hessiano indefinido sugiere un punto de silla.

Los problemas de optimización restringidos se convierten frecuentemente en formas no restringidas mediante la aplicación de multiplicadores de Lagrange. Además, la relajación lagrangiana ofrece un método para derivar soluciones aproximadas para problemas complejos restringidos.

Si la función objetivo es convexa, cualquier mínimo local representa inherentemente un mínimo global. Se encuentran disponibles métodos numéricos eficientes, como las técnicas de puntos interiores, para minimizar funciones convexas.

Convergencia global

Cuando la función objetivo no es cuadrática, numerosos algoritmos de optimización emplean estrategias para garantizar que una subsecuencia de iteraciones converja hacia una solución óptima. Un método de garantía de convergencia fundamental y ampliamente utilizado implica búsquedas de líneas, que optimizan una función a lo largo de una única dimensión. Un enfoque alternativo, cada vez más frecuente, para garantizar la convergencia utiliza regiones de confianza. Tanto las búsquedas de líneas como las regiones de confianza son parte integral de las técnicas contemporáneas de optimización no diferenciables. Normalmente, los optimizadores globales presentan un rendimiento más lento en comparación con los optimizadores locales sofisticados (por ejemplo, BFGS); en consecuencia, a menudo se puede sintetizar un optimizador global eficaz iniciando un optimizador local desde múltiples puntos de partida distintos.

Técnicas de optimización computacional

Para abordar problemas de optimización, los investigadores pueden emplear algoritmos que concluyen dentro de un número finito de pasos, métodos iterativos diseñados para converger a una solución para clases de problemas específicos o heurísticas que ofrecen soluciones aproximadas, incluso si sus iteraciones no necesariamente convergen.

Algoritmos de optimización

• El algoritmo Simplex, desarrollado por George Dantzig, está diseñado específicamente para programación lineal.
• Se han desarrollado extensiones del algoritmo Simplex para programación cuadrática y programación lineal-fraccional.
• Las variantes del algoritmo Simplex son particularmente adecuadas para problemas de optimización de redes.
• Algoritmos combinatorios
• Algoritmos de optimización cuántica

Métodos iterativos

Los métodos iterativos empleados para resolver problemas de programación no lineal se diferencian por su dependencia de la evaluación de hessianos, gradientes o únicamente valores de funciones. Aunque la evaluación de Hessianas (H) y gradientes (G) puede mejorar la tasa de convergencia para funciones suficientemente suaves donde existen estas cantidades, tales evaluaciones elevan simultáneamente la complejidad computacional (o costo) por iteración. En ciertos escenarios, esta carga computacional puede llegar a ser prohibitivamente alta.

Un criterio principal para evaluar los optimizadores es el número de evaluaciones de funciones requeridas, ya que esto a menudo constituye un esfuerzo computacional significativo, que con frecuencia supera las operaciones internas del propio optimizador, que procesa principalmente N variables. Si bien los derivados ofrecen información detallada para los optimizadores, su cálculo es más desafiante; por ejemplo, aproximar el gradiente requiere al menos N+1 evaluaciones de funciones. Para aproximaciones de derivadas de segundo orden, compiladas dentro de la matriz de Hesse, el número de evaluaciones de funciones aumenta con N². El método de Newton, que requiere derivadas de segundo orden, incurre en un costo computacional por iteración proporcional a N² llamadas a funciones, mientras que un optimizador de gradiente puro más simple requiere solo N llamadas. Sin embargo, los optimizadores de gradiente suelen exigir más iteraciones que el algoritmo de Newton. La elección óptima con respecto al número de llamadas a funciones depende del problema específico.

• • Método de Newton
  • La programación cuadrática secuencial representa una metodología basada en Newton adecuada para problemas restringidos de pequeña y mediana escala, con ciertas variantes capaces de abordar desafíos de grandes dimensiones.
  • Los métodos de puntos interiores constituyen una categoría amplia de técnicas para la optimización restringida, algunas se basan únicamente en información de (sub)gradiente y otras requieren la evaluación de hessianas.
• • Métodos de descenso de coordenadas: algoritmos que ajustan iterativamente una sola coordenada en cada paso.
  • Los métodos de gradiente conjugado son enfoques iterativos diseñados para problemas a gran escala. Teóricamente, estos métodos logran una terminación finita cuando se aplican a funciones objetivo cuadráticas; sin embargo, esta terminación finita no se realiza en la práctica en sistemas informáticos de precisión finita.
  • El descenso en gradiente, también conocido como "descenso más pronunciado" o "ascenso más pronunciado", es un método de importancia histórica y teórica. Si bien es inherentemente lento, ha experimentado un interés renovado por identificar soluciones aproximadas a problemas excepcionalmente de gran escala.
  • Los métodos de subgradiente representan un enfoque iterativo para grandes funciones de Lipschitz locales, empleando gradientes generalizados. Como señaló Boris T. Polyak, los métodos de proyección de subgradiente se parecen a los métodos de gradiente conjugado.
  • El método de descenso de paquetes es una técnica iterativa para problemas de tamaño pequeño a mediano que involucran localmente funciones de Lipschitz, especialmente pertinente para problemas de minimización convexa y que muestra similitudes con los métodos de gradiente conjugado.
  • El método del elipsoide es una técnica iterativa para problemas de pequeña escala que presentan funciones objetivo cuasiconvexas. Posee un interés teórico significativo, en particular para establecer la complejidad temporal polinomial de ciertos problemas de optimización combinatoria, y comparte características con los métodos Quasi-Newton.
  • El método de gradiente condicional (Frank-Wolfe) está diseñado para la minimización aproximada de problemas especialmente estructurados que presentan restricciones lineales, particularmente en el contexto de redes de tráfico. Para problemas generales sin restricciones, este método se simplifica al método de gradiente, que se considera obsoleto para la mayoría de las aplicaciones.
  • Los métodos cuasi-Newton son técnicas iterativas adecuadas para problemas de mediana y gran escala (por ejemplo, normalmente donde N < 1000).
  • El método de aproximación estocástica de perturbación simultánea (SPSA) se aplica en la optimización estocástica, que emplea una aproximación de gradiente aleatoria pero eficiente.
• • Métodos de interpolación
  • Métodos de búsqueda de patrones, que poseen propiedades de convergencia superiores en comparación con la heurística de Nelder-Mead (que utiliza simples).
  • Descenso en espejo

Heurística

Además de los algoritmos de terminación finita y los métodos iterativos convergentes, también existen heurísticas. Una heurística se define como un algoritmo que, si bien no garantiza matemáticamente que localice la solución óptima, resulta valioso en contextos prácticos específicos.

Aplicaciones

Mecánica

Los problemas dentro de la dinámica de cuerpos rígidos, particularmente la dinámica de cuerpos rígidos articulados, frecuentemente requieren técnicas de programación matemática. Esto se debe a que la dinámica de cuerpos rígidos puede conceptualizarse como la resolución de una ecuación diferencial ordinaria en una variedad de restricciones, donde estas restricciones incluyen diversas condiciones geométricas no lineales, por ejemplo, "estos dos puntos siempre deben coincidir", "esta superficie no debe penetrar ninguna otra" o "este punto siempre debe estar en algún lugar de esta curva". Además, el cálculo de las fuerzas de contacto se puede abordar mediante la solución de un problema de complementariedad lineal, que también se puede interpretar como un problema de programación cuadrática (QP).

Numerosos problemas de diseño se formulan con frecuencia como programas de optimización; este dominio se denomina optimización del diseño. La optimización de la ingeniería constituye un subconjunto, mientras que un subcampo distinto y en expansión es la optimización del diseño multidisciplinario, que, aunque ampliamente aplicable, ha encontrado particular utilidad en los problemas de ingeniería aeroespacial.

Este enfoque es aplicable dentro de la cosmología y la astrofísica.

Economía y finanzas

La conexión intrínseca entre la economía y la optimización de los agentes se ve subrayada por una definición influyente que caracteriza la economía qua ciencia como el "estudio del comportamiento humano como una relación entre fines y medios escasos" que posee aplicaciones alternativas. La teoría de la optimización contemporánea abarca enfoques tradicionales y al mismo tiempo se cruza con la teoría de juegos y el análisis de los equilibrios económicos. Dentro del sistema de clasificación del Journal of Economic Literature, la programación matemática, las metodologías de optimización y los temas asociados se clasifican en JEL:C61-C63.

La microeconomía aborda con frecuencia problemas de optimización económica, en particular el problema de maximización de la utilidad y su correspondiente dual, el problema de minimización del gasto. Suponiendo un comportamiento consistente, se supone que los consumidores maximizan su utilidad, mientras que normalmente se supone que las empresas maximizan sus ganancias. Además, con frecuencia se modela a los agentes económicos como reacios al riesgo, lo que indica una preferencia por evitarlo. La teoría de la optimización también se aplica para modelar los precios de los activos, aunque el marco matemático fundamental implica la optimización de procesos estocásticos en lugar de la optimización estática. Además, la teoría del comercio internacional emplea principios de optimización para dilucidar la dinámica comercial entre países. La optimización de la cartera sirve como un ejemplo destacado de optimización multiobjetivo dentro del ámbito económico.

Los economistas han utilizado la teoría del control para modelar procesos dinámicos de toma de decisiones a lo largo del tiempo desde la década de 1970. Por ejemplo, se emplean modelos de búsqueda dinámica para analizar la conducta del mercado laboral. Existe una diferenciación fundamental entre los enfoques de modelización determinista y estocástico. Los macroeconomistas construyen modelos dinámicos de equilibrio general estocástico (DSGE), que caracterizan la dinámica económica general como resultado de las decisiones de optimización interdependientes tomadas por trabajadores, consumidores, inversores y entidades gubernamentales.

Ingeniería eléctrica

Las técnicas de optimización encuentran numerosas aplicaciones dentro de la ingeniería eléctrica, abarcando áreas como el diseño de filtros activos, la mitigación de campos parásitos en sistemas de almacenamiento de energía magnéticos superconductores, el diseño de mapeo espacial para estructuras de microondas, antenas de teléfonos y diseño basado en electromagnetismo. Desde sus inicios en 1993, las metodologías de cartografía espacial, a menudo combinadas con modelos sustitutos empíricos o basados ​​en la física adecuados, se han empleado ampliamente en la optimización del diseño validado electromagnéticamente de antenas y componentes de microondas. Además, las técnicas de optimización son parte integral del análisis del flujo de energía.

Ingeniería civil

Los principios de optimización se aplican ampliamente en diversos ámbitos de la ingeniería civil. En particular, la gestión de la construcción y la ingeniería del transporte representan subdisciplinas clave dentro de la ingeniería civil que exhiben una dependencia sustancial de la optimización. Los desafíos comunes de ingeniería civil abordados mediante la optimización incluyen operaciones de corte y relleno de carreteras, evaluaciones del ciclo de vida de estructuras e infraestructura, nivelación de recursos, distribución de recursos hídricos, gestión del tráfico y optimización de horarios.

Investigación de Operaciones

La investigación de operaciones constituye otra disciplina que emplea ampliamente técnicas de optimización. Este campo también aprovecha el modelado y la simulación estocásticos para facilitar mejores procesos de toma de decisiones. Existe una tendencia creciente en la investigación de operaciones a utilizar programación estocástica para modelar decisiones dinámicas que se ajustan en respuesta a eventos en evolución; estos problemas son susceptibles de soluciones derivadas de optimización a gran escala y metodologías de optimización estocástica.

Ingeniería de control

La optimización matemática juega un papel importante en el diseño de controladores contemporáneo. Los sistemas de control avanzados, incluido el control predictivo de modelos (MPC) y la optimización en tiempo real (RTO), integran la optimización matemática. Al operar en línea, estos algoritmos determinan de manera iterativa valores para variables de decisión (por ejemplo, aberturas de estrangulamiento en una planta de proceso) resolviendo repetidamente un problema de optimización matemática que incorpora restricciones del sistema y un modelo del sistema controlado.

Geofísica

Las técnicas de optimización se aplican habitualmente en los desafíos de estimación de parámetros geofísicos. A partir de un conjunto determinado de mediciones geofísicas, como registros sísmicos, es una práctica estándar deducir las propiedades físicas y las configuraciones geométricas de las rocas y fluidos subterráneos. La mayoría de los problemas geofísicos son inherentemente no lineales, lo que requiere la aplicación generalizada de metodologías tanto deterministas como estocásticas.

Modelado molecular

Las metodologías de optimización no lineal se emplean ampliamente en el campo del análisis conformacional.

Biología de sistemas computacionales

Las metodologías de optimización se emplean ampliamente en varios dominios dentro de la biología de sistemas computacionales, abarcando la construcción de modelos, el diseño de experimentos óptimos, la ingeniería metabólica y la biología sintética. Específicamente, se ha utilizado la programación lineal para determinar los rendimientos máximos alcanzables de productos de fermentación y para deducir redes reguladoras de genes a partir de diversos conjuntos de datos de microarrays, junto con redes reguladoras transcripcionales derivadas de datos de alto rendimiento. Además, la programación no lineal ha sido fundamental en el análisis del metabolismo energético y su aplicación a la ingeniería metabólica y la estimación de parámetros dentro de rutas bioquímicas.

Aprendizaje automático

Solucionadores

Notas

Notas

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa. Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-83378-7.

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa. Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-83378-7.Gill, P. E.; Murray, W.; Wright, M. H. (1982). Optimización práctica. Londres: Academic Press. ISBN 0-12-283952-8.Lee, Jon (2004). Un primer curso en optimización combinatoria. Prensa de la Universidad de Cambridge. ISBN 0-521-01012-8.Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín: Springer. ISBN 0-387-30303-0.
  • "Árbol de decisiones para software de optimización"."EE364a: Optimización convexa I". Curso de la Universidad de Stanford.Varoquaux, Gaël. "Optimización matemática: búsqueda de mínimos de funciones".Fuente: Archivo de la Academia TORIma