La búsqueda de la sección áurea es una técnica para encontrar un extremo (mínimo o máximo) de una función dentro de un intervalo especificado. Para una función estrictamente unimodal con un extremo dentro del intervalo, encontrará ese extremo, mientras que para un intervalo que contiene múltiples extremos (posiblemente incluyendo los límites del intervalo), convergerá a uno de ellos. Si el único extremo del intervalo está en un límite del intervalo, convergerá a ese punto límite. El método opera estrechando sucesivamente el rango de valores en el intervalo especificado, lo que lo hace relativamente lento, pero muy robusto. La técnica deriva su nombre del hecho de que el algoritmo mantiene los valores de la función para cuatro puntos cuyos tres anchos de intervalo están en la razón2-φ: 2φ-3: 2-φ donde φ es la proporción áurea . Estas proporciones se mantienen para cada iteración y son de máxima eficacia. Exceptuando los puntos límite, cuando se busca un mínimo, el punto central siempre es menor o igual que los puntos externos, asegurando que se contenga un mínimo entre los puntos externos. Lo contrario es cierto cuando se busca un máximo. El algoritmo es el límite de la búsqueda de Fibonacci (que también se describe a continuación) para muchas evaluaciones de funciones. La búsqueda de Fibonacci y la búsqueda de la sección áurea fueron descubiertas por Kiefer (1953) (ver también Avriel y Wilde (1966)).
Idea básica
La discusión aquí se plantea en términos de búsqueda de un mínimo (la búsqueda de un máximo es similar) de una función unimodal . A diferencia de encontrar un cero, donde dos evaluaciones de funciones con signo opuesto son suficientes para poner entre corchetes una raíz, cuando se busca un mínimo, se necesitan tres valores. La búsqueda de la sección áurea es una forma eficaz de reducir progresivamente el intervalo localizando el mínimo. La clave es observar que independientemente de cuántos puntos se hayan evaluado, el mínimo se encuentra dentro del intervalo definido por los dos puntos adyacentes al punto con el menor valor evaluado hasta el momento.
El diagrama de arriba ilustra un solo paso en la técnica para encontrar un mínimo. Los valores funcionales deestán en el eje vertical y el eje horizontal es el parámetro x . El valor de ya ha sido evaluado en los tres puntos: , , y . Desde es más pequeño que cualquiera o , está claro que un mínimo se encuentra dentro del intervalo desde a .
El siguiente paso en el proceso de minimización es "probar" la función evaluándola en un nuevo valor de x , a saber. Es más eficiente elegir en algún lugar dentro del intervalo más grande, es decir, entre y . Del diagrama, está claro que si la función produce, entonces un mínimo se encuentra entre y , y el nuevo triplete de puntos será , , y . Sin embargo, si la función arroja el valor, entonces un mínimo se encuentra entre y , y el nuevo triplete de puntos será , , y . Por lo tanto, en cualquier caso, podemos construir un nuevo intervalo de búsqueda más estrecho que esté garantizado para contener el mínimo de la función.
Selección del punto de la sonda
En el diagrama de arriba, se ve que el nuevo intervalo de búsqueda estará entre y con una longitud de a + c , o entre y con una longitud de b . La búsqueda de la sección áurea requiere que estos intervalos sean iguales. Si no es así, una racha de "mala suerte" podría llevar a que el intervalo más amplio se utilice muchas veces, lo que ralentizará la velocidad de convergencia. Para asegurarse de que b = a + c , el algoritmo debe elegir.
Sin embargo, todavía queda la pregunta de dónde debe colocarse en relación con y . La búsqueda de la sección áurea elige el espaciado entre estos puntos de tal manera que estos puntos tengan la misma proporción de espaciado que el triple subsiguiente. o . Al mantener la misma proporción de espaciado en todo el algoritmo, evitamos una situación en la que está muy cerca de o y garantizar que el ancho del intervalo se contraiga en la misma proporción constante en cada paso.
Matemáticamente, para asegurar que el espaciado después de evaluar es proporcional al espaciado antes de esa evaluación, si es y nuestro nuevo triplete de puntos es , , y , entonces queremos
Sin embargo, si es y nuestro nuevo triplete de puntos es , , y , entonces queremos
Eliminando c de estas dos ecuaciones simultáneas se obtiene
o
donde φ es la proporción áurea :
La aparición de la proporción áurea en el espaciado proporcional de los puntos de evaluación es la forma en que este algoritmo de búsqueda recibe su nombre.
Condición de terminación
Se puede aplicar cualquier número de condiciones de terminación, dependiendo de la aplicación. El intervalo ΔX = X 4 - X 1 es una medida del error absoluto en la estimación del mínimo X y puede usarse para terminar el algoritmo. El valor de ΔX se reduce en un factor de r = φ - 1 para cada iteración, por lo que el número de iteraciones para alcanzar un error absoluto de ΔX es aproximadamente ln (ΔX / ΔX o ) / ln (r) donde ΔX o es el valor inicial de ΔX .
Debido a que las funciones suaves son planas (su primera derivada es cercana a cero) cerca de un mínimo, se debe prestar atención para no esperar una precisión demasiado grande al localizar el mínimo. La condición de terminación proporcionada en el libro Recetas numéricas en C se basa en probar las brechas entre, , y , terminando cuando se encuentra dentro de los límites de precisión relativa
dónde es un parámetro de tolerancia del algoritmo, y es el valor absoluto de. La comprobación se basa en el tamaño del corchete en relación con su valor central, porque ese error relativo en es aproximadamente proporcional al cuadrado del error absoluto en en casos típicos. Por esa misma razón, el texto de Recetas numéricas recomienda que, dónde es la precisión absoluta requerida de .
Algoritmo
Algoritmo iterativo
- Especifique la función que se minimizará, f (x), el intervalo que se buscará como {X 1 , X 4 } y sus valores funcionales F 1 y F 4 .
- Calcule un punto interior y su valor funcional F 2 . Las dos longitudes de intervalos están en la relación c: r o r: c , donde r = φ - 1; y c = 1 - r , siendo φ la proporción áurea.
- Utilizando el triplete, determine si se cumplen los criterios de convergencia. Si es así, estime la X en el mínimo de ese triplete y regrese.
- A partir del triplete, calcule el otro punto interior y su valor funcional. Los tres intervalos estarán en la proporción c: cr: c .
- Los tres puntos para la próxima iteración serán aquellos en los que F es un mínimo y los dos puntos más cercanos en X.
- Ir al paso 3
"" "Programa Python para la búsqueda de la sección dorada. Esta implementación no reutiliza las evaluaciones de funciones y asume que el mínimo es c o d (no en los bordes en a o b)" "" import mathgr = ( matemáticas . sqrt ( 5 ) + 1 ) / 2def gss ( f , a , b , tol = 1e-5 ): "" "Búsqueda de sección áurea para encontrar el mínimo de f en [a, b] f: una función estrictamente unimodal en [a, b] Ejemplo: >>> f = lambda x: (x-2) ** 2 >>> x = gss (f, 1, 5) >>> print ("%. 15f"% x) 2.000009644875678 "" " c = b - ( b - a ) / gr d = a + ( b - a ) / gr while abs ( b - a ) > tol : if f ( c ) < f ( d ): b = d else : a = c # Aquí recalculamos tanto c como d para evitar la pérdida de precisión que puede conducir a resultados incorrectos o bucle infinito c = b - ( b - a ) / gr d = a + ( b - a ) / gr volver ( b + a ) / 2
"" "Programa Python para la búsqueda de la sección dorada. Esta implementación reutiliza las evaluaciones de funciones, guarda la mitad de las evaluaciones por iteración y devuelve un intervalo delimitador." "" Import mathinvphi = ( matemáticas . sqrt ( 5 ) - 1 ) / 2 # 1 / phi invphi2 = ( 3 - matemáticas . sqrt ( 5 )) / 2 # 1 / phi ^ 2def gss ( f , a , b , tol = 1e-5 ): "" "Búsqueda de sección dorada. Dada una función f con un mínimo local único en el intervalo [a, b], gss devuelve un intervalo de subconjunto [c, d] que contiene el mínimo con dc <= tol. Ejemplo: >>> f = lambda x: (x-2) ** 2 >>> a = 1 >>> b = 5 >>> tol = 1e-5 >>> (c, d) = gss (f , a, b, tol) >>> imprimir (c, d) 1.9999959837979107 2.0000050911830893 "" " ( a , b ) = ( min ( a , b ), max ( a , b )) h = b - a si h <= tol : return ( a , b ) # Pasos necesarios para lograr la tolerancia n = int ( math . Ceil ( math . Log ( tol / h ) / math . Log ( invphi ))) c = a + invphi2 * h d = a + invphi * h yc = f ( c ) yd = f ( d ) para k en el rango ( n - 1 ): si yc < yd : b = d d = c yd = yc h = invphi * h c = a + invphi2 * h yc = f ( c ) else : a = c c = d yc = yd h = invphi * h d = a + invphi * h yd = f ( d ) if yc < yd : return ( a , d ) else : return ( c , b )
Algoritmo recursivo
public class GoldenSectionSearch { public static final doble invphi = ( Math . sqrt ( 5.0 ) - 1 ) / 2.0 ; public static final doble invphi2 = ( 3 - Math . sqrt ( 5.0 )) / 2.0 ; Función de interfaz pública { doble de ( doble x ); } // Devuelve el subintervalo de [a, b] que contiene un mínimo de f public static double [] gss ( Función f , double a , double b , double tol ) { return gss ( f , a , b , tol , b - a , true , 0 , 0 , true , 0 , 0 ); } private static double [] gss ( Función f , double a , double b , double tol , double h , boolean noC , double c , double fc , boolean noD , double d , double fd ) { if ( Math . abs ( h ) <= tol ) { return new double [] { a , b }; } si ( noC ) { c = a + invphi2 * h ; fc = f . de ( c ); } si ( noD ) { d = a + invphi * h ; fd = f . de ( d ); } if ( fc < fd ) { return gss ( f , a , d , tol , h * invphi , true , 0 , 0 , false , c , fc ); } else { return gss ( f , c , b , tol , h * invphi , false , d , fd , true , 0 , 0 ); } } public static void main ( String [] args ) { Función f = ( x ) -> Math . pow ( x - 2 , 2 ); doble a = 1 ; doble b = 5 ; doble tol = 1e-5 ; doble [] ans = gss ( f , a , b , tol ); Sistema . fuera . println ( "[" + ans [ 0 ] + "," + ans [ 1 ] + "]" ); // [1.9999959837979107,2.0000050911830893] } }
importar matemáticasinvphi = ( matemáticas . sqrt ( 5 ) - 1 ) / 2 # 1 / phi invphi2 = ( 3 - matemáticas . sqrt ( 5 )) / 2 # 1 / phi ^ 2def gssrec ( f , a , b , tol = 1e-5 , h = Ninguno , c = Ninguno , d = Ninguno , fc = Ninguno , fd = Ninguno ): "" "Búsqueda de sección áurea, recursiva. Dada una función f con un mínimo local único en el intervalo [a, b], gss devuelve un intervalo de subconjunto [c, d] que contiene el mínimo con dc <= tol. Ejemplo: >>> f = lambda x: (x-2) ** 2 >>> a = 1 >>> b = 5 >>> tol = 1e-5 >>> (c, d) = gssrec (f , a, b, tol) >>> imprimir (c, d) 1.9999959837979107 2.0000050911830893 "" " ( a , b ) = ( min ( a , b ), max ( a , b )) si h es Ninguno : h = b - a si h <= tol : devuelve ( a , b ) si c es Ninguno : c = a + invphi2 * h si d es None : d = a + invphi * h si fc es None : fc = f ( c ) si fd es None : fd = f ( d ) si fc < fd : return gssrec ( f , a , d , tol , h * invphi , c = None , fc = None , d = c , fd = fc ) else : return gssrec ( f , c , b , tol , h * invphi , c = d , fc = fd , d = Ninguno , fd = Ninguno )
Búsqueda de Fibonacci
También se puede utilizar un algoritmo muy similar para encontrar el extremo (mínimo o máximo) de una secuencia de valores que tiene un único mínimo local o máximo local. Para aproximar las posiciones de la sonda de búsqueda de la sección áurea mientras se sondean solo índices de secuencia de números enteros, la variante del algoritmo para este caso típicamente mantiene entre corchetes la solución en la que la longitud del intervalo entre corchetes es un número de Fibonacci . Por esta razón, la variante de secuencia de la búsqueda de la sección áurea a menudo se denomina búsqueda de Fibonacci .
La búsqueda de Fibonacci fue ideada por primera vez por Kiefer (1953) como una búsqueda minimax para el máximo (mínimo) de una función unimodal en un intervalo.
Ver también
Referencias
- Kiefer, J. (1953), "Sequential minimax search for a maximum", Proceedings of the American Mathematical Society , 4 (3): 502–506, doi : 10.2307 / 2032161 , JSTOR 2032161 , MR 0055639
- Avriel, Mordecai; Wilde, Douglass J. (1966), "Prueba de optimización para la técnica de búsqueda simétrica de Fibonacci", Fibonacci Quarterly , 4 : 265-269, MR 0208812
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 10.2. Búsqueda de sección dorada en una dimensión" , Recetas numéricas: El arte de la informática científica (3ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8