Algorithme à directions de descente
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.
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 euclidien (par exemple, , l'espace des -uplets de nombres réels, muni d'un produit scalaire) ou, plus généralement, sur un espace hilbertien. L'algorithme est itératif et procède donc par améliorations successives. Au point courant, un déplacement est effectué le long d'une direction de descente, de manière à faire décroître la fonction. Le déplacement le long de cette direction est déterminé par la technique numérique connue sous le nom de recherche linéaire.
Cette approche algorithmique peut être vue comme une technique de globalisation, c'est-à-dire une méthode permettant d'obtenir la convergence des itérés (sous certaines conditions) quel que soit l'itéré initial choisi. Elle s'apparente ainsi aux algorithmes à régions de confiance ; ces dernières améliorent légèrement (mais parfois de manière décisive) leurs résultats de convergence mais sont plus compliquées à mettre en œuvre, ce qui limite parfois leur application.
Les algorithmes à directions de descente s'étendent aux problèmes avec contraintes simples (pourvu que la projection sur l'ensemble admissible soit aisée, peu coûteuse en temps de calcul) ou pour des problèmes avec contraintes fonctionnelles non linéaires, par l'intermédiaire de fonctions de mérite. Elles sont aussi utilisées en optimisation non lisse.
Principes de l'algorithme
Cadre
Le cadre est le suivant. On cherche un point qui minimise une fonction différentiable :
définie sur un espace hilbertien , dont on note le produit scalaire et la norme associée. On note et la dérivée et le gradient de en si bien que
Énoncé
Les algorithmes à directions de descente cherchent un minimum de en générant une suite de points appelés itérés, qui approchent de mieux en mieux un minimiseur du critère , si tout va bien. Cette suite est construite en se fondant sur deux constructions :
- calcul d'une direction de descente
- détermination d'un pas , 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
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.
Algorithme à directions de descente (schéma) — On se donne un point/itéré initial et un seuil de tolérance . Un algorithme à directions de descente définit une suite d'itérés , , , jusqu'à ce qu'un test d'arrêt soit satisfait. Il passe de à par les étapes suivantes.
- Simulation : calcul de au moins.
- Test d'arrêt : si , arrêt.
- Direction : calcul d'une direction de descente .
- Recherche linéaire : déterminer un pas le long de .
- Nouvel itéré :
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.
À propos du test d'arrêt
En pratique, il faudra prendre 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 ( est généralement pris petit). C'est en effet ce que suggère la condition nécessaire d'optimalité du premier ordre . Comme n'est jamais exactement égal à , ce test ne pourra fonctionner que si est faible en norme pour voisin de , ce qui revient pratiquement à supposer que est de classe .
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 . 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 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, revient à , ce qui peut arriver si le pas 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 ? Le cas où est quadratique strictement convexe est instructif :
Minimiser revient alors à déterminer l'unique solution du système linéaire . Par ailleurs, le gradient de (pour le produit scalaire euclidien) est le résidu du système linéaire : . Or on sait bien que, si le conditionnement de est élevé, on peut très bien avoir petit et une erreur importante. Le test d'arrêt portant sur la petitesse du gradient doit donc être interprété avec précaution.
Choix d'une direction de descente
Les algorithmes à directions de descente portent en général le nom de leur direction de descente. Ainsi
- l'algorithme du gradient est celui qui utilise la direction du gradient,
- les algorithmes du gradient conjugué est ceux qui utilisent les directions du gradient conjugué,
- l'algorithme de Newton est celui qui utilise la direction de Newton,
- les algorithmes de quasi-Newton sont ceux qui utilisent des directions de quasi-Newton,
- l'algorithme de Gauss-Newton est utilisé pour résoudre les problèmes de moindres-carrés et utilise la direction de Gauss-Newton.
Ces directions sont décrites dans l'article «Direction de descente».
Règles de recherche linéaire
Plusieurs règles permettant de déterminer la valeur du paramètre existent. Elles consistent, pour la plupart, à trouver la valeur qui minimise la fonction-coût
Considérant que est une direction de descente, on obtient , ce qui permet de déterminer le comportement de q en fonction des valeurs de α. Il convient toutefois d'être prudent :
- en choisissant α trop grand, on ne parviendra pas à faire décroître les valeurs de q ou au pire d'obtenir un algorithme oscillant ;
- en choisissant α trop petit, l'algorithme aura une convergence lente.
Règles exactes
Peu de cas permettent d'établir exactement la valeur optimale du paramètre. Le cas quadratique est de ceux-ci : pour une fonction quadratique
le paramètre optimal à l'étape k est[1]
Règle d'Armijo
La règle d'Armijo se base sur le choix d'un paramètre et détermine une valeur approchée de par la condition :
Le risque de cette méthode est de favoriser les valeurs trop petites, aussi, elle est rarement utilisée seule.
Règle de Goldstein
Goldstein propose en 1967 une méthode basée sur le choix cette fois-ci de deux paramètres et détermine les valeurs approchées de par deux conditions :
Règle de Wolfe
Wolfe propose en 1969 une méthode basée sur le choix de deux paramètres et détermine les valeurs approchées de par deux conditions :
Deux valeurs usuelles des paramètres sont et .
Convergence
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
Dans le cas d'un algorithme de descente, la convergence est assurée pour une fonction convexe, différentiable et de gradient K-lipschitzien.
Annexes
Articles connexes
Lien externe
- J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.
Références
- ↑ (en) P.E. Frandsen, K. Jonasson, H.B. Nielsen et O. Tingleff, Unconstrained optimization, (lire en ligne)
Ouvrages généraux
- (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).
Portail des mathématiques