Problema de optimización

Problema de encontrar la mejor solución factible

En matemáticas , ingeniería , informática y economía , un problema de optimización es el problema de encontrar la mejor solución entre todas las soluciones posibles .

Los problemas de optimización se pueden dividir en dos categorías, dependiendo de si las variables son continuas o discretas :

Un problema de optimización con variables discretas se conoce como optimización discreta , en la que un objeto como un entero , una permutación o un gráfico debe encontrarse en un conjunto contable .
Un problema con variables continuas se conoce como optimización continua , en el que se debe encontrar un valor óptimo a partir de una función continua . Pueden incluir problemas restringidos y problemas multimodales.

Problema de optimización continua

La forma estándar de un problema de optimización continua es ^[1] donde ${\begin{aligned}&{\underset {x}{\operatorname {minimizar} }}&&f(x)\\&\operatorname {sujeto\;a} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}$

$f : ℝ n \to ℝ$ es la función objetivo a minimizar sobre elvector $x$ $de n$ variables ,
$g i (x) \leq 0$ se denominan restricciones de desigualdad
$h j (x) = 0$ se denominan restricciones de igualdad , y
$m \geq 0$ y $p \geq 0$ .

Si $m = p = 0$ , el problema es un problema de optimización sin restricciones. Por convención, la forma estándar define un problema de minimización . Un problema de maximización se puede tratar negando la función objetivo.

Problema de optimización combinatoria

Formalmente, un problema de optimización combinatoria $A$ es un cuádruple ^{[ cita requerida ]} $(I, f, m, g)$ , donde

$Yo$ soy un conjunto de instancias;
dada una instancia $x \in I$ , $f (x)$ es el conjunto de soluciones factibles;
dada una instancia $x$ y una solución factible $y$ de $x$ , $m (x, y)$ denota la medida de $y$ , que usualmente es un número real positivo .
$g$ es la función objetivo y puede ser $min$ o $max$ .

El objetivo es entonces encontrar para alguna instancia $x$ una solución óptima , es decir, una solución factible $y$ con $m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.$

Para cada problema de optimización combinatoria, existe un problema de decisión correspondiente que pregunta si existe una solución factible para alguna medida particular $m 0$ . Por ejemplo, si hay un grafo $G$ que contiene vértices $u$ y $v$ , un problema de optimización podría ser "encontrar un camino de $u$ a $v$ que use la menor cantidad de aristas". Este problema podría tener una respuesta de, digamos, 4. Un problema de decisión correspondiente sería "¿hay un camino de $u$ a $v$ que use 10 o menos aristas?" Este problema puede responderse con un simple 'sí' o 'no'.

En el campo de los algoritmos de aproximación , los algoritmos están diseñados para encontrar soluciones casi óptimas a problemas difíciles. La versión de decisión habitual es entonces una definición inadecuada del problema, ya que solo especifica soluciones aceptables. Aunque podríamos introducir problemas de decisión adecuados, el problema se caracteriza más naturalmente como un problema de optimización. ^[2]

Véase también

Problema de conteo (complejidad) – Tipo de problema computacional
Optimización del diseño
Principio variacional de Ekeland : teorema que afirma que existen soluciones casi óptimas para algunos problemas de optimización.Páginas que muestran descripciones de wikidata como alternativa
Problema de función – Tipo de problema computacional
Problema con los guantes
Investigación de operaciones – Disciplina relativa a la aplicación de métodos analíticos avanzados
Satisfactorio – Heurística cognitiva de búsqueda de una decisión aceptable: no es necesario encontrar la óptima, sólo una solución “suficientemente buena”.
Problema de búsqueda : tipo de problema computacional representado por una relación binariaPáginas que muestran descripciones de wikidata como alternativa
Programación semi-infinita : problema de optimización con un número finito de variables y un número infinito de restricciones, o un número infinito de variables y un número finito de restriccionesPáginas que muestran descripciones de wikidata como alternativa

Referencias

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Cambridge University Press. pág. 129. ISBN 978-0-521-83378-3.
^ Ausiello, Giorgio; et al. (2003), Complejidad y aproximación (edición corregida), Springer, ISBN 978-3-540-65431-5

Enlaces externos

"Cómo la modelación del tráfico optimiza el ancho de banda de la red". IPC . 12 de julio de 2016 . Consultado el 13 de febrero de 2017 .

[1] Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Cambridge University Press. pág. 129. ISBN 978-0-521-83378-3.

[Ausiello03-2] Ausiello, Giorgio; et al. (2003), Complejidad y aproximación (edición corregida), Springer, ISBN 978-3-540-65431-5