Optimización (matemática)

Gráfico de un paraboloide dado por f(x,y) = -(x²+y²)+4. El máximo global en (0, 0, 4) está indicado por un punto rojo.

En matemáticas, estadísticas, ciencias empíricas, ciencia de la computación, o economía, optimización matemática (o bien, optimización o programación matemática) es la selección del mejor elemento (con respecto a algún criterio) de un conjunto de elementos disponibles.[1]

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 (tomados de un conjunto permitido) y computando el valor de la función. La generalización de la teoría de la optimización y técnicas para otras formulaciones comprende un área grande de las matemáticas aplicadas. De forma general, la optimización incluye el descubrimiento de los "mejores valores" de alguna función objetivo dado un dominio definido, incluyendo una variedad de diferentes tipos de funciones objetivo y diferentes tipos de dominios.

Problemas de Optimización

Un problema de optimización puede ser representado de la siguiente forma

Dada: una función f : A \to R donde A es un conjunto de números reales.
Buscar: un elemento x0 en A tal que f(x0) ≤ f(x) para todo x en A ("minimización") o tal que f(x0) ≥ f(x) para todo x en A ("maximización").

Tal formulación es llamada un problema de optimización o un problema de programación matemática (un término no directamente relacionado a la programación de computadoras, pero todavía en uso por ejemplo en la programación lineal - ver Historia debajo). Muchos problemas teóricos y del mundo real pueden ser modelados en este esquema general. Problemas formulados usando esta técnica en los campos de física y visión por computadora se refieren a la técnica como minimización de la energía, hablando del valor de la función f representando la energía del sistema que está siendo modelado.

Típicamente, A es algún subconjunto del espacio Euclidiano Rn, con frecuencia especificado por un conjunto de restricciones, igualdades o desigualdades que los elementos de A tienen que satisfacer. El dominio A de f es llamado el espacio de búsqueda o el conjunto de elección, mientras que los elementos de A son llamados soluciones candidatas o soluciones factibles.

La función f es llamada, diversamente, una función objetivo, función de costo (minimización),[2] función de utilidad indirecta (minimización),[3] función de utilidad (maximización), o, en ciertos campos, función de energía, o energía funcional. Una solución factible que minimice (o maximice, si este es el propósito) la función objetivo, es llamada una solución óptima.

Por convenio, el formato estándar de un problema de optimización está declarado en términos de minimización. Generalmente, a menos que ambas, la función objetivo y la región factible sean convexas en un problema de minimización, puede haber varios mínimos locales, donde un mínimo local x* se define como un punto para el cual existe algún δ > 0, donde para todo x tal que

\|\mathbf{x}-\mathbf{x}^*\|\leq\delta\,

la expresión

f(\mathbf{x}^*)\leq f(\mathbf{x})

es verdadera; es decir, en alguna región alrededor de x* todos los valores de la función son mayores que o iguales al valor en ese punto. El máximo local se define de modo similar.

Un gran número de algoritmos propuestos para resolver problemas no-convexos – incluyendo a la mayoría de los solucionadores disponibles comercialmente – no son capaces de hacer una distinción entre soluciones óptimas locales y soluciones óptimas rigurosas, y tratan a las primeras como soluciones actuales del problema original. La rama de las matemáticas aplicadas y el análisis numérico que se responsabiliza con el desarrollo de algoritmos deterministas que son capaces de garantizar convergencia en tiempo finito a la solución óptima real de un problema no-convexo se llama optimización global.

Notación

Los problemas de optimización se expresan a menudo con una notación especial. A continuación se muestran algunos ejemplos.

Mínimo y Máximo valor de una función

Considere la siguiente notación:

\min_{x\in\mathbb R}\; (x^2 + 1)

Esta denota el valor mínimo de la función objetivo x^2 + 1, cuando x se selecciona del conjunto de números reales \mathbb R. El valor mínimo en este caso es 1 y ocurre para x = 0.

De modo similar, la notación

\max_{x\in\mathbb R}\; 2x

pregunta por el valor máximo de la función objetivo 2x, cuando x puede ser cualquier número real. En este caso, no existe tal máximo si la función objetivo es infinita, luego la respuesta es "infinito"o "indefinido".

Argumentos de la entrada óptima

Considere la siguiente notación:

\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1,

o de manera equivalente

\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{subject to:} \; x\in(-\infty,-1].

Esta representa el valor (o valores) del argumento de x en el intervalo (-\infty,-1] que minimiza (o minimizan) la función objetivo x2 + 1 (el valor del mínimo actual de esta función no es por quien el problema pregunta). En este caso, la respuesta es x = -1, puesto que x = 0 no es factible, es decir no pertenece al conjunto factible.

De modo similar,

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

o de manera equivalente

\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos(y), \; \text{subject to:} \; x\in[-5,5], \; y\in\mathbb R,

representa al par (x,y) (o pares) que maximiza (o maximizan) el valor de la función objetivo x\cos(y), con la restricción añadida de que x se encuentra en el intervalo [-5,5] (nuevamente, el valor del máximo actual de la expresión no importa). En este caso, las soluciones son los pares de la forma (5, 2kπ) y (−5,(2k+1)π), donde k recorre a todos los enteros.

Arg min y arg max a veces aparecen escritos como argmin y argmax, y quieren decir argumento del mínimo y argumento del máximo.

Historia

Pierre de Fermat y Joseph Louis Lagrange encontraron cálculos basados en fórmulas identificadas como óptimas, mientras que Isaac Newton y Carl Friedrich Gauss propusieron métodos iterativos para el movimiento hacia un óptimo. Históricamente, el primer término para la optimización fue programación lineal, debido a George B. Dantzig, aunque mucho de la teoría había sido introducida por Leonid Kantorovich en 1939. Dantzig publicó el algoritmo Simplex (Simple) en 1947 y John von Neumann desarrolló la teoría de la dualidad en el mismo año.

El término programación en este contexto no se refiere a la programación de computadoras. Más bien, el término viene del uso de programa por el ejército de Estados Unidos al referirse a la propuesta de entrenamiento y planificación logística, el cual fue el problema estudiado por Dantzig en aquel entonces.

Otros investigadores importantes en la optimización matemática son los siguientes:

  • Arkadi Nemirovski
  • Yurii Nesterov
  • Boris Polyak
  • Lev Pontryagin
  • James Renegar
  • R. Tyrrell Rockafellar
  • Cornelis Roos
  • Naum Z. Shor
  • Michael J. Todd
  • Albert Tucker

Subcampos Principales

En un número de subcampos, las técnicas son diseñadas principalmente para la optimización en contextos dinámicos (es decir, toma de decisiones con el transcurso del tiempo):

Clasificación de puntos críticos y extremos

Factibilidad del problema

La satisfabilidad del problema, también llamada la factibilidad del problema, es justo el problema de encontrar alguna solución factible de todas sin hacer caso del valor objetivo. Este puede ser considerado como el caso especial de la optimización matemática donde el valor objetivo es el mismo para toda solución, y así cualquier solución es óptima.

Muchos algoritmos de optimización necesitan comenzar a partir de un punto factible. Una vía para obtener tal punto es relajar las condiciones de factibilidad usando una variable de holgura; con suficiente holgura, cualquier punto de partida es factible. Entonces, se minimiza esa variable de holgura hasta que la holgura sea nula o negativa.

Existencia

El teorema del valor extremo de Karl Weierstrass afirma que una función real y continua en un conjunto compacto alcanza su valor máximo y mínimo. De forma más general, una función semi-continua inferior en un conjunto compacto alcanza su mínimo; una función semi-continua superior en un conjunto compacto alcanza su máximo.

Condiciones necesarias de optimalidad

Uno de los teoremas de Fermat asegura que los óptimos de los problemas irrestrictos son encontrados en los puntos estacionarios, donde la primera derivada o el gradiente de la función objetivo es cero. De forma más general, ellos pueden ser encontrados en los puntos críticos, donde la primera derivada o el gradiente de la función objetivo es cero o está indefinido, o en la frontera del conjunto de elección. Una ecuación (o conjunto de ecuaciones) indicando que la(s) primera(s) derivada(s) es(son) igual(es) a cero en un óptimo interior se llama una condición de primer orden o un conjunto de condiciones de primer orden.

Los óptimos de los problemas con restricciones de desigualdad son en cambio encontrados mediante el método de los multiplicadores de Lagrange. Este método computa un sistema de desigualdades llamado Condiciones de Karush–Kuhn–Tucker o condiciones de holguras complementarias, las cuales se usan entonces para calcular el óptimo.

Condiciones suficientes de optimalidad

Mientras la prueba de la primera derivada identifica los puntos que pueden ser extremos, esta prueba no distingue si un punto es mínimo, máximo, o ninguno de los dos. Cuando la función objetivo es dos veces diferenciable, estos casos pueden ser distinguidos estudiando la segunda derivada o la matriz de las segundas derivadas (llamada matriz Hessiana) en problemas irrestrictos, o la matriz de las segundas derivadas de la función objetivo y las restricciones llamada la frontera Hessiana en problemas restrictos.

Las condiciones que distinguen a los máximos, o mínimos, de otros puntos estacionarios son llamadas condiciones de segundo orden. Si un candidato a solución satisface las condiciones de primer orden y las condiciones de segundo orden también, es suficiente para establecer, al menos, optimalidad local.

Sensibilidad y continuidad del óptimo

El teorema de la envoltura describe como el valor de una solución óptima cambia cuando un parámetro subyacente cambia. El proceso que computa este cambio es llamado estática comparativa.

El teorema del máximo de Claude Berge (1963) describe la continuidad de una solución óptima como una función de parámetros subyacentes.

Cálculos de optimización

Para los problemas irrestrictos con funciones dos veces diferenciables, algunos puntos críticos pueden ser encontrados detectando los puntos donde el gradiente de la función objetivo es cero (es decir, los puntos estacionarios). De forma más general, un subgradiente cero certifica que un mínimo local ha sido encontrado para los problemas de minimización con funciones convexas y localmente otras funciones de Lipschitz.

Además, los puntos críticos pueden ser clasificados usando la concreción de la matriz Hessiana: si la Hessiana es definida positiva en un punto crítico, entonces el punto es un mínimo local; si la Hessiana es definida negativa, entonces el punto es un máximo local; finalmente, si es indefinida, entonces el punto es algún tipo de punto de ensilladura.

Los problemas restrictos pueden con frecuencia ser transformados en problemas irrestrictos con ayuda de los multiplicadores de Lagrange. La relajación Lagrangiana puede también proveer soluciones aproximadas a difíciles problemas restrictos.

Cuando la función objetivo es convexa, entonces cualquier mínimo local será también un mínimo global. Existen técnicas numéricas eficientes para minimizar funciones convexas, por ejemplo los métodos de punto interior.

Técnicas de optimización computacional

Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).

Algoritmos de optimización

Métodos iterativos

Los métodos iterativos usados para resolver problemas de programación no lineal difieren según lo que ellos evalúen: Hessianas, gradientes, o solamente valores de función. Mientras que evaluando Hessianas (H) y gradientes (G) mejora la velocidad de convergencia, tales evaluaciones aumentan la complejidad computacional (o costo computacional) de cada iteración. En algunos casos, la complejidad computacional puede ser excesivamente alta.

Un importante criterio para los optimizadores es justo el número de evaluaciones de funciones requerido, como este con frecuencia es de por sí un gran esfuerzo computacional, usualmente mucho más esfuerzo que el del optimizador en sí, ya que en su mayoría tiene que operar sobre N variables. Las derivadas proveen información detallada para los optimizadores, pero son aún más costosas de calcular, por ejemplo aproximando el gradiente toma al menos N+1 evaluaciones de funciones. Para la aproximación de las segundas derivadas (agrupadas en la matriz Hessiana) el número de evaluaciones de funciones es de orden N². El método de Newton requiere las derivadas de Segundo orden, por lo tanto por cada iteración el número de llamadas a función es de orden N², pero para el optimizador de un gradiente puro más simple es de orden N. Sin embargo, los optimizadores de gradiente necesitan usualmente más iteraciones que el algoritmo de Newton. Ser mejor con respecto al número de llamadas a funciones depende del problema en sí.

Convergencia global

De modo general, si la función objetivo no es una función cuadrática, entonces muchos métodos de optimización usan otros métodos para garantizar que alguna subsecuencia de iteraciones converge a una solución óptima. El primer método popular que garantiza convergencia se apoya en búsquedas lineales, el cual optimiza una función en una dimensión. Un segundo y popularizado método para garantizar convergencia usa regiones de confianza. Ambos búsquedas lineales y regiones de confianza son usados en métodos modernos de optimización no diferenciable. Usualmente un optimizador global es mucho más lento que los optimizadores locales avanzados (por ejemplo BFGS), por lo tanto con frecuencia un optimizador global eficiente puede ser construido por el inicio del optimizador local de diferentes puntos de partida.

Heurísticas

Además de los algoritmos (terminación finita) y los métodos iterativos (convergentes), existen heurísticas que pueden proveer soluciones aproximadas a algunos problemas de optimización:

Véase también

Referencias

  1. "The Nature of Mathematical Programming," Mathematical Programming Glossary, INFORMS Computing Society.
  2. W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents.
  3. Peter Newman (2008). "indirect utility function," The New Palgrave Dictionary of Economics, 2nd Edition. Contents.

Enlaces externos

This article is issued from Wikipedia - version of the Friday, January 15, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.