thumb| 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ística, economía, ciencias empíricas y ciencia de la computación, la optimización (también, optimización matemática o programación matemática) es la selección del mejor elemento (con respecto a algún criterio) de un conjunto de elementos disponibles. La investigación operativa es uno de los campos de la matemática en cuyas bases funciona la optimización."The Nature of Mathematical Programming," Mathematical Programming Glossary, INFORMS Computing Society.

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.

Optimización hace referencia a la acción y efecto de optimizar. En términos generales, se refiere a la capacidad de hacer o resolver alguna cosa de la manera más eficiente posible y, en el mejor de los casos, utilizando la menor cantidad de recursos.

En las últimas décadas, el término optimización se ha vinculado al mundo de la informática. Sin embargo, es un concepto que también se utiliza en las matemáticas, en la gestión de procesos y la economía.

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

Dada: una función f : A R. 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 con la programación de computadoras pero todavía en uso, por ejemplo en la programación lineal - véase la sección Historia). Muchos problemas teóricos y del mundo real pueden ser modelados mediante 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 euclídeo Rn, con frecuencia delimitado 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, función objetivo, función de costo (minimización),W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents. función de utilidad (maximización), función de utilidad indirecta (minimización),Peter Newman (2008). "indirect utility function," The New Palgrave Dictionary of Economics, 2nd Edition. Contents. 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

la expresión

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:

Esta denota el valor mínimo de la función objetivo , cuando x se selecciona del conjunto de números reales . El valor mínimo en este caso es y ocurre para .

De modo similar, la notación

expresa el valor máximo de la función objetivo 2x, siendo x cualquier número real. En este caso, no existe tal máximo, luego no hay un valor óptimo acotado.

Argumentos de la entrada óptima

Considérese la siguiente expresión:

o de manera equivalente

Esta representa el valor (o valores) del argumento de x en el intervalo que minimizan (o maximizan) la función objetivo x2 + 1 (y no el valor mínimo que alcanza la función objetivo para dichos valores). En este caso, la respuesta es x = -1, puesto que x = 0 no es factible, es decir no pertenece al dominio del problema.

De modo similar,

que equivalente a

representa al par (o pares) (x,y) que minimizan (o maximizan) el valor de la función objetivo xcos(y), con la restricción añadida de que x se encuentra en el intervalo [-5,5] (nuevamente, el valor mínimo de la función no importa). En este caso, las soluciones son los pares de la forma (5, 2kπ) y (−5,(2k+1)π), donde k recorre 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 fórmulas basadas en el cálculo para identificar valores óptimos, mientras que Isaac Newton y Carl Friedrich Gauss propusieron métodos iterativos para aproximar el óptimo. Históricamente, el término programación lineal para referirse a ciertos problemas de optimización se debe a George B. Dantzig, aunque gran parte de la teoría había sido introducida por Leonid Kantorovich en 1939. Dantzig publicó el Algoritmo símplex 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 el campo de la optimización matemática fueron los siguientes:

Richard Bellman Ronald A. Howard Narendra Karmarkar William Karush Leonid Khachiyan Bernard Koopman Harold W. Kuhn Joseph Louis Lagrange László Lovász

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

Subcampos principales

Programación convexa estudia el caso en que la función objetivo es convexa (minimización) o cóncava (maximización) y el conjunto de restricciones es convexo. Este puede ser visto como un caso particular de la programación no lineal o como la generalización de la programación lineal o de la convexa cuadrática. Programación lineal (PL): es un tipo de programación convexa, en el que la función objetivo f es lineal y el conjunto de restricciones se especifica usando solamente ecuaciones e inecuaciones lineales. Dicho conjunto es llamado poliedro o politopo si está acotado. Programación cónica: es una forma general de la programación convexa. PL, PCSO y PSD pueden todos ser vistos como programas cónicos con el tipo de cono apropiado. Programación de cono de segundo orden (PCSO): es un tipo de programación convexa e incluye ciertos tipos de problemas de programación cuadrática. Programación semidefinida (PSD): es un subcampo de la optimización convexa donde las variables fundamentales son matrices semidefinidas. Es una generalización de la programación lineal y la programación cuadrática convexa. Programación geométrica: es una técnica por medio de la cual el objetivo y las restricciones de desigualdad expresados como polinomios y las restricciones de igualdad como monomios, pueden ser transformados en un programa convexo. Programación con enteros o Programación entera: estudia programas lineales en los cuales algunas o todas las variables están obligadas a tomar valores enteros. Esta no es convexa y en general es mucho más compleja que la programación lineal regular. Programación cuadrática: permite a la función objetivo tener términos cuadráticos, mientras que el conjunto factible puede ser especificado con ecuaciones e inecuaciones lineales. Para formas específicas del término cuadrático, esta es un tipo de programación convexa. Programación fraccionaria: estudia la optimización de razones de dos funciones no lineales. La clase especial de programas fraccionarios cóncavos puede ser transformada a un problema de optimización convexa. Programación no lineal: estudia el caso general en el que la función objetivo, o las restricciones, o ambos, contienen partes no lineales. Este puede o no, ser un programa convexo. En general, si el programa es convexo afecta la dificultad de resolución. Programación estocástica u Optimización estocástica: estudia el caso en el que alguna de las restricciones o parámetros depende de variables aleatorias. Programación robusta: como la programación estocástica, es un intento por capturar la incertidumbre en los datos fundamentales del problema de optimización. Esto se hace mediante el uso de variables aleatorias, pero en cambio, el problema es resuelto teniendo en cuenta imprecisiones en los datos de entrada. Optimización combinatoria: se preocupa de los problemas donde el conjunto de soluciones factibles es discreto o puede ser reducido a uno. Optimización dimensional-infinita: estudia el caso donde el conjunto de soluciones factibles es un subconjunto de un espacio de dimensión infinita, por ejemplo un espacio de funciones. Heurísticas y Metaheurísticas: hacen suposiciones sobre el problema que está siendo optimizado. Usualmente, las heurísticas no garantizan que cualquier solución óptima sea encontrada. Luego, las heurísticas son usadas para encontrar soluciones aproximadas para muchos problemas de optimización complicados. Satisfacción de restricción: estudia el caso en el cual la función objetivo f es constante (esta es usada en inteligencia artificial, particularmente en razonamiento automatizado). Programación disyuntiva: se usa cuando al menos una restricción puede ser satisfecha pero no todas. Esta es de uso particular en la programación 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). Cálculo de variaciones: busca optimizar un objetivo definido sobre muchos puntos con el tiempo, considerando como la función objetivo cambia si el cambio es pequeño en el camino de elección. La técnica del control óptimo es una generalización de este. Programación dinámica estudia el caso en el que la estrategia de optimización se basa en la división del problema en subproblemas más pequeños. La ecuación que describe la relación entre estos subproblemas se llama ecuación de Bellman.