6.3 Optimisation de géométrie
165
1. une direction de descente d k ∈ IR
n , c’est-à-dire une direction dans laquelle
f décroît au moins localement ; une telle direction est caractérisée par
(d k , g k ) ≤ 0 où l’on a noté g k = ∇f (x k ) le gradient de f en x k ,
2. une longueur de descente t k ∈ IR
+ ,
et en posant
x k+1 = x k + t k d k .
Les constructions de d k et t k résultent du choix d’un modèle local pour f .
Typiquement, on considère que lorsqu’on est au point x k , minimiser f revient
à minimiser son développement de Taylor en x k à l’ordre 1 (méthode de gradient) ou à l’ordre 2 (méthode de Newton).
Dans les méthodes exposées ci-dessous, on détermine d’abord la direction de
descente d k , puis la longueur de descente t k en minimisant (de façon approximative) sur IR
+ la fonction
q(t) = f (x k + t d k ).
Cette deuxième étape porte le nom de recherche linéaire. Notons cependant qu’il existe d’autres méthodes (par exemple celles dites des régions de
confiance) pour lesquelles détermination de la direction et de la longueur de
descente sont effectuées conjointement.
Les sections 6.3.1.2 à 6.3.1.5 présentent quatre méthodes plus ou moins performantes de recherche d’une direction de descente : la méthode de plus grande
pente, la méthode du gradient conjugué non linéaire, la méthode de Newton, et la (famille) de méthode(s) de quasi-Newton. La section 6.3.1.6 aborde
succinctement le problème de la recherche linéaire.
Remarque 6.6 On obtient donc ainsi une suite (x k ) k∈I N dont on peut espérer qu’elle converge vers un minimum. Comme on ne dispose pas d’un temps
infini pour effectuer la minimisation, il faut arrêter l’algorithme dès qu’on
estime être suffisamment proche d’un minimum. Le critère d’arrêt généralement retenu porte sur la norme du gradient de la fonction à minimiser : on
choisit > 0 suffisamment petit et on arrête l’algorithme dès que
|g k | ≤
Cette condition ne garantit évidemment pas en toute généralité qu’on soit
arrivé au voisinage d’un minimum local, mais elle fonctionne plutôt bien en
pratique.
6.3.1.2 Méthode de plus forte pente
La première idée qu’on peut avoir pour déterminer une direction de descente
est d’utiliser le modèle au premier ordre
165
1. une direction de descente d k ∈ IR
n , c’est-à-dire une direction dans laquelle
f décroît au moins localement ; une telle direction est caractérisée par
(d k , g k ) ≤ 0 où l’on a noté g k = ∇f (x k ) le gradient de f en x k ,
2. une longueur de descente t k ∈ IR
+ ,
et en posant
x k+1 = x k + t k d k .
Les constructions de d k et t k résultent du choix d’un modèle local pour f .
Typiquement, on considère que lorsqu’on est au point x k , minimiser f revient
à minimiser son développement de Taylor en x k à l’ordre 1 (méthode de gradient) ou à l’ordre 2 (méthode de Newton).
Dans les méthodes exposées ci-dessous, on détermine d’abord la direction de
descente d k , puis la longueur de descente t k en minimisant (de façon approximative) sur IR
+ la fonction
q(t) = f (x k + t d k ).
Cette deuxième étape porte le nom de recherche linéaire. Notons cependant qu’il existe d’autres méthodes (par exemple celles dites des régions de
confiance) pour lesquelles détermination de la direction et de la longueur de
descente sont effectuées conjointement.
Les sections 6.3.1.2 à 6.3.1.5 présentent quatre méthodes plus ou moins performantes de recherche d’une direction de descente : la méthode de plus grande
pente, la méthode du gradient conjugué non linéaire, la méthode de Newton, et la (famille) de méthode(s) de quasi-Newton. La section 6.3.1.6 aborde
succinctement le problème de la recherche linéaire.
Remarque 6.6 On obtient donc ainsi une suite (x k ) k∈I N dont on peut espérer qu’elle converge vers un minimum. Comme on ne dispose pas d’un temps
infini pour effectuer la minimisation, il faut arrêter l’algorithme dès qu’on
estime être suffisamment proche d’un minimum. Le critère d’arrêt généralement retenu porte sur la norme du gradient de la fonction à minimiser : on
choisit > 0 suffisamment petit et on arrête l’algorithme dès que
|g k | ≤
Cette condition ne garantit évidemment pas en toute généralité qu’on soit
arrivé au voisinage d’un minimum local, mais elle fonctionne plutôt bien en
pratique.
6.3.1.2 Méthode de plus forte pente
La première idée qu’on peut avoir pour déterminer une direction de descente
est d’utiliser le modèle au premier ordre