El algoritmo dicotómico en optimización: Dividir para encontrar el mínimo

Imagen de Thomas Wolter extraída de Unsplash

El Método Dicotómico (o Búsqueda Dicotómica) es uno de los algoritmos secuenciales directos más populares en optimización numérica unidimensional. A diferencia de la Búsqueda Uniforme, que evalúa todos los puntos de forma simultánea a lo largo de una malla, el método dicotómico aprovecha la información obtenida en cada paso para dividir aproximadamente a la mitad el intervalo de incertidumbre en cada iteración, garantizando una convergencia más rápida sin calcular derivadas.

A mediados del siglo XX, con la sistematización de la investigación operativa por autores como Douglass J. Wilde (1964) (Wilde, 1964), el método dicotómico se estableció como el puente conceptual perfecto entre la exploración a ciegas por malla y los algoritmos secuenciales de eficiencia óptima como la Búsqueda de la Sección Áurea.

El algoritmo dicotómico

El objetivo del algoritmo es minimizar una función continua y unimodal $f(x)$ dentro de un intervalo inicial $[a, b]$.

En lugar de evaluar un solo punto en el centro del intervalo $m = \frac{a + b}{2}$ (lo cual no aportaría información sobre la pendiente de la curva), el método evalúa un par de puntos extremadamente cercanos separados por una pequeña distancia $2\delta$ ($\delta > 0$):

Cálculo del punto medio: Se determina el centro del intervalo actual $[a_k, b_k]$: $m_k = \frac{a_k + b_k}{2}$
Generación del par de prueba: Se definen dos puntos simétricos respecto al punto medio utilizando una tolerancia escalar pequeña $\delta > 0$: $x_1 = m_k - \delta \quad \text{y} \quad x_2 = m_k + \delta$
Evaluación de la función: Se calculan los valores $f(x_1)$ y $f(x_2)$.
Regla de reducción del intervalo:
- Si $f(x_1) < f(x_2)$, la unimodalidad garantiza que el mínimo no puede estar en $[x_2, b_k]$. Se descarta esa mitad y el nuevo intervalo pasa a ser $[a_{k+1}, b_{k+1}] = [a_k, x_2]$.
- Si $f(x_1) > f(x_2)$, el mínimo no está en $[a_k, x_1]$. Se descarta esa región y el nuevo intervalo pasa a ser $[a_{k+1}, b_{k+1}] = [x_1, b_k]$.

La nueva longitud del intervalo tras cada iteración se reduce a $L_{k+1} = \frac{b_k - a_k}{2} + \delta$. Es decir, el intervalo no se divide exactamente por la mitad: las longitudes decrecen geométricamente hacia una anchura límite de $2\delta$. Por ello, la tolerancia de parada $\varepsilon$ debe cumplir $\varepsilon > 2\delta$; en caso contrario, el bucle nunca terminaría.

Pseudocódigo

A continuación se presenta la formulación algorítmica estructurada:

\begin{algorithm}
\caption{Búsqueda Dicotómica Unidimensional}
\begin{algorithmic}
\PROCEDURE{BusquedaDicotomica}{$$f, a, b, delta, epsilon$$}
    \STATE $$ak = a$$
    \STATE $$bk = b$$
    \WHILE{$$(bk - ak) > epsilon$$}
        \STATE $$m = (ak + bk) / 2$$
        \STATE $$x1 = m - delta$$
        \STATE $$x2 = m + delta$$
        \IF{$$f(x1) < f(x2)$$}
            \STATE $$bk = x2$$
        \ELSE
            \STATE $$ak = x1$$
        \ENDIF
    \ENDWHILE
    \STATE $$xopt = (ak + bk) / 2$$
    \RETURN $$xopt, f(xopt), [ak, bk]$$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Ejemplo numérico

Para comparar la eficiencia directamente con el post de Búsqueda Uniforme, consideremos la función no lineal:

\[f(x) = x^2 - 3,2x + 3\]

en el intervalo $[a; b] = [0; 3]$. Fijaremos un margen de perturbación $\delta = 0,1$.

Analíticamente, el mínimo exacto se encuentra en $x^* = 1,6$ con $f(1,6) = 0,44$.

Las iteraciones usando el método dicotómico para este ejemplo son:

Iteración 1:

Intervalo inicial: $[a_0; b_0] = [0; 3]$ (Longitud $L_0 = 3,0$).
Punto medio: $m_0 = (0 + 3)/2 = 1,5$.
Puntos de prueba:
- $x_1 = 1,5 - 0,1 = 1,4 \implies f(1,4) = 0,48$
- $x_2 = 1,5 + 0,1 = 1,6 \implies f(1,6) = 0,44$
Decisión: Como $f(1,4) > f(1,6)$, descartamos la región $[0; 1,4]$.
Nuevo intervalo: $[a_1; b_1] = [1,4; 3,0]$ (Longitud $L_1 = 1,6$).

Iteración 2:

Intervalo actual: $[a_1, b_1] = [1,4; 3,0]$.
Punto medio: $m_1 = (1,4 + 3,0)/2 = 2,2$.
Puntos de prueba:
- $x_1 = 2,2 - 0,1 = 2,1 \implies f(2,1) = 0,69$
- $x_2 = 2,2 + 0,1 = 2,3 \implies f(2,3) = 0,93$
Decisión: Como $f(2,1) < f(2,3)$, descartamos la región $[2,3; 3,0]$.
Nuevo intervalo: $[a_2; b_2] = [1,4; 2,3]$ (Longitud $L_2 = 0,9$).

Iteración 3:

Intervalo actual: $[a_2; b_2] = [1,4; 2,3]$.
Punto medio: $m_2 = (1,4 + 2,3)/2 = 1,85$.
Puntos de prueba:
- $x_1 = 1,85 - 0,1 = 1,75 \implies f(1,75) = 0,4625$
- $x_2 = 1,85 + 0,1 = 1,95 \implies f(1,95) = 0,5625$
Decisión: Como $f(1,75) < f(1,95)$, descartamos la región $[1,95; 2,3]$.
Nuevo intervalo: $[a_3; b_3] = [1,4; 1,95]$ (Longitud $L_3 = 0,55$).

Resultado: En tan solo 3 iteraciones (6 evaluaciones de la función, sin contar la evaluación final de $f(x_{opt})$ del pseudocódigo), el intervalo inicial de longitud $3,0$ se ha reducido a $0,55$, garantizando que el óptimo $x^* = 1,6$ reside en $[1,4; 1,95]$.

Si se usara el método de la Búsqueda Uniforme, se requieren 7 evaluaciones para lograr una reducción similar a un intervalo de longitud $1,0$.

Estas tres iteraciones se observan gráficamente en la siguiente figura:

Análisis técnico: Búsqueda Dicotómica vs. Búsqueda Uniforme

La diferencia fundamental entre ambos métodos radica en su velocidad de convergencia respecto al número de evaluaciones numéricas $N$:

Búsqueda Uniforme (Simultánea): La reducción del intervalo es lineal, con una razón $R_N = \frac{2}{N-1}$.
Método Dicotómico (Secuencial): Si se realizan $k$ iteraciones ($N = 2k$ evaluaciones), la longitud del intervalo final es aproximadamente:
\[L_k \approx \frac{b - a}{2^k} + 2\delta \left(1 - \frac{1}{2^k}\right)\]

Esta convergencia del método dicotómico permite alcanzar tolerancias de precisión muy estrictas (por ejemplo, $\varepsilon = 10^{-4}$, eligiendo un $\delta$ suficientemente pequeño como $10^{-5}$) con apenas 30 evaluaciones de la función, mientras que la Búsqueda Uniforme requeriría decenas de miles.

Ventajas y Limitaciones

Ventajas:
- Eficiencia extrema: Reduce drásticamente el espacio de búsqueda en muy pocas evaluaciones.
- Sin derivadas: Solo requiere evaluaciones de la función. No obstante, la garantía sobre el intervalo exige que la función sea continua y unimodal.
Limitaciones:
- Naturaleza secuencial: No es tan fácil de paralelizar masivamente como la Búsqueda Uniforme, ya que cada par de evaluaciones depende del resultado anterior.
- Redundancia: Evalúa 2 puntos por paso (otros métodos más avanzados logran reutilizar puntos para requerir sólo una evaluación por paso tras la primera iteración).

El Método Dicotómico representa el puente fundamental entre el muestreo ciego por malla y los métodos secuenciales avanzados. Al aprovechar la información de cada paso para bisecar el intervalo sin calcular derivadas, demuestra que la clave de la eficiencia algorítmica radica en saber descartar inteligentemente la mitad del problema en cada decisión.

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.