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

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 ∗ ) ≈ $f : R \rightarrow R, f \in C^1$$x^*$$f'(x^*) \approx 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 ) = $f(x_k)$$f'(x_k)$$f(x_{k+1})$$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 ( x k + 1 - x k ) = f ( x k + 1 ) Q ′ ( x k + 1 - x k ) = f ′ ( x k + 1$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})$

Je résous l'équation quadratique: $(1): Q'(x^*-x_k) = 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)=\mathcal{O}(x^2)$ comme la solution de forme fermée pour $(1)$ divise par $a$ 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 $Q_2(x)=bx^2+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 | < ϵ τ ϵ τ $a \equiv 0$$|a| < \epsilon\tau$$\epsilon$$\tau$$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$$\phi(\alpha)=f(\bar{x}_k+\alpha \bar{p_k})$$f'(x^*) \approx 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.

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(x_{k-1})$$f(x_0)$$x_k$$x_{k-1}$$x_0$

J'espère que cela t'aides.

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