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

1. $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. $\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 $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 $\alpha _{k}$ permette de décroître suffisamment $f$, et la condition de courbure assure que le taux d'accroissement de la fonction $\phi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ en $\alpha _{k}$ est plus grand que $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 $\phi$ dépendant de $\alpha \in \mathbb {R}$. Cependant, les conditions peuvent donner une valeur pour le pas qui n'est pas proche d'un minimum de $\phi$. Si on modifie la condition de courbure de la manière suivante :

2.a) $\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 $\alpha _{k}$ est forcément proche d'un point critique de $\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é