Búsqueda de la sección áurea

Técnica para encontrar un extremo de una función

Diagrama de una búsqueda de sección áurea. El triplete inicial de valores x es { x ₁ ,  x ₂ ,  x ₃ }. Si f ( x ₄ ) =  f _4a , se elige el triplete { x ₁ ,  x ₂ ,  x ₄ } para la siguiente iteración. Si f ( x ₄ ) =  f _4b , se elige el triplete { x ₂ ,  x ₄ ,  x ₃ }.

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 en el intervalo está en un límite del intervalo, convergerá a ese punto límite. El método opera reduciendo 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 proporción φ :1: φ , donde φ es la proporción áurea . Estas proporciones se mantienen para cada iteración y son máximamente eficientes. Exceptuando los puntos límite, cuando se busca un mínimo, el punto central siempre es menor o igual que los puntos externos, lo que garantiza que un mínimo esté contenido 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 (también descrita 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) (véase también Avriel y Wilde (1966)).

Idea básica

El análisis que se presenta aquí se basa en la búsqueda de un mínimo (la búsqueda de un máximo es similar) de una función unimodal . A diferencia de la búsqueda de un cero, donde dos evaluaciones de funciones con signos opuestos son suficientes para encerrar una raíz, cuando se busca un mínimo, se necesitan tres valores. La búsqueda de la sección áurea es una forma eficiente de reducir progresivamente el intervalo para localizar 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 anterior ilustra un solo paso de la técnica para hallar un mínimo. Los valores funcionales de están en el eje vertical y el eje horizontal es el parámetro x . El valor de ya se ha evaluado en los tres puntos: , y . Como es menor que o , es evidente que un mínimo se encuentra dentro del intervalo de a . ${\displaystyle f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{1}}$ ${\displaystyle f_{3}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{3}}$

El siguiente paso en el proceso de minimización es "probar" la función evaluándola en un nuevo valor de x , es decir , . Es más eficiente elegir 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 produce 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 que contenga el mínimo de la función. ${\displaystyle x_{4}}$ ${\displaystyle x_{4}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle f_{4a}>f(x_{2})}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{4}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{4}}$ ${\displaystyle f_{4b}<f(x_{2})}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{4}}$ ${\displaystyle x_{3}}$

Selección del punto de sonda

Del diagrama anterior se desprende 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 lo son, una racha de "mala suerte" podría hacer que el intervalo más amplio se utilice muchas veces, lo que ralentizaría la tasa de convergencia. Para garantizar que b = a  +  c , el algoritmo debería elegir . ${\displaystyle x_{1}}$ ${\displaystyle x_{4}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{4}=x_{1}+(x_{3}-x_{2})}$

Sin embargo, aún queda la cuestión de dónde se debe colocar en relación con y . La búsqueda de 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 posterior o . Al mantener la misma proporción de espaciado a lo largo del algoritmo, evitamos una situación en la que está muy cerca de o y garantizamos que el ancho del intervalo se reduzca en la misma proporción constante en cada paso. ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{1},x_{2},x_{4}}$ ${\displaystyle x_{2},x_{4},x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{3}}$

Matemáticamente, para garantizar que el espaciado después de la evaluación sea proporcional al espaciado antes de esa evaluación, si es y nuestro nuevo triplete de puntos es , , y , entonces queremos ${\displaystyle f(x_{4})}$ ${\displaystyle f(x_{4})}$ ${\displaystyle f_{4a}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{4}}$

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

Sin embargo, si es y nuestro nuevo triplete de puntos es , , y , entonces queremos ${\displaystyle f(x_{4})}$ ${\displaystyle f_{4b}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{4}}$ ${\displaystyle x_{3}}$

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

Eliminando c de estas dos ecuaciones simultáneas obtenemos

${\displaystyle \left({\frac {b}{a}}\right)^{2}-{\frac {b}{a}}=1,}$

o

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

donde φ es la proporción áurea :

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

La aparición de la proporción áurea en el espaciado proporcional de los puntos de evaluación es lo que da nombre a este algoritmo de búsqueda.

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 ₄ − X ₁ es una medida del error absoluto en la estimación del X mínimo y se puede utilizar para terminar el algoritmo. El valor de Δ X se reduce por 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 ₀ ) / ln( r ), donde Δ X ₀ 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 a no esperar una precisión demasiado grande al ubicar el mínimo. La condición de terminación proporcionada en el libro Recetas numéricas en C se basa en probar los espacios entre , , y , terminando cuando se encuentra dentro de los límites de precisión relativa. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{4}}$

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

donde 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 error absoluto al cuadrado en en casos típicos. Por esa misma razón, el texto de Recetas numéricas recomienda que , donde es la precisión absoluta requerida de . ${\displaystyle \tau }$ ${\displaystyle |x|}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle \tau ={\sqrt {\varepsilon }}}$ ${\displaystyle \varepsilon }$ ${\displaystyle f(x)}$

Algoritmo

¡Nota! Los ejemplos que se muestran aquí describen un algoritmo que sirve para hallar el mínimo de una función. Para hallar el máximo, es necesario invertir los operadores de comparación.

Algoritmo iterativo

Diagrama de la búsqueda de un mínimo mediante la sección áurea. El intervalo inicial encerrado por X ₁ y X ₄ se divide en tres intervalos y se evalúa f[X] en cada uno de los cuatro X _i . A continuación, se seleccionan los dos intervalos que contienen el mínimo de f ( X _i ), se calcula un tercer intervalo y valor funcional y se repite el proceso hasta que se cumplen las condiciones de terminación. Los tres anchos de intervalo están siempre en la proporción c:cr:c donde r = φ − 1 = 0,619... y c = 1 − r = 0,381..., siendo φ la proporción áurea . Esta elección de proporciones de intervalos es la única que permite mantener las proporciones durante una iteración.

1. Especifique la función que se minimizará, ⁠ ⁠ ${\displaystyle f(x)}$ , el intervalo que se buscará como { X ₁ , X ₄ } y sus valores funcionales F ₁ y F ₄ .
2. Calcular un punto interior y su valor funcional F ₂ . Las dos longitudes de intervalo están en la razón c : r o r : c donde r = φ − 1; y c = 1 − r , siendo φ la proporción áurea.
3. 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 vuelva.
4. A partir del triplete, calcula el otro punto interior y su valor funcional. Los tres intervalos estarán en la razón ⁠ ⁠ ${\displaystyle c:cr:c}$ .
5. Los tres puntos para la siguiente iteración serán aquel donde F sea un mínimo y los dos puntos más cercanos a él en X.
6. Vaya al paso 3.

""" Programa Python para la búsqueda de la sección áurea. Esta implementación no reutiliza las evaluaciones de funciones y supone que el mínimo es c o d (no en los bordes a o b) """importar  matemáticasinvphi  =  ( math . sqrt ( 5 )  -  1 )  /  2  # 1 / phidef  gss ( f ,  a ,  b ,  tolerancia = 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:  >>> def f(x): return (x - 2) ** 2  >>> x = gss(f, 1, 5)  >>> print(f"{x:.5f}")  2.00000 """  mientras  b  -  a  >  tolerancia :  c  =  b  -  ( b  -  a )  *  invphi  d  =  a  +  ( b  -  a )  *  invphi  si  f ( c )  <  f ( d ):  b  =  d  de lo contrario :  # f(c) > f(d) para encontrar el máximo  a  =  c devuelve  ( b  +  a )  /  2

// a y c definen el rango a buscar // func(x) devuelve el valor de la función en x que se minimizará function goldenSection ( a , c , func ) { function split ( x1 , x2 ) { return x1 + 0.6180339887498949 * ( x2 - x1 ); } var b = split ( a , c ); var bv = func ( b ); while ( a != c ) { var x = split ( a , b ); var xv = func ( x ) ; if ( xv < bv ) { bv = xv ; c = b ; b = x ; } else { a = c ; c = x ; } } return b ; } function test ( x ) { return - Math.sin ( x ); } console.log ( goldenSection ( 0 , 3 , test )); // imprime PI / 2                                                                       

""" Programa Python para la búsqueda de la sección áurea. Esta implementación no reutiliza las evaluaciones de funciones y supone que el mínimo es c o d (no en los bordes a o b) """importar  matemáticasinvphi  =  ( math . sqrt ( 5 )  -  1 )  /  2  # 1 / phi invphi2  =  ( 3  -  math . sqrt ( 5 ))  /  2  # 1 / phi^2def  gss ( f ,  a ,  b ,  tolerancia = 1e-5 ): """  Búsqueda de sección áurea.  Dada una función f con un único mínimo local en  el intervalo [a,b], gss devuelve un subconjunto del intervalo  [c,d] que contiene el mínimo con dc <= tolerancia. Ejemplo:  >>> def f(x): return (x - 2) ** 2  >>> print(*gss(f, a=1, b=5, tolerancia=1e-5))  1,9999959837979107 2,0000050911830893  """  a ,  b  =  min ( a ,  b ),  max ( a ,  b )  h  =  b  -  a  si  h  <=  tolerancia :  return  ( a ,  b ) # Pasos necesarios para lograr la tolerancia  n  =  int ( math . ceil ( math . log ( tolerancia  /  h )  /  math . log ( invphi ))) c ,  d  =  a  +  invphi2  *  h ,  a  +  invphi  *  h  yc ,  yd  =  f ( c ),  f ( d ) para  _  en  rango ( n  -  1 ):  h  *=  invphi  si  yc  <  yd :  b ,  d  =  d ,  c  yd  =  yc  c  =  a  +  invphi2  *  h  yc  =  f ( c )  de lo contrario :  # yc > yd para encontrar el máximo  a ,  c  =  c ,  d  yc  =  yd  d  =  a  +  invphi  *  h  yd  =  f ( d ) devuelve  ( a ,  d )  si  yc  <  yd  de lo contrario  ( c ,  b )

Algoritmo recursivo

clase pública GoldenSectionSearch { pública estática final doble invphi = ( Math . sqrt ( 5.0 ) - 1 ) / 2.0 ; pública estática final doble invphi2 = ( 3 - Math . sqrt ( 5.0 )) / 2.0 ;                          Interfaz pública Función { doble de ( doble x ); }        // Devuelve el subintervalo de [a,b] que contiene el mínimo de f public static double [] gss ( Función f , doble a , doble b , doble tol ) { return gss ( f , a , b , tol , b - a , verdadero , 0 , 0 , verdadero , 0 , 0 ); } private static double [] gss ( Función f , doble a , doble b , doble tol , doble h , booleano noC , doble c , doble fc , booleano noD , doble d , doble fd ) { if ( Math . abs ( h ) <= tol ) { return new double [] { a , b }; } if ( noC ) { c = a + invphi2 * h ; fc = f . of ( c ); } if ( noD ) { d = a + invphi * h ; fd = f . of ( d ); } if ( fc < fd ) { // fc > fd para encontrar el máximo retorno gss ( f , a , d , tol , h * invphi , true , 0 , 0 , false , c , fc ); } else { return gss ( f ,                                                                                                                       c , b , tol , h * invphi , falso , d , fd , verdadero , 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 ) ; System.out.println ( "[" + ans [ 0 ] + " ," + ans [ 1 ] + " ] " ); // [1.9999959837979107,2.0000050911830893] } }                                         

importar  matemáticasinvphi  =  ( math . sqrt ( 5 )  -  1 )  /  2  # 1 / phi invphi2  =  ( 3  -  math . 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 único mínimo local 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)  >>> print (c, d)  1.9999959837979107 2.0000050911830893  """ ( a ,  b )  =  ( min ( a ,  b ),  max ( a ,  b ))  si  h  es  Ninguno :  h  =  b  -  a  si  h  <=  tol :  return  ( a ,  b )  si  c  es  Ninguno :  c  =  a  +  invphi2  *  h  si  d  es  Ninguno :  d  =  a  +  invphi  *  h  si  fc  es  Ninguno :  fc  =  f ( c )  si  fd  es  Ninguno :  fd  =  f ( d )  si  fc  <  fd :  # fc > fd para encontrar el máximo  return  gssrec ( f ,  a ,  d ,  tol ,  h  *  invphi ,  c = Ninguno ,  fc = Ninguno ,  d = c ,  fd = fc )  else :  return  gssrec ( f ,  c ,  b ,  tol ,  h  *  invphi ,  c = d ,  fc = fd ,  d = Ninguno ,  fd = Ninguno )

Algoritmos relacionados

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 o máximo local. Para aproximar las posiciones de sondeo de la búsqueda de la sección áurea mientras se sondean solo los índices de secuencia de números enteros, la variante del algoritmo para este caso normalmente mantiene un corchete de la solución en el que la longitud del intervalo corcheteado 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 del máximo (mínimo) de una función unimodal en un intervalo.

Método de bisección

El método de bisección es un algoritmo similar para hallar un cero de una función. Nótese que, para encerrar un cero, solo se necesitan dos puntos, en lugar de tres. La razón del intervalo disminuye en 2 en cada paso, en lugar de en la proporción áurea.

Véase también

• Búsqueda ternaria
• El método de Brent
• Búsqueda binaria

Referencias

• Kiefer, J. (1953), "Búsqueda secuencial de minimax para un máximo", Actas de la American Mathematical Society , 4 (3): 502–506, doi : 10.2307/2032161 , JSTOR  2032161, MR  0055639
• Avriel, Mordecai; Wilde, Douglass J. (1966), "Prueba de optimalidad para la técnica de búsqueda simétrica de Fibonacci", Fibonacci Quarterly , 4 : 265–269, MR  0208812

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 10.2. Búsqueda de la sección áurea en una dimensión", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-82-5-33-0 978-0-521-88068-8, archivado desde el original el 11-08-2011 , consultado el 12-08-2011