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

9

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 ) 0f:RR,fC1xf(x)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(xk)f(xk)f(xk+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(xk+1)0xk<x<xk+1Q(x)=ax3+bx2+cx+dQ(0)=f(xk)Q(0)=f(xk)Q ( x k + 1 - x k ) = f ( x k + 1 )Q(xk+1xk)=f(xk+1)Q(xk+1xk)=f(xk+1)

Resuelvo la ecuación cuadrática: para mi buscado usando la solución de forma cerrada.x (1):Q(xxk)=0x

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 0f(x)=O(x2)(1)a0

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 )aQ2(x)=bx2+cx+db,c,dQ(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 | < ϵ τ ϵ τ fa0|a|<ϵτϵτ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 ) 0fϕ(α)=f(x¯k+αpk¯)f(x)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.

Emily L.
fuente

Respuestas:

4

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 0f(xk1)f(x0)xkxk1x0

Espero que esto ayude.

LKlevin
fuente
Editado para mayor claridad. Por "usar " quiero decir que hice un ajuste cúbico a y descubrí que tengo que ya es un polinomio cuadrático. Y la pregunta era si los coeficientes obtenidos para este ajuste son razonables de usar para hacer una interpolación o si debo volver a calcular nuevos coeficientes para un ajuste cuadrático típico. Q ( x ) = a x 3 + b x 2 + c x + d un 0 Q ( x ) = b x 2 + c x + d b , c , db,c,dQ(x)=ax3+bx2+cx+da0Q(x)=bx2+cx+db,c,d
Emily L.
Ahh, claro, por supuesto. No veo ningún problema en usar los coeficientes desde un punto de vista numérico. El único punto en el que creo que importaría, está muy cerca de la solución donde terminarías de todos modos.
LKlevin
¿Puede motivar su respuesta con el cálculo de la cúbica y la verificación de valores "malos"? ¿Por qué es seguro hacerlo cuando o ? un 0a<<ba0
Emily L.
Cuando , y serán aproximadamente los que está para el caso cuadrático. Como la búsqueda de líneas BFGS es bastante robusta, debería usarlas, incluso si no son completamente precisas. Mientras obedezca las condiciones de Wolfe obtendrá convergencia. En cuanto a los valores "malos", siempre que la computadora pueda hacer los cálculos con precisión con la precisión que necesita, todo está bien. Cuando no puede, comenzarás a ver inf y NaN. b , c da0b,cd
LKlevin
4

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 ).

Juan pablo frias
fuente
¡Bienvenido a SciComp.SE! He formateado tu publicación para que sea más fácil encontrar el artículo. Si puede encontrar un enlace a la implementación de Nocedal, sería útil.
Christian Clason