¿La búsqueda ternaria es menos eficiente que este algoritmo relacionado?

Question

El algoritmo ternary search es un algoritmo rápido para encontrar el mínimo o máximo de una unimodal function, una función que o bien aumenta y luego disminuye o disminuye y luego aumenta. Supongamos que estamos tratando con una función que disminuye, luego aumenta, y que queremos encontrar el mínimo de valor. La búsqueda ternaria funciona utilizando la siguiente recursión:

• Si el tamaño de la ventana es "suficientemente pequeño", simplemente devuelva su punto medio.
• lo contrario:
  • evaluar la función en los límites izquierdo y derecho; llame a los valores l y r.
  • Evaluar la función en 1/3 y 2/3 puntos; llaman a los valores M y m
  • Si m < m , entonces estamos en la creciente región de la función y el mínimo no puede ser de entre m y r .
  • Si m > m , entonces estamos en la región de la disminución de la función puede el mínimo no puede ser de entre l y m
  • recursivamente buscar en los 2/3 que no eran' t descartado.

Este algoritmo funciona de forma rápida, ya que puede mantener lanzando un tercio de los valores en cada iteración.

Sin embargo, siento que me falta algo porque creo que podemos hacer que este algoritmo funcione mucho más rápido. En particular, observe que siempre estamos tirando uno de los tercios del rango entre un límite y uno de los puntos de prueba. Esto significa que conservamos la región entre el punto de prueba y el otro límite. Debido a que la búsqueda ternaria selecciona los puntos de prueba en 1/3 puntos, esto significa que conservamos 2/3 de los valores en cada punto. ¿Qué pasa si en lugar de sondear en el 1/3 y 2/3 puntos, probamos en el 1/2 - y épsilon; y 1/2 + & epsilon; puntos para un extremadamente pequeño épsilon ;? Esto significaría que estaríamos lanzando 1/2 - y épsilon; del rango en cada paso, lo que significa que el tamaño del rango disminuiría mucho más rápido que si simplemente lanzáramos 1/3 de los elementos cada vez.

Como ejemplo, si selecciono & epsilon; = 1/1000, arrojamos 999/2000 del rango para buscar en cada iteración. La fracción restante después de algún número de iteraciones se muestra aquí (búsqueda ternario está a la izquierda, mi algoritmo está a la derecha :)

1 :    1.0 >=    1.0 
2 :  0.666666666667 >=    0.5005 
3 :  0.444444444444 >=   0.25050025 
4 :  0.296296296296 >=  0.125375375125 
5 :  0.197530864198 >= 0.0627503752501 
6 :  0.131687242798 >= 0.0314065628127 
7 : 0.0877914951989 >= 0.0157189846877 
8 : 0.0585276634659 >= 0.00786735183621 
9 : 0.0390184423106 >= 0.00393760959402 
10 : 0.0260122948737 >= 0.00197077360181 
11 : 0.0173415299158 >= 0.000986372187705 
12 : 0.0115610199439 >= 0.000493679279947 
13 : 0.00770734662926 >= 0.000247086479613 
14 : 0.00513823108617 >= 0.00
15 : 0.00342548739078 >= 6.18952249147e-05 
16 : 0.00228365826052 >= 3.09785600698e-05 
17 : 0.00152243884035 >= 1.55047693149e-05 
18 : 0.00101495922690 >= 7.76013704213e-06 
19 : 0.000676639484599 >= 3.88394858959e-06 

¿Es esta versión modificada del algoritmo sólo "mejor" que la versión original? ¿O hay algo que me falta aquí que significaría que no debería usar la estrategia modificada para elegir los puntos de prueba?

Answer 1

Esta versión ciertamente convergerá más rápido, pero podría ser más propensa a problemas de precisión de coma flotante. Por ejemplo, ¿qué pasa si obtienes m + eps = m? Esa es una posibilidad real si m es grande, por ejemplo. Entonces hay una compensación entre exactitud y tasa de convergencia.El mejor algoritmo de esta clase podría decirse que es Golden Section Search, que es rápido y preciso.

Answer 2

Si una función es unimodal, entonces g (y) = F (y + ε) - F (y) cruza el cero una sola vez, al aumentar y desde el límite izquierdo al derecho.

Básicamente, lo que propone en su segundo/algoritmo mejorado es una búsqueda binaria para el cruce por cero (raíz) de g (y). Suponga que está minimizando, por lo que F (y) tiene un mínimo. Entonces G (y) es negativo por un tiempo, y luego positivo. Por lo tanto, si g (x) < 0, entonces la raíz es mayor que x (o más precisa: x + ε), y si g (x)> 0, entonces la raíz es menor que x.

Esto es más rápido (peor caso) que su primer/algoritmo original, porque la región donde se encuentra el mínimo se reduce a la mitad en cada paso, en lugar de multiplicarse por 2/3.