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).
![](http://up.wiki.x.io/wikipedia/commons/thumb/5/52/GoldenSectionSearch.png/325px-GoldenSectionSearch.png)
Idea básica
editarEl 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
editarDel 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
editarEn 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
editarMé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
editarUn 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
editarReferencias
editar- 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.