Critères de Wolfe

En optimisation, les critères de Wolfe sont un ensemble d'inégalités permettant d'optimiser la méthode de recherche linéaire ; plus précisément, cela permet de sélectionner un pas adéquat pour la recherche linéaire. Ils portent le nom de Philip Wolfe.

Description

Soit ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ une fonction de classe ${\displaystyle C^{1}}$, et soit ${\displaystyle \mathbf {p} _{k}}$ une direction de descente. Un pas ${\displaystyle \alpha _{k}}$ est considéré comme satisfaisant les critères de Wolfe si les deux inégalités suivantes sont vérifiées :

1. ${\displaystyle f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq f(\mathbf {x} _{k})+c_{1}\alpha _{k}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})}$ ;
2. ${\displaystyle \mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\geq c_{2}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})}$.

avec ${\displaystyle 0<c_{1}<c_{2}<1}$.

La première inégalité est connue sous le nom de condition d'Armijo (ou condition de Goldstein ou condition de Goldstein-Armijo) et la seconde comme la condition de courbure. La condition d'Armijo impose que ${\displaystyle \alpha _{k}}$ permette de décroître suffisamment ${\displaystyle f}$, et la condition de courbure assure que le taux d'accroissement de la fonction ${\displaystyle \phi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ en ${\displaystyle \alpha _{k}}$ est plus grand que ${\displaystyle c_{2}}$ fois celui en 0.

Les critères de Wolfe donnent une façon économique de point de vue algorithmique de calculer le pas permettant de diminuer ${\displaystyle \phi }$ dépendant de ${\displaystyle \alpha \in \mathbb {R} }$. Cependant, les conditions peuvent donner une valeur pour le pas qui n'est pas proche d'un minimum de ${\displaystyle \phi }$. Si on modifie la condition de courbure de la manière suivante :

2.a) ${\displaystyle \left|\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\right|\leq c_{2}\left|\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})\right|}$

alors les conditions 1 et 2.a) prises ensemble sont appelées conditions fortes de Wolfe, puisque ${\displaystyle \alpha _{k}}$ est forcément proche d'un point critique de ${\displaystyle \phi }$.

Référence

(en) J. Nocedal et S. J. Wright, Numerical optimization, Springer Verlag, NY, 1999

Articles connexes

• Méthode de Quasi-Newton
• Méthode du gradient conjugué