Búsqueda de la sección dorada

Esquema de una búsqueda de sección dorada

La búsqueda (o método) de la sección dorada es una técnica para hallar el extremo (mínimo o máximo) de una función unimodal, mediante reducciones sucesivas del rango de valores en el cual se conoce que se encuentra el extremo. La técnica debe su nombre al hecho de que el algoritmo mantiene los valores de la función en tríos de puntos cuyas distancias forman una proporción dorada. El algoritmo es el límite de la búsqueda de Fibonacci (también descrita debajo) para un largo número de evaluaciones de la función. La búsqueda de Fibonacci y la búsqueda de la sección dorada fueron descubiertos por Kiefer (1953).

Idea básica

El diagrama de arriba ilustra un paso en la técnica para hallar un mínimo. Los valores de la función $f(x)$ están en el eje vertical y el horizontal es el parámetro $x$. El valor de $f(x)$ ha sido calculado ya para los tres puntos $x_{1}$, $x_{2}$ y $x_{3}$. Dado que $f_{2}$ es más pequeño que $f_{1}$ y que $f_{3}$, es evidente que el mínimo se encuentra dentro del intervalo desde $x_{1}$ hasta $x_{3}$ (porque $f$ es unimodal)

El siguiente paso en el proceso de minimización es "probar" la función evaluándola en el nuevo valor de $x$: $x_{4}$. Es más eficiente escoger $x_{4}$ en algún lugar dentro del intervalo más grande, dígase entre $x_{2}$ y $x_{3}$. Por la figura, se puede notar que si $f(x_{4})=f_{4a}$ entonces el mínimo se encuentra entre $x_{1}$ y $x_{4}$ y el nuevo trío de puntos serán $x_{1}$, $x_{2}$ y $x_{4}$. Sin embargo, si $f(x_{4})=f_{4b}$, entonces el mínimo pertenece al intervalo desde $x_{2}$ hasta $x_{3}$, y el nuevo trío de puntos serán $x_{2}$, $x_{4}$ y $x_{3}$. De esta manera, en cualquier caso, es posible construir un nuevo intervalo de búsqueda más pequeño en el cual está garantizado que se encuentra el mínimo de la función.

Selección del punto de prueba

Del diagrama de arriba se deduce que el nuevo intervalo de búsqueda será desde $x_{1}$ hasta $x_{4}$ con tamaño $a+c$, o desde $x_{2}$ hasta $x_{3}$ con tamaño $b$. Este método requiere que ambos intervalos sean de igual tamaño. Si no lo son, es posible que una "mala suerte" pueda llevar a utilizar el intervalo más grande muchas veces, ralentizando así la convergencia del método. Para garantizar que $b=a+c$, el algoritmo debe escoger $x_{4}=x_{1}+(x_{3}-x_{2})$.

Sin embargo, queda aún sin responder dónde debe ubicarse $x_{2}$ con respecto a $x_{1}$ y $x_{3}$. La búsqueda de la sección dorada escoge los espacios entre estos puntos de forma tal que se mantenga la proporción entre ellos y los de los puntos subsecuentes $x_{1}$, $x_{2}$, $x_{4}$ o $x_{2}$, $x_{4}$, $x_{3}$. Al mantener la misma proporción durante todo el algoritmo, se evita la situación en la cual $x_{2}$ está muy cerca de $x_{1}$ o $x_{3}$, y se garantiza que la longitud del intervalo se estreche con la misma proporción en cada paso.

Matemáticamente, para asegurar que el espaciado después de evaluar $f(x_{4})$ es proporcional al espaciado antes de la evaluación, si $f(x_{4})=f_{4a}$ y el nuevo trío de puntos es $x_{1}$, $x_{2}$ y $x_{4}$ entonces se quiere:

${\frac {c}{a}}={\frac {a}{b}}.$

En cambio, si $f(x_{4})=f_{4b}$ y el nuevo trío de puntos es $x_{2}$, $x_{4}$ y $x_{3}$, entonces se quiere:

${\frac {c}{(b-c)}}={\frac {a}{b}}.$

Eliminando c de este sistema de dos ecuaciones se obtiene:

$\left({\frac {b}{a}}\right)^{2}={\frac {b}{a}}+1$

o

${\frac {b}{a}}=\varphi$

donde $\varphi$ es la proporción dorada:

$\varphi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988\ldots$

La aparición del número dorado en el espaciado proporcional de la evaluación de los puntos es el motivo por el cual este algoritmo de búsqueda recibe su nombre.

Condición de terminación

En adición al procedimiento de reducción del tamaño del espacio de búsqueda de la solución, el algoritmo debe tener una condición de terminación. La dada en el libro "Numerical Recipes in C" se basa en los espacios entre $x_{1}$, $x_{2}$, $x_{3}$ y $x_{4}$, terminando cuando se cumple la siguiente cota de precisión relativa:

$|x_{3}-x_{1}|<\tau (|x_{2}|+|x_{4}|)\,$

donde $\tau$ es un parámetro de tolerancia del algoritmo y $|x|$ es el valor absoluto de $x$. La condición está basada en el tamaño del intervalo relativo a su valor central, porque el error relativo en $x$ es aproximadamente proporcional al cuadrado del error absoluto en $f(x)$ en los casos típicos. Por esa misma razón, en "Numerical Recipes in C" se recomienda $\tau ={\sqrt {\epsilon }}$ donde $\epsilon$ es la precisión absoluta requerida para $f(x)$.

Algoritmo

Método de la sección dorada

import math
from typing import Tuple, Callable

def golden(f: Callable, bracket: Tuple[float, float, float], xtol=0.001, maxiter=100) -> Tuple[float, int, int]:
    """Recibe una funcion f, una tupla bracket que define un bracket de f y, a partir de dicho bracket, devuelve 
    una tupla r, nit, nfev con un mínimo aproximado 'r' y el número de iteraciones y de evaluaciones de f  
    necesarias para encontrarlo mediante el método de la razón  ́aurea.

    Args:
        f (Callable): función a evaluar
        bracket (Tuple[float, float, float]): bracket sobre el que buscar el mínimo
        xtol (float, optional): longitud del intervalo margen de error mínimo. Por defecto es 0.001
        maxiter (int, optional): número de iteraciones máximas del algoritmo. Por defecto es 100.

    Raises:
        Exception: hemos superado el número maximo de iteraciones
        ValueError: el bracket no cumple las condiciones de orden

    Returns:
        Tuple[float, int, int]: tupla con la raíz, el número de iteraciones y el número de evaluaciones de 
        la función
    """
    a, b, c = bracket
    if not (a < b < c) and not (f(a) > f(b) and  f(b) < f(c)):
        raise ValueError('Incorrect bracket')
    
    nit = 0  # Número de iteraciones de la función
    nfev = 2  # Número de evaluaciones de la función
    phi = (1 + math.sqrt(5))/2
    ra = 1/phi 
    x2 = a + (c - a) * ra
    x1 = c - (c - a) * ra
    f1 = f(x1)
    f2 = f(x2)
    
    while abs(c - a) > xtol and nit <= maxiter:
        nit += 1
        nfev += 1  

        # Calculamos los puntos intermedios.
        if f1 < f2:
            c = x2  
            x2 = x1
            x1 = c - (c - a) * ra
            f2 = f1
            f1 = f(x1)
        else:
            a = x1
            x1 = x2
            x2 = a + (c - a) * ra
            f1 = f2
            f2 = f(x2)

    if nit > maxiter:
        raise Exception("El número máximo de iteraciones permitidas ha sido excedido.")
    
    r = (a + c) / 2
    return r, nit, nfev

El ahorro de un 50% del número de llamados a $f(x)$, junto con un número ligeramente inferior de pasos, constituye la principal ventaja algorítmica de este método sobre la búsqueda ternaria.

Búsqueda de Fibonacci

Un algoritmo muy similar puede ser también usado para determinar el extremo (mínimo o máximo) de una secuencia de valores que tiene un único mínimo local o máximo local. Esta variante del algoritmo, mantiene un intervalo de búsqueda cuya longitud es un número Fibonacci para aproximar las posiciones de prueba de la búsqueda de la sección dorada. Por esta razón, la variante del método para secuencias es usualmente llamada búsqueda de Fibonacci.

La búsqueda de Fibonacci fue ideada por Kiefer (1953) como una búsqueda minimax para encontrar el máximo (mínimo) de una función unimodal en un intervalo.

Véase también

• Búsqueda ternaria
• Búsqueda binaria

Referencias

• Kiefer, J. (1953), «Sequential minimax search for a maximum», Proceedings of the American Mathematical Society 4 (3): 502-506, JSTOR 2032161, MR 0055639, doi:10.2307/2032161 .
• Avriel, Mordecai; Wilde, Douglass J. (1966), «Optimality proof for the symmetric Fibonacci search technique», Fibonacci Quarterly 4: 265-269, MR 0208812 .

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 10.2. Golden Section Search in One Dimension», Numerical Recipes: The Art of Scientific Computing (3rd edición), New York: Cambridge University Press, ISBN 978-0-521-88068-8, archivado desde el original el 11 de agosto de 2011, consultado el 4 de enero de 2016 .

• Datos: Q2424337