Algorithme du gradient

Lalgorithme du gradient, aussi appelé algorithme de descente de gradient, désigne un algorithme d'optimisation différentiable. Il est par conséquent 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é dans la direction opposée au gradient, 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 description montre que l'algorithme fait partie de la famille des algorithmes à directions de descente. Les algorithmes d'optimisation sont généralement écrits pour minimiser une fonction. Si l'on désire maximiser une fonction, il suffira de minimiser son opposée. Il est important de garder à l'esprit le fait que le gradient, et donc la direction de déplacement, dépend du produit scalaire qui équipe l'espace hilbertien ; l'efficacité de l'algorithme dépend donc de ce produit scalaire. L'algorithme du gradient est également connu sous le nom dalgorithme de la plus forte pente ou de la plus profonde descente (steepest descent, en anglais) parce que le gradient est la pente de la fonction linéarisée au point courant et est donc, localement, sa plus forte pente (notion qui dépend du produit scalaire). Dans sa version la plus simple, l'algorithme ne permet de trouver ou d'approcher qu'un point stationnaire (i.e., un point en lequel le gradient de la fonction à minimiser est nul) d'un problème d'optimisation sans contrainte. De tels points sont des minima globaux, si la fonction est convexe. Des extensions sont connues pour les problèmes avec contraintes simples, par exemple des contraintes de borne.