170
6 Simulation numérique des modèles
6.3.1.6 Un mot sur la recherche linéaire
Le principal message à retenir de cette section tient en ceci : comme aux itérations intermédiaires, la direction de descente n’est pas celle qui conduit au
minimum, il ne sert à rien de mener la recherche linéaire jusqu’à son terme
à chaque itération ; il faut s’arrêter dès qu’on estime avoir “suffisamment progressé”. La règle d’arrêt considérée à l’heure actuelle comme la plus efficace
est la règle de Wolfe ; elle consiste à choisir deux réels 0 < m 1 < m 2 < 1 et à
imposer l’arrêt dès que les deux conditions
q(t) ≤ q(0) + m 1 tq
(0)
(6.34)
et
q
(t) ≥ m 2 q
(0).
(6.35)
sont satisfaites. La première condition impose que le pas ne soit pas trop
grand : si elle n’est pas satisfaite, cela veut dire en effet qu’on se trouve “sur
l’autre versant de la cuvette”, i.e. qu’on a dépassé le minimum. La deuxième
condition exprime que la dérivée a suffisament décru, ce qui signifie que le pas
n’est pas trop petit (on n’est pas resté dans l’immédiat voisinage de x k ).
Le principe de la recherche linéaire est ensuite de chercher une longueur de
descente t à l’intérieur d’un intervalle de confiance ]t g , t d [ que l’on réduit au
cours des itérations. A l’origine de la recherche on prend t g = 0 et t d = +∞
et on se donne un pas initial t > 0. Trois cas peuvent se produire
1. t vérifie les conditions d’arrêt (i.e. les deux conditions (6.34) et (6.35) pour
la règle de Wolfe), auquel cas on a terminé ;
2. t est trop grand (i.e. t ne vérifie pas (6.34)), auquel cas on pose t d = t et
on cherche un nouveau t ∈]t g , t d [ par interpolation,
3. t est trop petit (i.e. t ne vérifie pas (6.35)), auquel cas on pose t g = t
et on cherche un nouveau t ∈]t g , t d [ par interpolation si t d < +∞ et par
extrapolation si t d = +∞.
Les techniques les plus simples consistent à prendre t = (t g + t d )/2 pour
l’interpolation, t nouveau = a t ancien avec a > 1 pour l’extrapolation. On
utilise plutôt en pratique, pour l’interpolation comme pour l’extrapolation, un
ajustement cubique (ou par un polynôme de degré 5 si les dérivées secondes
de q sont accessibles) consistant à prendre pour nouveau t le minimum du
polynôme interpolant les valeurs de q et de ses dérivées (ainsi que de ses
dérivées secondes pour l’ajustement par un polynôme de degré 5) en les deux
dernières valeurs de t. On renvoie à [40] pour les détails techniques.
Reste maintenant à choisir le pas initial. Dans la méthode de quasi-Newton,
un choix naturel (t = 1) est fourni par l’algorithme. Pour la méthode du
gradient conjugué non linéaire on peut utiliser l’initialisation de Fletcher t =
−2(f (x k−1 ) − f (x k ))/(g k · d k ).
6 Simulation numérique des modèles
6.3.1.6 Un mot sur la recherche linéaire
Le principal message à retenir de cette section tient en ceci : comme aux itérations intermédiaires, la direction de descente n’est pas celle qui conduit au
minimum, il ne sert à rien de mener la recherche linéaire jusqu’à son terme
à chaque itération ; il faut s’arrêter dès qu’on estime avoir “suffisamment progressé”. La règle d’arrêt considérée à l’heure actuelle comme la plus efficace
est la règle de Wolfe ; elle consiste à choisir deux réels 0 < m 1 < m 2 < 1 et à
imposer l’arrêt dès que les deux conditions
q(t) ≤ q(0) + m 1 tq
(0)
(6.34)
et
q
(t) ≥ m 2 q
(0).
(6.35)
sont satisfaites. La première condition impose que le pas ne soit pas trop
grand : si elle n’est pas satisfaite, cela veut dire en effet qu’on se trouve “sur
l’autre versant de la cuvette”, i.e. qu’on a dépassé le minimum. La deuxième
condition exprime que la dérivée a suffisament décru, ce qui signifie que le pas
n’est pas trop petit (on n’est pas resté dans l’immédiat voisinage de x k ).
Le principe de la recherche linéaire est ensuite de chercher une longueur de
descente t à l’intérieur d’un intervalle de confiance ]t g , t d [ que l’on réduit au
cours des itérations. A l’origine de la recherche on prend t g = 0 et t d = +∞
et on se donne un pas initial t > 0. Trois cas peuvent se produire
1. t vérifie les conditions d’arrêt (i.e. les deux conditions (6.34) et (6.35) pour
la règle de Wolfe), auquel cas on a terminé ;
2. t est trop grand (i.e. t ne vérifie pas (6.34)), auquel cas on pose t d = t et
on cherche un nouveau t ∈]t g , t d [ par interpolation,
3. t est trop petit (i.e. t ne vérifie pas (6.35)), auquel cas on pose t g = t
et on cherche un nouveau t ∈]t g , t d [ par interpolation si t d < +∞ et par
extrapolation si t d = +∞.
Les techniques les plus simples consistent à prendre t = (t g + t d )/2 pour
l’interpolation, t nouveau = a t ancien avec a > 1 pour l’extrapolation. On
utilise plutôt en pratique, pour l’interpolation comme pour l’extrapolation, un
ajustement cubique (ou par un polynôme de degré 5 si les dérivées secondes
de q sont accessibles) consistant à prendre pour nouveau t le minimum du
polynôme interpolant les valeurs de q et de ses dérivées (ainsi que de ses
dérivées secondes pour l’ajustement par un polynôme de degré 5) en les deux
dernières valeurs de t. On renvoie à [40] pour les détails techniques.
Reste maintenant à choisir le pas initial. Dans la méthode de quasi-Newton,
un choix naturel (t = 1) est fourni par l’algorithme. Pour la méthode du
gradient conjugué non linéaire on peut utiliser l’initialisation de Fletcher t =
−2(f (x k−1 ) − f (x k ))/(g k · d k ).