Aide à décider entre l'interpolation cubique et quadratique dans la recherche en ligne

9

J'effectue une recherche de ligne dans le cadre d'un algorithme BFGS quasi-Newton. Dans une étape de la recherche de ligne, j'utilise une interpolation cubique pour me rapprocher du minimiseur local.

Soit la fonction d'intérêt. Je veux trouver un tel que .x f ( x ) 0f:RR,fC1xF(X)0

Soit , , et connus. Supposons également . J'ajuste un polynôme cubique sorte que , , Q (x_ {k +1} -x_ {k}) = f (x_ {k + 1}) et Q '(x_ {k + 1} -x_ {k}) = f' (x_ {k + 1}) .f ( x k ) f ( x k + 1 ) f ( x k + 1 ) 0 x k < x < x k + 1 Q ( x ) = a x 3 + b x 2 + c x + d Q ( 0 ) = fF(Xk)F(Xk)F(Xk+1)F(Xk+1)0xk<x<xk+1Q(x)=ax3+bx2+cx+dQ ( 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(0)=f(xk)Q(0)=f(xk)Q(xk+1xk)=f(xk+1)Q(xk+1xk)=f(xk+1)

Je résous l'équation quadratique: (1):Q(xxk)=0 pour mon x utilisant la solution de forme fermée.

Ce qui précède fonctionne bien dans la plupart des cas, sauf lorsque f(x)=O(x2) comme la solution de forme fermée pour (1) divise par une qui devient très proche ou exactement 0 .

Ma solution est de regarder a et si elle est "trop ​​petite" il suffit de prendre la solution de forme fermée pour le minimiseur du polynôme quadratique Q2(x)=bx2+cx+d pour lequel j'ai déjà les coefficients b,c,d de l'ajustement antérieur à Q(x) .

Ma question est: comment puis-je concevoir un bon test pour savoir quand prendre l'interpolation quadratique sur le cube? L'approche naïve pour tester est mauvaise pour des raisons numériques, donc je regarde où est la précision de la machine, mais je ne peux pas décider d'un bon qui soit invariant à l'échelle de .| a | < ϵ τ ϵ τ fa0|a|<ϵτϵτf

Question bonus: y a-t-il des problèmes numériques avec l'utilisation des coefficients, , de l'ajustement cubique échoué ou dois-je effectuer un nouvel ajustement quadratique avec une méthode appropriée de calcul des coefficients?b,c,d

Modifier pour clarification: Dans ma question, est en fait ce qui est communément appelé dans la littérature. Je viens de simplifier la formulation de la question. Le problème d'optimisation que je résous est non linéaire en 6 dimensions. Et je suis bien conscient que les conditions de Wolfe sont suffisantes pour la recherche de ligne BFGS, déclarant donc que j'étais intéressé par ; Je cherche quelque chose qui satisfera les fortes conditions de Wolfe et prendre le minimiseur de l'approximation cubique est une bonne étape en cours de route.ϕ ( α ) = f ( ˉ x k + α ¯fϕ(α)=f(x¯k+αpk¯)f(x)0

La question ne portait pas sur les BFGS, mais plutôt sur la façon de déterminer quand le coefficient cubique est suffisamment petit pour qu'une approximation quadratique soit plus appropriée.

Edit 2: Mettre à jour la notation, les équations sont inchangées.

Emily L.
la source

Réponses:

4

Hmm ... l'interpolation cubique n'est pas inconnue pour la recherche de ligne, mais généralement exagérée.

Si je lis correctement votre problème, n'est qu'un scalaire? Dans ce cas, BFGS n'est probablement pas le moyen le plus efficace de résoudre votre problème. Les algorithmes d'optimisation scalaire comme la méthode de Brenth sont susceptibles de résoudre votre problème plus rapidement.x

Il existe un certain nombre d'algorithmes de recherche de ligne pour BFGS. Pour mes propres applications, en utilisant le BFGS à mémoire limitée (L-BFGS), cette recherche de ligne fonctionne très bien. N'oubliez pas que vous n'avez qu'à satisfaire aux conditions Wolfe, et vous ne gagnerez probablement pas grand-chose en trouvant le minimiseur exact.

Quoi qu'il en soit, pour répondre à votre question: je considérerais simplement de passer au polynôme quadratique si la résolution du cubique donne de "mauvaises" valeurs telles que NaN ou Inf (comme cela se fait ici ).

Je ne sais pas trop ce que vous voulez dire en utilisant ? Ces coefficients pour l'ajustement cubique ne seront pas les mêmes que pour l'ajustement quadratique, vous ne pouvez donc pas les réutiliser.b,c,d

Enfin, vous voudrez peut-être utiliser , plutôt que f ( x 0 ) , car votre fonction ne sera (probablement) qu'approximativement cubique ou quadratique localement, et x k et devraient être plus proches les uns des autres (et de la solution) que .f(xk1)f(x0)xkxk1x0

J'espère que cela t'aides.

LKlevin
la source
Modifié pour plus de clarté. Par "en utilisant ", je veux dire que j'ai fait un ajustement cubique à Q ( x ) = a x 3 + b x 2 + c x + d et a constaté que a 0 ainsi j'ai Q ( x ) = b x 2 + c x + d qui est déjà un polynôme quadratique. Et la question était de savoir si les coefficients b , c , db,c,dQ(x)=ax3+bx2+cx+da0Q(x)=bx2+cx+db,c,obtenus pour cet ajustement sont judicieux à utiliser pour effectuer une interpolation ou si je dois recalculer de nouveaux coefficients pour un ajustement quadratique typique.
Emily L.
Ahh, bien sûr. Je ne vois aucun problème à utiliser les coefficients d'un point de vue numérique. Le seul point où je pense que cela importerait, est très proche de la solution où vous mettriez fin de toute façon.
LKlevin
Pouvez-vous motiver votre réponse en calculant le cube et en vérifiant les "mauvaises" valeurs? Pourquoi est - il sécuritaire de le faire quand ou une 0 ? a<<ba0
Emily L.
Quand , b , c et d seront approximativement ceux du cas quadratique. Comme la recherche de lignes BFGS est assez robuste, vous devriez pouvoir les utiliser, même si elles ne sont pas complètement précises. Tant que vous respectez les conditions Wolfe, vous obtiendrez une convergence. Quant aux "mauvaises" valeurs, tant que l'ordinateur peut effectuer avec précision les calculs avec la précision dont vous avez besoin, tout va bien. Si ce n'est pas le cas, vous commencerez à voir inf et NaN. a0b,cd
LKlevin
4

Il y a un article de Moré, mis en œuvre par Nocedal, à ce sujet:

Jorge J. Moré et David J. Thuente. 1994. Algorithmes de recherche en ligne avec une diminution suffisante garantie. ACM Trans. Math. Softw. 20, 3 (septembre 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( préimpression ).

Juan Pablo Frias
la source
Bienvenue sur SciComp.SE! J'ai formaté votre message pour faciliter la recherche du papier. Si vous pouvez trouver un lien vers la mise en œuvre de Nocedal, ce serait utile.
Christian Clason