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 euclidien (par exemple, , l'espace des n-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

Le cadre est le suivant. On cherche à minimiser une fonction différentiable

définie sur un espace hilbertien , dont on note le produit scalaire et la norme associée. On note f'(x) et la dérivée et le gradient de f en x, si bien que

Les algorithmes à directions de descente cherchent un minimum de f en générant une suite de points appelés itérés, qui approchent de mieux en mieux un minimiseur du critère f, 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 α_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 x_{k + 1}: = x_k + α_kd_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.

En pratique, il faudra prendre ε > 0 ; la valeur nulle de cette tolérance a été admise uniquement pour simplifier l'expression des résultats de convergence ci-dessous. 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.

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

Règles exactes

Règle d'Armijo

Règle de Goldstein

Règle de Wolfe

Convergence

Annexes

Articles connexes

• Algorithme du gradient
• Algorithme du gradient conjugué
• Direction de descente
• Recherche linéaire

Lien externe

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

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