El método de la sección áurea en optimización: la proporción divina al servicio del mínimo

Imagen de Hao Chen extraída de Unsplash

El Método de la Sección Áurea (o Búsqueda de la Sección Áurea, Golden Section Search) es uno de los algoritmos secuenciales directos más elegantes y eficientes de la optimización numérica unidimensional. Al igual que el Método de Búsqueda Dicotómica, aprovecha la información de cada paso para descartar parte del intervalo de incertidumbre sin calcular derivadas. Sin embargo, en lugar de evaluar dos puntos nuevos en cada iteración, coloca los puntos de prueba de forma tan precisa que uno de ellos se reutiliza en la iteración siguiente, de modo que, tras la primera iteración, basta con una única evaluación nueva por paso.

El secreto de esta colocación es el número áureo $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1,618$, la célebre proporción que Euclides describió como la división de un segmento en extrema y media razón y que siglos después se popularizó como la divina proporción.

En 1953, Jack Kiefer estudió las estrategias secuenciales óptimas (en sentido minimax) para localizar el máximo de una función unimodal (Kiefer, 1953), trabajo en el que la Sección Áurea aparece como una estrategia de búsqueda de eficiencia casi óptima. Poco después, Douglass J. Wilde (1964) (Wilde, 1964) sistematizó estos métodos dentro de la familia de los algoritmos secuenciales, consolidando la Sección Áurea como el método de referencia de la búsqueda unidimensional sin derivadas.

El algoritmo de la sección áurea

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

¿De dónde sale el número áureo?

Supongamos que, en el intervalo actual $[a_k, b_k]$ de longitud $L_k = b_k - a_k$, colocamos dos puntos de prueba simétricos respecto al centro del intervalo:

\[x_1 = a_k + (1 - \tau) L_k \quad \text{y} \quad x_2 = a_k + \tau L_k, \qquad \text{con } \tfrac{1}{2} < \tau < 1\]

Si $f(x_1) < f(x_2)$, descartamos $[x_2, b_k]$ y el nuevo intervalo es $[a_k, x_2]$, de longitud $L_{k+1} = \tau L_k$. Para reutilizar el punto $x_1$, queremos que pase a ser el punto derecho de la siguiente iteración, es decir:

\[a_k + (1 - \tau) L_k = a_k + \tau L_{k+1} = a_k + \tau^2 L_k\]

Lo que conduce a la ecuación:

\[\tau^2 + \tau - 1 = 0 \quad \Longrightarrow \quad \tau = \frac{\sqrt{5} - 1}{2} = \frac{1}{\varphi} \approx 0,618\]

Por simetría, el razonamiento es idéntico si se descarta la parte izquierda. Así pues, la única forma de reutilizar un punto en cada iteración manteniendo una reducción constante es dividir el intervalo según la proporción áurea: en cada paso el intervalo se reduce a un $61,8\%$ de su longitud.

Pasos del algoritmo

Inicialización: Se fija $\tau = \frac{\sqrt{5} - 1}{2}$ y se calculan los dos puntos iniciales: $x_1 = b - \tau (b - a) \quad \text{y} \quad x_2 = a + \tau (b - a)$ y sus 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 está en $[x_2, b_k]$. El nuevo intervalo es $[a_k, x_2]$. El antiguo $x_1$ pasa a ser el nuevo $x_2$ y sólo se calcula un nuevo $x_1 = b_{k+1} - \tau (b_{k+1} - a_{k+1})$.
- Si $f(x_1) \geqslant f(x_2)$, el mínimo no está en $[a_k, x_1]$. El nuevo intervalo es $[x_1, b_k]$. El antiguo $x_2$ pasa a ser el nuevo $x_1$ y sólo se calcula un nuevo $x_2 = a_{k+1} + \tau (b_{k+1} - a_{k+1})$.
Criterio de parada: Se repite el paso anterior hasta que la longitud del intervalo sea menor que una tolerancia $\varepsilon > 0$.

A diferencia de la Búsqueda Dicotómica, aquí no existe ningún parámetro $\delta$ que limite la precisión alcanzable: la longitud del intervalo tiende a cero, por lo que cualquier tolerancia $\varepsilon > 0$ es alcanzable.

Pseudocódigo

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

\begin{algorithm}
\caption{Búsqueda de la Sección Áurea}
\begin{algorithmic}
\PROCEDURE{SeccionAurea}{$$f, a, b, epsilon$$}
    \STATE $$tau = (sqrt(5) - 1) / 2$$
    \STATE $$ak = a$$
    \STATE $$bk = b$$
    \STATE $$x1 = bk - tau * (bk - ak)$$
    \STATE $$x2 = ak + tau * (bk - ak)$$
    \STATE $$f1 = f(x1)$$
    \STATE $$f2 = f(x2)$$
    \WHILE{$$(bk - ak) > epsilon$$}
        \IF{$$f1 < f2$$}
            \STATE $$bk = x2$$
            \STATE $$x2 = x1$$
            \STATE $$f2 = f1$$
            \STATE $$x1 = bk - tau * (bk - ak)$$
            \STATE $$f1 = f(x1)$$
        \ELSE
            \STATE $$ak = x1$$
            \STATE $$x1 = x2$$
            \STATE $$f1 = f2$$
            \STATE $$x2 = ak + tau * (bk - ak)$$
            \STATE $$f2 = f(x2)$$
        \ENDIF
    \ENDWHILE
    \STATE $$xopt = (ak + bk) / 2$$
    \RETURN $$xopt, f(xopt), [ak, bk]$$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Ejemplo numérico

Para estudiar el comportamiento del algoritmo, consideremos la función no lineal:

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

en el intervalo $[a; b] = [0; 3]$, con $\tau \approx 0,618$.

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

Las primeras iteraciones del método de la sección áurea para este ejemplo son:

Iteración 1:

Intervalo inicial: $[a_0; b_0] = [0; 3]$ (Longitud $L_0 = 3,0$).
Puntos de prueba (ambos se evalúan):
- $x_1 = 3 - 0,618 \cdot 3 = 1,1459 \implies f(1,1459) = 0,6462$
- $x_2 = 0 + 0,618 \cdot 3 = 1,8541 \implies f(1,8541) = 0,5046$
Decisión: Como $f(x_1) > f(x_2)$, descartamos la región $[0; 1,1459]$.
Nuevo intervalo: $[a_1; b_1] = [1,1459; 3,0]$ (Longitud $L_1 = 1,8541$).

Iteración 2:

Intervalo actual: $[a_1; b_1] = [1,1459; 3,0]$.
Puntos de prueba:
- $x_1 = 1,8541$ (reutilizado, era el $x_2$ anterior) $\implies f(1,8541) = 0,5046$
- $x_2 = 1,1459 + 0,618 \cdot 1,8541 = 2,2918 \implies f(2,2918) = 0,9186$ (única evaluación nueva)
Decisión: Como $f(x_1) < f(x_2)$, descartamos la región $[2,2918; 3,0]$.
Nuevo intervalo: $[a_2; b_2] = [1,1459; 2,2918]$ (Longitud $L_2 = 1,1459$).

Continuando de la misma forma, se obtienen las siguientes iteraciones, donde en negrita se indica el valor de la función que se calcula en cada iteración (el otro se reutiliza de la anterior):

Iter.	$[a_k; b_k]$	$x_1$	$f(x_1)$	$x_2$	$f(x_2)$	Nuevo intervalo	$L_{k+1}$
1	$[0; 3]$	$1,1459$	$\mathbf{0,6462}$	$1,8541$	$\mathbf{0,5046}$	$[1,1459; 3]$	$1,8541$
2	$[1,1459; 3]$	$1,8541$	$0,5046$	$2,2918$	$\mathbf{0,9186}$	$[1,1459; 2,2918]$	$1,1459$
3	$[1,1459; 2,2918]$	$1,5836$	$\mathbf{0,4403}$	$1,8541$	$0,5046$	$[1,1459; 1,8541]$	$0,7082$
4	$[1,1459; 1,8541]$	$1,4164$	$\mathbf{0,4737}$	$1,5836$	$0,4403$	$[1,4164; 1,8541]$	$0,4377$
5	$[1,4164; 1,8541]$	$1,5836$	$0,4403$	$1,6869$	$\mathbf{0,4476}$	$[1,4164; 1,6869]$	$0,2705$

Resultado: Con 6 evaluaciones de la función (dos en la primera iteración y una en cada una de las cuatro siguientes, sin contar la evaluación final de $f(x_{opt})$ del pseudocódigo), el intervalo inicial de longitud $3$ se ha reducido a $0,2705$, garantizando que el óptimo $x^* = 1,6$ reside en $[1,4164; 1,6869]$.

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

Análisis técnico: Sección Áurea vs. Búsqueda Dicotómica

Como tras la primera iteración cada evaluación produce una reducción del intervalo en un factor $\tau$, tras $N$ evaluaciones de la función la longitud del intervalo final es:

\[L_N = (b - a)\, \tau^{N-1} \approx (b - a) \cdot 0,618^{N-1}\]

Por tanto, para que el intervalo final tenga una amplitud menor que $\varepsilon$, basta con elegir:

\[N > 1 + \frac{\ln\left(\varepsilon / (b - a)\right)}{\ln \tau}\]

Comparando la reducción del intervalo por evaluación de la función:

Búsqueda Uniforme (Simultánea): reducción lineal, con una razón $R_N = \frac{2}{N-1}$.
Método Dicotómico (Secuencial): cada par de evaluaciones reduce el intervalo aproximadamente a la mitad, es decir, un factor $\sqrt{1/2} \approx 0,707$ por evaluación.
Sección Áurea (Secuencial): cada evaluación reduce el intervalo en un factor $\tau \approx 0,618$.

Así, por ejemplo, para alcanzar una tolerancia $\varepsilon = 10^{-4}$ en el intervalo $[0; 3]$, la Sección Áurea necesita apenas 23 evaluaciones, frente a las aproximadamente 30 del Método Dicotómico y las decenas de miles de la Búsqueda Uniforme.

Ventajas y Limitaciones

Ventajas:
- Una sola evaluación por iteración: Tras la primera iteración, reutiliza uno de los dos puntos de prueba, lo que la hace especialmente adecuada cuando evaluar $f(x)$ es costoso.
- Reducción constante y predecible: El intervalo se reduce siempre en el mismo factor $\tau$, por lo que el número de evaluaciones necesarias se conoce de antemano.
- Sin derivadas ni parámetros: No requiere derivadas ni ajustar parámetros como el $\delta$ del Método Dicotómico. No obstante, la garantía sobre el intervalo exige que la función sea continua y unimodal.
Limitaciones:
- Naturaleza secuencial: Cada evaluación depende del resultado de la anterior, por lo que no es paralelizable.
- Errores de redondeo: Como $\tau$ es irracional, al reutilizar puntos durante muchas iteraciones se acumulan pequeños errores numéricos que pueden romper la simetría de los puntos de prueba. En implementaciones prácticas suele recalcularse periódicamente la posición de ambos puntos a partir de los extremos del intervalo.
- Convergencia lineal: Si la función es suave, métodos que usan derivadas o interpolación (como Newton o la interpolación parabólica) convergen mucho más rápido cerca del óptimo.

El Método de la Sección Áurea es la culminación natural de la búsqueda secuencial sin derivadas. Donde el Método Dicotómico desperdiciaba información evaluando dos puntos nuevos en cada paso, la Sección Áurea coloca sus puntos con una precisión tal que nada se pierde, y lo hace recurriendo a una proporción que la humanidad lleva más de dos mil años admirando en el arte y la naturaleza. Una muestra más de que, en optimización, la elegancia matemática y la eficiencia computacional suelen ir de la mano.

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