Búsqueda de la 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  están en el eje vertical y el horizontal es el parámetro . El valor de  ha sido calculado ya para los tres puntos ,  y . Dado que  es más pequeño que  y que , es evidente que el mínimo se encuentra dentro del intervalo desde  hasta  (porque  es unimodal)

El siguiente paso en el proceso de minimización es "probar" la función evaluándola en el nuevo valor de : . Es más eficiente escoger  en algún lugar dentro del intervalo más grande, dígase entre  y . Por la figura, se puede notar que si  entonces el mínimo se encuentra entre  y  y el nuevo trío de puntos serán ,  y . Sin embargo, si , entonces el mínimo pertenece al intervalo desde  hasta , y el nuevo trío de puntos serán ,  y . 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  hasta  con tamaño , o desde  hasta  con tamaño . 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 , el algoritmo debe escoger .

Sin embargo, queda aún sin responder dónde debe ubicarse  con respecto a  y . 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 , ,  o , , . Al mantener la misma proporción durante todo el algoritmo, se evita la situación en la cual  está muy cerca de  o , 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  es proporcional al espaciado antes de la evaluación, si  y el nuevo trío de puntos es ,  y  entonces se quiere:
 
En cambio, si  y el nuevo trío de puntos es ,  y , entonces se quiere:
 
Eliminando c de este sistema de dos ecuaciones se obtiene:
 
o
 
donde   es la proporción dorada:
 
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 , ,  y , terminando cuando se cumple la siguiente cota de precisión relativa:
 
donde  es un parámetro de tolerancia del algoritmo y  es el valor absoluto de . La condición está basada en el tamaño del intervalo relativo a su valor central, porque el error relativo en  es aproximadamente proporcional al cuadrado del error absoluto en  en los casos típicos. Por esa misma razón, en "Numerical Recipes in C" se recomienda  donde  es la precisión absoluta requerida para .

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 , 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 
 
 

 

Números de Fibonacci
Algoritmos de búsqueda
Número áureo