Direction de descente

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.

Sommaire

Définition

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

f'(x;d):=\lim_{t\downarrow0}\frac{f(x+td)-f(x)}{t}\in\mathbb{R}

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

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

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

f'(x;d) < 0.

On en déduit que

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

si bien que f décroît en x dans la direction 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 \mathbb{E} est un espace hilbertien, dont le produit scalaire est noté \langle\cdot,\cdot\rangle et la norme associée \|\cdot\|, et que f:\mathbb{E}\to\mathbb{R} est au moins une fois différentiable au point x considéré. On note f'(x) sa dérivée, qui est une application linéaire continue de \mathbb{E} dans \mathbb{R}, et f'(x)\cdot d=f'(x;d) la valeur en d\in\mathbb{E} de cette dérivée. Par le théorème de Riesz-Fréchet, il existe alors un vecteur \nabla f(x)\in\mathbb{E}, appelé le gradient de f en x, défini par

\forall\,d\in\mathbb{E}:\qquad f'(x)\cdot d=\langle\nabla f(x),d\rangle.

Direction du gradient

La direction du gradient d est, en réalité, l'opposé du gradient :

d = -\nabla f(x).

Il s'agit bien d'une direction de descente si f'(x)\ne0 puisqu'alors

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 en ajoutant à l'opposé du gradient, la direction d_-\in\mathbb{E} calculée à l'itéré précédent x − , multipliée par un scalaire \beta\in\mathbb{R} :

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.

Vérifions qu'il s'agit bien d'une direction de descente. On a

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)\ne0,
  2. \langle\nabla f(x),d_-\rangle=0, qui a lieu si x = x − + α − d − où α − est un point stationnaire (dérivée nulle) de la fonction t\mapsto f(x_-+td_-), ce qui revient à faire de la recherche linéaire exacte.

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

Pour une fonction 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 β permettent d'assurer la descente des directions et la convergence des algorithmes associés.

Direction de Newton

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

\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 en lequel le hessien de f est inversible par

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

Cette direction est une direction de descente si

En effet

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  désigne la plus grande valeur propre de \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 auto-adjoint :

M \sim \nabla^2f(x).

Une direction de quasi-Newton est donc de la forme

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

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

En effet

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  désigne la plus grande valeur propre de 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):=\frac{1}{2}\,\|F(x)\|^2,

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

\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 \bigl(F'(x)^*F'(x)\bigr)\,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 que son premier terme dans l'expression ci-dessus, de manière à éviter le calcul des dérivées secondes de F. C'est en réalité une solution arbitraire d de l'équation normale

\bigl(F'(x)^*F'(x)\bigr)\,d = -F'(x)^*F(x).

On reconnaît dans le membre de droite l'opposé du gradient de f. Cette équation linéaire a en fait une solution unique si et seulement si 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\in\mathbb{E}}\;\frac{1}{2}\,\|F(x)+F'(x)\cdot d\|^2.

Une direction de Gauss-Newton d est une direction de descente de f en x si f'(x)\ne0. En effet

f'(x)\cdot d=\langle\nabla f(x),d\rangle=-\langle\bigl(F'(x)^*F'(x)\bigr)\,d,d\rangle=-\|F'(x)d\|^2<0.

L'inégalité stricte vient du fait que si F'(x)d = 0, alors \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

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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Direction de descente de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Direction De Descente — La direction de descente est une forme de généralisation de la descente de gradient. En optimisation, une direction de descente est un vecteur tel que, permet de rapprocher d un minimum local de la fonction . Supposons que nous calculons par une… …   Wikipédia en Français

  • Descente De Gradient — Traduction à relire Gradient descent → …   Wikipédia en Français

  • Descente de gradient — Traduction à relire Gradient descent → …   Wikipédia en Français

  • Algorithme de descente — Descente de gradient Traduction à relire Gradient descent → …   Wikipédia en Français

  • Descente de Laffrey — Rampe de Laffrey Début de la rampe de Laffrey à la sortie du village éponyme La rampe de Laffrey, appelée aussi descente de Laffrey ou côte de Laffrey est un tronçon de la RN 85 dite route Napoléon, route alpine qui relie Gap à Grenoble. Elle se… …   Wikipédia en Français

  • Descente de la Courtille — Pour les articles homonymes, voir Courtille (homonymie). Scène de la Descente de la Courtille en 1843 …   Wikipédia en Français

  • Descente (cyclisme) — Le VTT de descente (aussi désigné par l expression anglophone downhill mountain biking ou simplement downhill(DH)) est une discipline sportive dans laquelle le but est de descendre, à l aide d un VTT, des pistes spécialement conçues à travers la… …   Wikipédia en Français

  • Direction du Racing Club de Strasbourg — La direction du club est assurée en 1930 par un comité central. Joseph Heintz (assis, deuxième de la droite), devient le premier président de la section professionnelle en 1933. La direction du Racing Club de Strasbourg est l entité qui est… …   Wikipédia en Français

  • Algorithme à directions de descente — Un algorithme à directions de descente est un algorithme d optimisation différentiable (l optimisation dont il est question ici est une branche des mathématiques), destiné à minimiser une fonction réelle différentiable définie sur un espace… …   Wikipédia en Français

  • La Descente Infernale — est un film américain réalisé par Michael Ritchie, sorti en 1969. Sommaire 1 Synopsis 2 Fiche Technique 3 Distribution 4 Voir aussi …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”