Critères de Wolfe

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 : R n → R {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} } une fonction de classe C 1 {\displaystyle C^{1}} , et soit p k {\displaystyle \mathbf {p} _{k}} une direction de descente. Un pas α k {\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. f ( x k + α k p k ) ≤ f ( x k ) + c 1 α k p k T ∇ f ( x k ) {\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. p k T ∇ f ( x k + α k p k ) ≥ c 2 p k T ∇ f ( x k ) {\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 0 < c 1 < c 2 < 1 {\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 α k {\displaystyle \alpha _{k}} permette de décroître suffisamment f {\displaystyle f} , et la condition de courbure assure que le taux d'accroissement de la fonction ϕ ( α ) = f ( x k + α p k ) {\displaystyle \phi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})} en α k {\displaystyle \alpha _{k}} est plus grand que c 2 {\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 α ∈ R {\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) | p k T ∇ f ( x k + α k p k ) | ≤ c 2 | p k T ∇ f ( x k ) | {\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 α k {\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

  • icône décorative Portail de l'analyse