Direction de descente

En optimisation différentiable, qui est une discipline d'analyse numérique en mathématiques étudiant en particulier les algorithmes minimisant des fonctions différentiables sur des ensembles, une direction de descente est une direction le long de laquelle la fonction à minimiser a une dérivée directionnelle strictement négative. Ces directions sont utilisées par les méthodes à directions de descente. C'est le long de ces directions qu'un déplacement est effectué afin de trouver l'itéré suivant, en lequel la fonction à minimiser prend une valeur inférieure à celle qu'elle a en l'itéré courant. Des directions de descente peuvent être calculées par de nombreuses techniques dont les plus classiques sont présentées ci-dessous.

Définition

Soient E {\displaystyle \mathbb {E} } un espace vectoriel et f : E → R {\displaystyle f:\mathbb {E} \to \mathbb {R} } une fonction réelle définie sur E , {\displaystyle \mathbb {E} ,} admettant des dérivées directionnelles au point x ∈ E {\displaystyle x\in \mathbb {E} } considéré. On note

f ′ ( x ; d ) := lim t ↓ 0 f ( x + t d ) − f ( x ) t ∈ R {\displaystyle f'(x;d):=\lim _{t\downarrow 0}{\frac {f(x+td)-f(x)}{t}}\in \mathbb {R} }

la dérivée directionnelle (au sens de Dini) de f {\displaystyle f} en x ∈ E {\displaystyle x\in \mathbb {E} } dans la direction d ∈ E {\displaystyle d\in \mathbb {E} } . La notation t ↓ 0 {\displaystyle t\downarrow 0} signifie que le réel t {\displaystyle t} tend vers zéro dans R {\displaystyle \mathbb {R} } par des valeurs strictement positives.

La notion de direction de descente est surtout utilisée en optimisation numérique.

Direction de descente — Une direction de descente de f {\displaystyle f} en x {\displaystyle x} est un vecteur d ∈ E {\displaystyle d\in \mathbb {E} } tel que

f ′ ( x ; d ) < 0. {\displaystyle f'(x;d)<0.}

On en déduit que

∀ α > 0       petit : f ( x + α d ) < f ( x ) , {\displaystyle \forall \,\alpha >0~~~{\mbox{petit}}:\qquad f(x+\alpha d)<f(x),}

si bien que f {\displaystyle f} décroît en x {\displaystyle x} dans la direction d {\displaystyle d} . Cette propriété justifie le nom donné à cette direction. Certains auteurs utilisent cette dernière propriété comme définition d'une direction de descente ; cependant, comme cette propriété n'implique pas que la dérivée directionnelle soit strictement négative, elle n'est pas suffisamment forte pour les algorithmes à directions de descente.

Exemples de direction de descente

Il existe de nombreuses méthodes permettant de calculer une direction de descente. Les principales sont présentées dans cette section ; chacune avec ses propres caractéristiques. Un algorithme qui utilise une telle direction hérite d'elle son nom. Ainsi l'algorithme du gradient est l'algorithme à directions de descente qui utilise la direction du gradient, l'algorithme du gradient conjugué utilise la direction du gradient conjugué, etc.

On suppose dans cette section que E {\displaystyle \mathbb {E} } est un espace hilbertien, dont le produit scalaire est noté ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } et la norme associée ‖ ⋅ ‖ , {\displaystyle \|\cdot \|,} et que f : E → R {\displaystyle f:\mathbb {E} \to \mathbb {R} } est au moins une fois différentiable au point x {\displaystyle x} considéré. On note f ′ ( x ) {\displaystyle f'(x)} sa dérivée, qui est une application linéaire continue de E {\displaystyle \mathbb {E} } dans R {\displaystyle \mathbb {R} } , et f ′ ( x ) ⋅ d = f ′ ( x ; d ) {\displaystyle f'(x)\cdot d=f'(x;d)} la valeur en d ∈ E {\displaystyle d\in \mathbb {E} } de cette dérivée. Par le théorème de Riesz-Fréchet, il existe alors un vecteur ∇ f ( x ) ∈ E {\displaystyle \nabla f(x)\in \mathbb {E} } , appelé le gradient de f {\displaystyle f} en x {\displaystyle x} , défini par

∀ d ∈ E : f ′ ( x ) ⋅ d = ⟨ ∇ f ( x ) , d ⟩ . {\displaystyle \forall \,d\in \mathbb {E} :\qquad f'(x)\cdot d=\langle \nabla f(x),d\rangle .}

Direction du gradient

La direction du gradient d {\displaystyle d} est, en réalité, l'opposé du gradient :

d = − ∇ f ( x ) . {\displaystyle d=-\nabla f(x).}

Il s'agit bien d'une direction de descente si f ′ ( x ) ≠ 0 {\displaystyle f'(x)\neq 0} puisqu'alors

f ′ ( x ) ⋅ ( − ∇ f ( x ) ) = ⟨ ∇ f ( x ) , − ∇ f ( x ) ⟩ = − ‖ ∇ f ( x ) ‖ 2 < 0. {\displaystyle f'(x)\cdot (-\nabla f(x))=\langle \nabla f(x),-\nabla f(x)\rangle =-\|\nabla f(x)\|^{2}<0.}

L'algorithme du gradient, qui utilise les directions du gradient comme directions de descente, est lent et il vaut mieux l'éviter, d'autant plus qu'il existe d'autres directions aussi simples à calculer et conduisant à des algorithmes beaucoup plus efficaces, comme l'algorithme ℓ-BFGS (en) par exemple.

Direction du gradient conjugué

L'algorithme du gradient conjugué construit sa direction de descente en x {\displaystyle x} en ajoutant à l'opposé du gradient, la direction d − ∈ E {\displaystyle d_{-}\in \mathbb {E} } calculée à l'itéré précédent x − , {\displaystyle x_{-},} multipliée par un scalaire β ∈ R {\displaystyle \beta \in \mathbb {R} } , appelé le bêta de conjugaison :

d = − ∇ f ( x ) + β d − . {\displaystyle d=-\nabla f(x)+\beta \,d_{-}.}

À la première itération, il n'y a pas de direction précédente et l'algorithme prend alors simplement l'opposé du gradient. Il y a beaucoup de formules pour le bêta de conjugaison, sans que l'on puisse encore donner aujourd'hui une ligne de conduite claire.

Afin d'assurer qu'il s'agit d'une direction de descente, on considère l'égalité :

f ′ ( x ) ⋅ d = ⟨ ∇ f ( x ) , d ⟩ = − ‖ ∇ f ( x ) ‖ 2 + β ⟨ ∇ f ( x ) , d − ⟩ . {\displaystyle f'(x)\cdot d=\langle \nabla f(x),d\rangle =-\|\nabla f(x)\|^{2}+\beta \langle \nabla f(x),d_{-}\rangle .}

La dérivée directionnelle est donc strictement négative si les deux conditions suivantes sont vérifiées :

  1. f ′ ( x ) ≠ 0 , {\displaystyle f'(x)\neq 0,}
  2. ⟨ ∇ f ( x ) , d − ⟩ = 0 , {\displaystyle \langle \nabla f(x),d_{-}\rangle =0,} qui a lieu si x = x − + α − d − {\displaystyle x=x_{-}+\alpha _{-}d_{-}} où α − {\displaystyle \alpha _{-}} est un point stationnaire (dérivée nulle) de la fonction t ↦ f ( x − + t d − ) , {\displaystyle t\mapsto f(x_{-}+td_{-}),} ce qui revient à faire de la recherche linéaire exacte.

Cette seconde condition est aisément satisfaite lorsque f {\displaystyle f} est quadratique, ce qui est le cadre fonctionnel habituel de l'algorithme du gradient conjugué, puisqu'alors α − {\displaystyle \alpha _{-}} est donné explicitement par une formule.

Pour une fonction f {\displaystyle f} arbitraire, on a longtemps pensé que cette seconde condition devait aussi être satisfaite pour que la direction soit de descente, ce qui empêchait l'utilisation de cette approche algorithmique pour les problèmes non quadratiques car la seconde condition ne peut être réalisée exactement dans ce cas. On sait depuis les années 1985[1]-92[2] que des règles de recherche linéaire adaptées aux formules de β {\displaystyle \beta } permettent d'assurer la descente des directions et la convergence des algorithmes associés.

Direction de Newton

On suppose ici que la fonction f {\displaystyle f} à minimiser est deux fois différentiable en x {\displaystyle x} et on désigne par ∇ 2 f ( x ) {\displaystyle \nabla ^{2}f(x)} son hessien en x {\displaystyle x} , lequel est l'unique opérateur linéaire auto-adjoint ∇ 2 f ( x ) : E → E {\displaystyle \nabla ^{2}f(x):\mathbb {E} \to \mathbb {E} } vérifiant

∀ ( h , k ) ∈ E 2 : f ″ ( x ) ⋅ ( h , k ) = ⟨ ∇ 2 f ( x ) h , k ⟩ . {\displaystyle \forall \,(h,k)\in \mathbb {E} ^{2}:\qquad f''(x)\cdot (h,k)=\langle \nabla ^{2}f(x)h,k\rangle .}

La direction de Newton est définie en un point x {\displaystyle x} en lequel le hessien de f {\displaystyle f} est inversible par

d = − ( ∇ 2 f ( x ) ) − 1 ∇ f ( x ) . {\displaystyle d=-\left(\nabla ^{2}f(x)\right)^{-1}\nabla f(x).}

Cette direction est une direction de descente si

  • f ′ ( x ) ≠ 0 , {\displaystyle f'(x)\neq 0,}
  • ∇ 2 f ( x ) {\displaystyle \nabla ^{2}f(x)} est définie positive.

En effet

f ′ ( x ) ⋅ d = ⟨ ∇ f ( x ) , d ⟩ = − ⟨ ∇ f ( x ) , ∇ 2 f ( x ) − 1 ∇ f ( x ) ⟩ ⩽ − λ max − 1 ‖ ∇ f ( x ) ‖ 2 < 0 , {\displaystyle f'(x)\cdot d=\langle \nabla f(x),d\rangle =-\langle \nabla f(x),\nabla ^{2}f(x)^{-1}\nabla f(x)\rangle \leqslant -\lambda _{\max }^{-1}\|\nabla f(x)\|^{2}<0,}

où λ max {\displaystyle \lambda _{\max }} désigne la plus grande valeur propre de ∇ 2 f ( x ) {\displaystyle \nabla ^{2}f(x)} .

La seconde condition assurant le caractère descendant de la direction de Newton sera vérifiée dans le voisinage d'une solution vérifiant les conditions suffisantes d'optimalité du deuxième ordre.

Direction de quasi-Newton

Les algorithmes de quasi-Newton en optimisation définissent une direction de descente en prenant une approximation convenable du hessien du critère au moyen d'un opérateur M {\displaystyle M} auto-adjoint :

M ∼ ∇ 2 f ( x ) . {\displaystyle M\sim \nabla ^{2}f(x).}

Une direction de quasi-Newton est donc de la forme

d = − M − 1 ∇ f ( x ) . {\displaystyle d={}-M^{-1}\nabla f(x).}

Comme pour la direction de Newton, cette direction est une direction de descente si

  • f ′ ( x ) ≠ 0 , {\displaystyle f'(x)\neq 0,}
  • M {\displaystyle M} est définie positive.

En effet

f ′ ( x ) ⋅ d = ⟨ ∇ f ( x ) , d ⟩ = − ⟨ ∇ f ( x ) , M − 1 ∇ f ( x ) ⟩ ⩽ − λ max − 1 ‖ ∇ f ( x ) ‖ 2 < 0 , {\displaystyle f'(x)\cdot d=\langle \nabla f(x),d\rangle =-\langle \nabla f(x),M^{-1}\nabla f(x)\rangle \leqslant -\lambda _{\max }^{-1}\|\nabla f(x)\|^{2}<0,}

où λ max {\displaystyle \lambda _{\max }} désigne la plus grande valeur propre de M {\displaystyle M} .

Direction de Gauss-Newton

La direction de Gauss-Newton est utilisée pour résoudre les problèmes de moindres carrés dont le critère est de la forme

f ( x ) := 1 2 ‖ F ( x ) ‖ 2 , {\displaystyle f(x):={\frac {1}{2}}\,\|F(x)\|^{2},}

où F : E → F {\displaystyle F:\mathbb {E} \to \mathbb {F} } ( F {\displaystyle \mathbb {F} } est un espace hilbertien dont le produit scalaire est aussi noté ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } et ‖ ⋅ ‖ {\displaystyle \|\cdot \|} est la norme associée). On calcule aisément

f ′ ( x ) ⋅ h = ⟨ F ( x ) , F ′ ( x ) ⋅ h ⟩ = ⟨ F ′ ( x ) ∗ F ( x ) , h ⟩ . f ″ ( x ) ⋅ ( h , k ) = ⟨ F ′ ( x ) ⋅ h , F ′ ( x ) ⋅ k ⟩ + ⟨ F ( x ) , F ″ ( x ) ⋅ ( h , k ) ⟩ = ⟨ ( F ′ ( x ) ∗ F ′ ( x ) ) h , k ⟩ + ⟨ F ( x ) , F ″ ( x ) ⋅ ( h , k ) ⟩ . {\displaystyle {\begin{array}{rcl}f'(x)\cdot h&=&\langle F(x),F'(x)\cdot h\rangle \\&=&\langle F'(x)^{*}F(x),h\rangle .\\[1ex]f''(x)\cdot (h,k)&=&\langle F'(x)\cdot h,F'(x)\cdot k\rangle +\langle F(x),F''(x)\cdot (h,k)\rangle \\&=&\langle \left(F'(x)^{*}F'(x)\right)\,h,k\rangle +\langle F(x),F''(x)\cdot (h,k)\rangle .\end{array}}}

La direction de Gauss-Newton s'obtient en ne gardant du hessien de f {\displaystyle f} que son premier terme dans l'expression ci-dessus, de manière à éviter le calcul des dérivées secondes de F {\displaystyle F} . C'est en réalité une solution arbitraire d {\displaystyle d} de l'équation normale

( F ′ ( x ) ∗ F ′ ( x ) ) d = − F ′ ( x ) ∗ F ( x ) . {\displaystyle \left(F'(x)^{*}F'(x)\right)\,d=-F'(x)^{*}F(x).}

On reconnaît dans le membre de droite l'opposé du gradient de f {\displaystyle f} . Cette équation linéaire a en fait une solution unique si et seulement si F ′ ( x ) {\displaystyle F'(x)} est injective. Les directions de Gauss-Newton sont aussi les solutions du problème de moindres carrés linéaire suivant

min x ∈ E 1 2 ‖ F ( x ) + F ′ ( x ) ⋅ d ‖ 2 . {\displaystyle \min _{x\in \mathbb {E} }\;{\frac {1}{2}}\,\|F(x)+F'(x)\cdot d\|^{2}.}

Une direction de Gauss-Newton d {\displaystyle d} est une direction de descente de f {\displaystyle f} en x {\displaystyle x} si f ′ ( x ) ≠ 0 {\displaystyle f'(x)\neq 0} . En effet

f ′ ( x ) ⋅ d = ⟨ ∇ f ( x ) , d ⟩ = − ⟨ ( F ′ ( x ) ∗ F ′ ( x ) ) d , d ⟩ = − ‖ F ′ ( x ) d ‖ 2 < 0. {\displaystyle f'(x)\cdot d=\langle \nabla f(x),d\rangle =-\langle \left(F'(x)^{*}F'(x)\right)\,d,d\rangle =-\|F'(x)d\|^{2}<0.}

L'inégalité stricte vient du fait que si F ′ ( x ) d = 0 {\displaystyle F'(x)d=0} , alors ∇ f ( x ) = F ′ ( x ) ∗ F ( x ) {\displaystyle \nabla f(x)=F'(x)^{*}F(x)} est nul par l'équation normale, ce que nous avons supposé ne pas avoir lieu.

Annexes

Notes

  1. ↑ M. Al-Baali (1985), Descent property and global convergence of the Fletcher-Reeves methods with inexact line search, IMA Journal of Numerical Analysis, 5, 121-124. doi
  2. ↑ J. Ch. Gilbert, J. Nocedal (1992), Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2, 21–42. doi

Articles connexes

Lien externe

  • J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

Ouvrages généraux

  • (en) D. P. Bertsekas (1995), Nonlinear Programming. Athena Scientific. (ISBN 1-886529-14-0).
  • (en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006), Numerical Optimization - Theoretical and Numerical Aspects [détail des éditions].
  • (en) J. Nocedal, S. J. Wright (2006), Numerical Optimization, Springer. (ISBN 0-387-30303-0).
  • icône décorative Portail de l'analyse