Algorithme à directions de descente

Le cadre est le suivant. On cherche un point ${\displaystyle x_{*}}$ qui minimise une fonction différentiable :

définie sur un espace hilbertien ${\displaystyle \mathbb {E} }$, dont on note ${\displaystyle \langle \cdot ,\cdot \rangle }$ le produit scalaire et ${\displaystyle \|\cdot \|}$ la norme associée. On note ${\displaystyle f'(x)}$ et ${\displaystyle \nabla f(x)}$ la dérivée et le gradient de ${\displaystyle f}$ en ${\displaystyle x,}$ si bien que

Les algorithmes à directions de descente cherchent un minimum de ${\displaystyle f}$ en générant une suite de points ${\displaystyle \{x_{k}\}_{k\geqslant 1},}$ appelés itérés, qui approchent de mieux en mieux un minimiseur ${\displaystyle x_{*}}$ du critère ${\displaystyle f}$, si tout va bien. Cette suite est construite en se fondant sur deux constructions :

• calcul d'une direction de descente ${\displaystyle d_{k}\in \mathbb {E} ,}$
• détermination d'un pas ${\displaystyle \alpha _{k}}$, qui est un nombre réel strictement positif, le long de la direction de descente de telle sorte que le nouvel itéré donne au critère une valeur inférieure à celle qu'il a en l'itéré courant ; le nouvel itéré est de la forme suivante
  ${\displaystyle x_{k+1}:=x_{k}+\alpha _{k}d_{k};}$
  
  cette opération de détermination du pas s'appelle la recherche linéaire.

Ces deux opérations seront décrites ci-dessous, mais on peut dès à présent résumer l'algorithme. Il s'agit d'un schéma algorithmique, car beaucoup d'aspects de celui-ci ne sont pas spécifiés avec précision.

Cet algorithme est extrêmement simple ; ça ne l'empêche pas d'avoir des propriétés de convergence intéressantes, bien au contraire. Cette simplicité permet d'étendre l'algorithme à des contextes variés, aux problèmes d'optimisation avec contraintes en particulier.

En pratique, il faudra prendre ${\displaystyle \varepsilon >0}$ dans le test d'arrêt de l'étape 2 ; la valeur nulle de cette tolérance a été admise uniquement pour simplifier l'expression des résultats de convergence ci-dessous.

Dans les problèmes sans contrainte, il est normal que le test d'arrêt porte sur la petitesse du gradient (${\displaystyle \varepsilon }$ est généralement pris petit). C'est en effet ce que suggère la condition nécessaire d'optimalité du premier ordre ${\displaystyle \nabla f(x_{*})=0}$. Comme ${\displaystyle x_{k}}$ n'est jamais exactement égal à ${\displaystyle x_{*}}$, ce test ne pourra fonctionner que si ${\displaystyle \nabla f(x)}$ est faible en norme pour ${\displaystyle x}$ voisin de ${\displaystyle x_{*}}$, ce qui revient pratiquement à supposer que ${\displaystyle f}$ est de classe ${\displaystyle C^{1}}$.

Par ailleurs, un tel test d'arrêt suggère qu'un algorithme à directions de descente ne peut pas trouver mieux qu'un point stationnaire de ${\displaystyle f}$. C'est en effet souvent le cas, mais ce point faible est rarement rédhibitoire en pratique. On peut noter qu'il existe une version élaborée des méthodes à régions de confiance qui permet de trouver un minimum local, évitant ainsi les points stationnaires qui n'ont pas cette propriété de minimalité locale.

On est parfois tenté d'arrêter l'algorithme si le critère ${\displaystyle f}$ ne décroît presque plus. Ceci n'est pas sans risque et il vaut mieux ne pas utiliser un tel test d'arrêt, car une faible variation du critère peut se produire loin d'une solution. En effet, au premier ordre, ${\displaystyle f(x_{k+1})\simeq f(x_{k})}$ revient à ${\displaystyle \alpha _{k}\langle \nabla f(x_{k}),d_{k}\rangle \simeq 0}$, ce qui peut arriver si le pas ${\displaystyle \alpha _{k}}$ est petit (c'est en général très suspect) ou si la direction de descente fait avec l'opposé du gradient un angle proche de 90 degrés, une situation qui se rencontre fréquemment (si l'algorithme est bien conçu, cela traduit un mauvais conditionnement du problème).

Même si le test d'arrêt de l'étape 2 est suggéré par la théorie, on peut s'interroger sur sa pertinence, du point de vue suivant : peut-on préciser dans quelle mesure le fait d'avoir un petit gradient implique que l'itéré est proche d'un point stationnaire de ${\displaystyle f}$ ? Le cas où ${\displaystyle f}$ est quadratique strictement convexe est instructif :

${\displaystyle f(x)={\frac {1}{2}}x^{\top }Ax-b^{\top }x,\qquad {\mbox{avec}}~~A\succ 0.}$

Minimiser ${\displaystyle f}$ revient alors à déterminer l'unique solution ${\displaystyle x_{*}}$ du système linéaire ${\displaystyle Ax=b}$. Par ailleurs, le gradient de ${\displaystyle f}$ (pour le produit scalaire euclidien) est le résidu du système linéaire : ${\displaystyle \nabla f(x)=Ax-b}$. Or on sait bien que, si le conditionnement de ${\displaystyle A}$ est élevé, on peut très bien avoir ${\displaystyle \|Ax-b\|_{2}}$ petit et une erreur ${\displaystyle \|x-x_{*}\|_{2}}$ importante. Le test d'arrêt portant sur la petitesse du gradient doit donc être interprété avec précaution.

Peu de cas permettent d'établir exactement la valeur optimale du paramètre. Le cas quadratique est de ceux-ci : pour une fonction quadratique

${\displaystyle f(x)={\frac {1}{2}}x^{\top }Ax+b^{\top }x+c}$

le paramètre optimal à l'étape k est[1]

${\displaystyle \alpha _{k}={\frac {-b^{\top }d_{k}}{d_{k}^{\top }Ad_{k}}}.}$

La règle d'Armijo se base sur le choix d'un paramètre ${\displaystyle 0<m<1}$ et détermine une valeur approchée de ${\displaystyle \alpha _{k}}$ par la condition :

${\displaystyle q(\alpha )\leqslant q(0)+m\alpha q'(0).}$

Le risque de cette méthode est de favoriser les valeurs trop petites, aussi, elle est rarement utilisée seule.

Goldstein propose en 1967 une méthode basée sur le choix cette fois-ci de deux paramètres ${\displaystyle 0<m_{1}<m_{2}<1}$ et détermine les valeurs approchées de ${\displaystyle \alpha _{k}}$ par deux conditions :

${\displaystyle {\begin{cases}q(\alpha )&\leqslant q(0)+m_{1}\alpha q'(0),\\q(\alpha )&\geqslant q(0)+m_{2}\alpha q'(0).\end{cases}}}$

Wolfe propose en 1969 une méthode basée sur le choix de deux paramètres ${\displaystyle 0<m_{1}<m_{2}<1}$ et détermine les valeurs approchées de ${\displaystyle \alpha _{k}}$ par deux conditions :

${\displaystyle {\begin{cases}q(\alpha )&\leqslant q(0)+m_{1}\alpha q'(0),\\q'(\alpha )&\geqslant m_{2}q'(0).\end{cases}}}$

Deux valeurs usuelles des paramètres sont ${\displaystyle m_{1}=0,1}$ et ${\displaystyle m_{2}=0,7}$.

• Algorithme du gradient
• Algorithme du gradient conjugué
• Direction de descente

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

• (en) D. P. Bertsekas (1995), Nonlinear Programming. Athena Scientific. (ISBN 978-1-886529-14-4).
• (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 978-0-387-30303-1).