Ayuda a decidir entre interpolación cúbica y cuadrática en la búsqueda de línea

Estoy realizando una búsqueda de línea como parte de un algoritmo cuasi-Newton BFGS. En un paso de la búsqueda de línea, uso una interpolación cúbica para acercarme al minimizador local.

Sea ser la función de interés. Quiero encontrar una tal que .x ∗ f ′ ( x ∗ ) ≈ $f : R \rightarrow R, f \in C^1$$x^*$$f'(x^*) \approx 0$

Deje que , , y sean conocidas. Supongamos también . Encajo un polinomio cúbico para que , , y .f ′ ( x k ) f ( x k + 1$f(x_k)$$f'(x_k)$$f(x_{k+1})$0 ≤ x k < x ∗ < x k + 1 Q ( x ) = a x 3 + b x 2 + c x + d Q ( 0 ) = f ( x k ) Q ′ ( 0 ) = f ′ ( x k ) Q $f'(x_{k+1})$$0\le x_k<x^*<x_{k+1}$$Q(x)=ax^3+bx^2+cx+d$$Q(0)=f(x_k)$$Q'(0)=f'(x_k)$Q ′ ( x k + 1 - x k ) = f ′ ( x k + 1$Q(x_{k+1}-x_{k})=f(x_{k+1})$$Q'(x_{k+1}-x_{k})=f'(x_{k+1})$

Resuelvo la ecuación cuadrática: para mi buscado usando la solución de forma cerrada.x $(1): Q'(x^*-x_k) = 0$$x^*$

Lo anterior funciona bien en la mayoría de los casos, excepto cuando ya que la solución de forma cerrada para divide por que se acerca mucho o es exactamente .( 1 ) a $f(x)=\mathcal{O}(x^2)$$(1)$$a$$0$

Mi solución es mirar a y si es "demasiado pequeña" simplemente tomar la solución de forma cerrada para el minimizador de la polinomio cuadrático para los que ya tengo los coeficientes del ajuste anterior a .Q 2 ( x ) = b x 2 + c x + d b , c , d Q ( x $a$$Q_2(x)=bx^2+cx+d$$b,c,d$$Q(x)$

Mi pregunta es: ¿cómo creo una buena prueba para cuándo tomar la interpolación cuadrática sobre el cúbico? El enfoque ingenuo para probar a es malo debido a razones numéricas, así que estoy mirando donde es la precisión de la máquina, pero no puedo decidir una buena que sea una escala invariante de .| a | < ϵ τ ϵ τ $a \equiv 0$$|a| < \epsilon\tau$$\epsilon$$\tau$$f$

Pregunta adicional: ¿Hay algún problema numérico con el uso de los coeficientes, , del ajuste cúbico fallido o debería realizar un nuevo ajuste cuadrático con la forma adecuada de calcular los coeficientes?$b,c,d$

Editar para aclarar: en mi pregunta, es en realidad lo que comúnmente se conoce como en la literatura. Simplemente simplifiqué la formulación de la pregunta. El problema de optimización que estoy resolviendo es no lineal en 6 dimensiones. Y soy muy consciente de que las condiciones de Wolfe son suficientes para la búsqueda de línea BFGS, por lo tanto, afirman que estaba interesado en ; Estoy buscando algo que satisfaga las fuertes condiciones de Wolfe y tomar el minimizador de la aproximación cúbica es un buen paso en el camino.ϕ ( α ) = f ( ˉ x k + α ¯ p k ) f ′ ( x ∗ ) ≈ $f$$\phi(\alpha)=f(\bar{x}_k+\alpha \bar{p_k})$$f'(x^*) \approx 0$

La pregunta no era sobre BFGS, sino cómo determinar cuándo el coeficiente cúbico es lo suficientemente pequeño como para que una aproximación cuadrática sea más apropiada.

Edición 2: Notación de actualización, las ecuaciones no cambian.

Hmm ... la interpolación cúbica no es desconocida para la búsqueda de línea, pero generalmente es exagerada.

Si estoy leyendo tu problema correctamente, ¿ es solo un escalar? En este caso, BFGS probablemente no sea la forma más eficiente de resolver su problema. Es probable que los algoritmos de optimización escalar como el método de Brenth resuelvan su problema más rápido.$x$

Hay varios algoritmos de búsqueda de línea para BFGS. Para mis propias aplicaciones, usando la memoria limitada BFGS (L-BFGS) esta búsqueda de líneas funciona muy bien. Recuerde que solo necesita satisfacer las condiciones de Wolfe, y es probable que no gane mucho al encontrar el minimizador exacto.

De todos modos, para responder realmente a su pregunta: consideraría simplemente cambiar al polinomio cuadrático si resolver el cúbico produce valores "malos" como NaN o Inf (como se hace aquí ).

No estoy muy seguro de lo que quieres decir con . Estos coeficientes para el ajuste cúbico no serán los mismos que para el ajuste cuadrático, por lo que no puede reutilizarlos.$b,c,d$

Por último, es posible que desee usar , en lugar de , ya que su función (probablemente) solo será aproximadamente cúbica o cuadrática localmente, y y deberían ser más cerca uno del otro (y la solución) que .f ( x 0 ) x k x k - 1 x $f(x_{k-1})$$f(x_0)$$x_k$$x_{k-1}$$x_0$

Espero que esto ayude.

Hay un documento de Moré, implementado por Nocedal, sobre eso:

Jorge J. Moré y David J. Thuente. 1994. Algoritmos de búsqueda de línea con disminución suficiente garantizada. ACM Trans. Matemáticas. Softw. 20, 3 (septiembre de 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( preimpresión ).