Direction de descente

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Soient un espace vectoriel et une fonction réelle définie sur admettant des dérivées directionnelles au point considéré. On note

la dérivée directionnelle (au sens de Dini) de en dans la direction . La notation signifie que le réel tend vers zéro dans 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 en est un vecteur tel que

On en déduit que

si bien que décroît en dans la direction . 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[modifier | modifier le code]

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 est un espace hilbertien, dont le produit scalaire est noté et la norme associée et que est au moins une fois différentiable au point considéré. On note sa dérivée, qui est une application linéaire continue de dans , et la valeur en de cette dérivée. Par le théorème de Riesz-Fréchet, il existe alors un vecteur , appelé le gradient de en , défini par

Direction du gradient[modifier | modifier le code]

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

Il s'agit bien d'une direction de descente si puisqu'alors

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é[modifier | modifier le code]

L'algorithme du gradient conjugué construit sa direction de descente en en ajoutant à l'opposé du gradient, la direction calculée à l'itéré précédent multipliée par un scalaire  :

À 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

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

  1. qui a lieu si est un point stationnaire (dérivée nulle) de la fonction ce qui revient à faire de la recherche linéaire exacte.

Cette seconde condition est aisément satisfaite lorsque 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 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[modifier | modifier le code]

On suppose ici que la fonction à minimiser est deux fois différentiable en et on désigne par son hessien en , lequel est l'unique opérateur linéaire auto-adjoint vérifiant

La direction de Newton est définie en un point en lequel le hessien de est inversible par

Cette direction est une direction de descente si

  • est définie positive.

En effet

désigne la plus grande valeur propre de .

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[modifier | modifier le code]

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 auto-adjoint :

Une direction de quasi-Newton est donc de la forme

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

  • est définie positive.

En effet

désigne la plus grande valeur propre de .

Direction de Gauss-Newton[modifier | modifier le code]

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

( est un espace hilbertien dont le produit scalaire est aussi noté et est la norme associée). On calcule aisément

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

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

Une direction de Gauss-Newton est une direction de descente de en si . En effet

L'inégalité stricte vient du fait que si , alors est nul par l'équation normale, ce que nous avons supposé ne pas avoir lieu.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  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[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Ouvrages généraux[modifier | modifier le code]