Búsqueda de la sección dorada
# 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 $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

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.

