Problema de optimización

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 factibles .

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 se debe encontrar un objeto , como un número entero , una permutación o un grafo, a partir de un conjunto contable .
Un problema con variables continuas se conoce como optimización continua , en la que se debe encontrar un valor óptimo a partir de una función continua . Estos problemas pueden incluir problemas con restricciones y problemas multimodales.

Espacio de búsqueda

En el contexto de un problema de optimización, el espacio de búsqueda se refiere al conjunto de todos los puntos o soluciones posibles que satisfacen las restricciones, objetivos o metas del problema. ^{[ 1 ]} Estos puntos representan las soluciones factibles que pueden evaluarse para encontrar la solución óptima según la función objetivo. El espacio de búsqueda suele definirse mediante el dominio de la función que se está optimizando, abarcando todas las entradas válidas que cumplen los requisitos del problema. ^{[ 2 ]}

El espacio de búsqueda puede variar significativamente en tamaño y complejidad según el problema. Por ejemplo, en un problema de optimización continua, el espacio de búsqueda podría ser un dominio multidimensional de valores reales definido por límites o restricciones. En un problema de optimización discreta, como la optimización combinatoria, el espacio de búsqueda podría consistir en un conjunto finito de permutaciones, combinaciones o configuraciones.

En algunos contextos, el término espacio de búsqueda también puede referirse a la optimización del dominio en sí, como determinar el conjunto más apropiado de variables o parámetros para definir el problema. Comprender y explorar eficazmente el espacio de búsqueda es fundamental para diseñar algoritmos eficientes, ya que influye directamente en la complejidad computacional y en la probabilidad de encontrar una solución óptima.

problema de optimización continua

La forma estándar de un problema de optimización continua es ^{[ 3 ].} ${\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}}$ dónde

$f : ℝ n \to ℝ$ es la función objetivo que se debe minimizar sobre elvector $de n variables$ $x$ ,
$Las restricciones g i (x) \leq 0$ se denominan restricciones de desigualdad .
$Las restricciones de igualdad 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 puede tratarse negando la función objetivo.

Problema de optimización combinatoria

Formalmente, un problema de optimización combinatoria $A$ es una cuádrupla $($ $I$ $,$ $f$ $,$ $m$ $,$ $g$ $)$ , donde

$Yo$ es 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 suele ser un número real positivo .
$g$ es la función objetivo, y es $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 utilice el menor número de aristas". Este problema podría tener una respuesta de, digamos, 4. Un problema de decisión correspondiente sería "¿existe un camino de $u$ a $v$ que utilice 10 o menos aristas?". Este problema se puede responder con un simple "sí" o "no".

En el campo de los algoritmos de aproximación , estos se diseñan para encontrar soluciones casi óptimas a problemas complejos. La versión habitual de decisión resulta, por lo tanto, una definición inadecuada del problema, ya que solo especifica soluciones aceptables. Si bien podríamos introducir problemas de decisión apropiados, el problema se caracteriza de forma más natural como un problema de optimización. ^{[ 4 ]}

Véase también

Problema de conteo (complejidad) – Tipo de problema computacional
Optimización del diseño
El principio variacional de Ekeland
Problema de función – Tipo de problema computacional
Problema del guante : problema de optimización en investigación operativa
Investigación operativa : 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 solución óptima, sino simplemente una solución "suficientemente buena".
Problema de búsqueda – Clase de problemas computacionales
Programación semiinfinita

Referencias

↑ "Espacio de búsqueda" . courses.cs.washington.edu . Consultado el 10 de mayo de 2025 .
↑ "Espacio de búsqueda - LessWrong" . www.lesswrong.com . 22 de septiembre de 2020. Consultado el 10 de mayo de 2025 .
↑ 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), Complexity and Approximation ( Edición corregida), Springer, ISBN 978-3-540-65431-5