1 Recherche linéaire par la règle de Wolfe
1.1 Principes généraux
Soit f une fonction à minimiser. On note :
— x(k) le point courant,
— g (k) le gradient de f en x(k) ,
— d(k) la direction de descente,
— α(k) le pas de descente.
La règle de Wolfe a pour but de déterminer un pas α(k) vérifiant les deux conditions suivantes :
1. la fonction f doit décroı̂tre de manière significative :
>
f (x(k) + α(k) d(k) ) ≤ f (x(k) ) + ω1 α(k) g (k) d(k) , (1a)
2. le pas α(k) doit être suffisamment grand :
> >
∇f (x(k) + α(k) d(k) ) d(k) ≥ ω2 g (k) d(k) , (1b)
avec 0 < ω1 < ω2 < 1 (typiquement, ω1 = 0.1 et ω2 = 0.9).
1.2 Algorithme de résolution
La procédure itérative suivante, inspirée d’une mise en œuvre due à Flechter & Lemaréchal, permet de
manière particulièrement simple de calculer un pas α(k) vérifiant les deux conditions de Wolfe.
L’initialisation consiste à poser α = 0 et α = +∞ et à se donner un pas α(k,1) ∈]α, α[. À chaque itération `
de l’algorithme de Flechter-Lemaréchal, on effectue le test suivant afin de modifier la valeur de α(k,`) jusqu’à
obtenir un pas vérifiant les deux conditions de Wolfe :
• si α(k,`) ne vérifie pas la condition (1a) :
- on diminue la borne supérieure : α = α(k,`) ,
- on choisit un nouveau pas : α(k,`+1) = 12 (α + α),
• sinon,
? si α(k,`) ne vérifie pas la condition (1b) :
- on augmente la borne inférieure : α = α(k,`) ,
- on choisit un nouveau pas :
. α(k,`+1) = 2α si α = +∞,
(k,`+1) 1
. α = 2 (α + α) sinon,
? sinon, le pas α(k,`) vérifie la règle de Wolfe
et servira à se déplacer dans la direction d(k) :
x(k+1) = x(k) + α(k,`) d(k) .
On notera que les conditions (1a) et (1b) ne sont pas traitées de manière symétrique dans cette procédure.
En effet, la seconde condition de Wolfe n’est testée que si la première condition est satisfaite. Par contre, la
modification de la borne inférieure α dans le cas où la seconde condition n’est pas vérifiée oblige à refaire le
test de la première condition.
1.3 Mise en œuvre
1.3.1 Terminaison de l’algorithme
D’un point de vue pratique, et bien que l’on puisse montrer, sous des conditions raisonnables, que
l’algorithme de Flechter-Lemaréchal fournit un pas α(k,`) satisfaisant les deux conditions de Wolfe en un
nombre fini d’étapes, il peut arriver que cet algorithme nécessite un très grand nombre d’étapes pour obtenir
une valeur correcte du pas. C’est pourquoi il est souhaitable, lors de sa programmation, de contrôler le nombre
maximal d’essais de pas de l’algorithme à l’aide d’un test d’arrêt. Cependant, ce test ne doit pas porter sur
la longueur de l’intervalle de recherche en α, mais plutôt sur le déplacement en x correspondant. Ceci
revient donc à se donner une résolution en x, car cette dernière grandeur a une interprétation physique qui
devrait permettre à l’utilisateur du code de connaı̂tre l’ordre de grandeur de ses variations. Notant x(k,`) =
x(k) + α(k,`) d(k) le point proposé à la `-ème étape de l’algorithme de Flechter-Lemaréchal, le test d’arrêt
portera donc sur la quantité :
kx(k,`+1) − x(k,`) k = |α(k,`+1) − α(k,`) | kd(k) k .
1.3.2 Pas initial de l’algorithme
Il reste enfin à déterminer la valeur initiale α(k,0) avec laquelle on initialise cette procédure. Dans le
cas d’une utilisation dans le cadre d’un algorithme de type Newton ou quasi-Newton, le pas unité est tout
indiqué. Pour d’autres méthodes comme le gradient ou le gradient conjugué, il n’existe pas de pas naturel
évident . Une possibilité consiste à déterminer ce pas en se basant sur la décroissance attendue ∆
(k) de
la fonction f . Pour cela, on considère une approximation quadratique de la fonction α 7→ f (x(k) + α d(k) ), à
savoir :
(k) (k) 1 (k)
ϕ(k) (α) = a0 + a1 α + a2 α2 .
2
Les deux premiers coefficients de cette approximation sont facilement disponibles :
(k)
a0 = f (x(k) ) ,
(k) >
a1 = g (k) d(k) .
(k)
Plutôt que d’obtenir le dernier coefficient a2 à l’aide de la matrice hessienne de f , on le détermine en
imposant que la décroissance maximale de ϕ(k) soit égale à la décroissance attendue ∆(k) de f :
∆(k) = ϕ(k) (0) − min ϕ(k) (α) ,
α≥0
d’où :
(k) 2
(k) a
a2 = 1 (k) .
2∆
On en déduit alors le pas initial α(k,0) , qui est celui donnant la décroissance maximale de l’approximation
quadratique ainsi définie. On obtient :
(k)
a1 2∆(k) 2∆(k)
α(k,0) = − (k)
=− (k)
=− >
.
a2 a1 g (k) d(k)
Ce pas est appelé pas de Flechter.
Remarque 1. La détermination du pas initial est donc reportée sur la détermination de la décroissance
attendue ∆(k) . Cette dernière valeur peut provenir de considérations directes sur le problème d’optimisation
que l’on doit résoudre : par exemple, si l’on dispose d’une bonne approximation d’un minorant de la fonc-
tion f , la décroissance attendue pourra être prise égale à une (petite) fraction de l’écart entre f (x(k) ) et ce
minorant.
2 Directions de descente
Soit f une fonction à minimiser. On note :
— x(k) le point courant,
— g (k) le gradient de f en x(k) .
On cherche une direction d(k) dans laquelle la fonction f décroisse à partir du point x(k) :
∃α(k) > 0 , f (x(k) + α(k) d(k) ) < f (x(k) ) ,
>
inégalité induite par la relation : g (k) d(k) < 0. Le pas α(k) est en général déterminé par recherche linéaire.
2.1 Formule de Polak-Ribière
Dans les méthodes de type gradient conjugué, la direction de descente d(k) au point x(k) est de la
forme :
−g (1)
(k) si k = 1
d = (k) (k) (k−1) . (2)
−g + β d sinon
Dans la mise en œuvre de Polak-Ribière, le coefficient β (k) est donné par la formule :
>
g (k) g (k) − g (k−1)
(k)
β = 2 . (3)
g (k−1)
2.2 Formule de BFGS inverse
Dans les méthodes de type quasi-Newton, la direction de descente est de la forme :
d(k) = −W (k) g (k) , (4)
où W (k) représente une approximation de l’inverse de la matrice hessienne H (k) de f au point x(k) . Cette
approximation est remise à jour à chaque itération de l’algorithme.
Avec les notations suivantes :
(k)
— δx = x(k) − x(k−1) ,
(k)
— δg = g (k) − g (k−1) ,
la formule de remise à jour de BFGS (Broyden-Flechter-Goldfarb-Shanno) est donnée par :
(k) (k) > (k) (k) > (k) (k) >
(k) δx δg (k−1) δg δx δx δx
W = I− W I− + . (5)
(k) > (k) (k) > (k) (k) > (k)
δg δx δg δx δg δx
A défaut de meilleure idée, la matrice W (1) initialisant cette formule est prise égale à l’identité.
Remarque 2. Lorsque le pas α(k) est déterminé par la règle de Wolfe, la relation (1b) implique :
> >
δg(k) δx(k) ≥ α(k) (ω2 − 1)g (k) d(k) > 0 . (6)
Si l’on choisit une matrice initiale W (1) définie positive, la formule de mise à jour (5) génère alors des
matrice W (k) qui sont aussi définies positives. C’est pourquoi on utilise toujours la règle de Wolfe pour
effectuer la recherche linéaire dans l’algorithme de BFGS.
P. Carpentier, 03 mars 2020.