Gradient projeté

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En optimisation mathématique, le gradient projeté est un vecteur dont la nullité exprime l'optimalité au premier ordre d'un problème d'optimisation avec contraintes convexes. Il est aussi utilisé dans la description et l'analyse de l'algorithme du gradient projeté.

De manière plus précise, le gradient projeté est la projection orthogonale du gradient en un point de la fonction que l'on cherche à minimiser, projection sur l'opposé du cône tangent au point à l'ensemble admissible du problème, supposé convexe.

Définition[modifier | modifier le code]

Considérons le problème d'optimisation générique

dans lequel on cherche à minimiser une fonction différentiable sur une partie convexe d'un espace euclidien , dont le produit scalaire est noté . Soit un point de . On note

  • le gradient de en ,
  • le cône tangent à en ,
  • le projecteur orthogonal sur un convexe fermé non vide de .

Alors le gradient projeté en est le vecteur défini par[1]

D'après la première expression, il s'agit de la projection orthogonale du gradient sur , qui est l'opposé du cône tangent à en (c'est un cône convexe fermé lorsque est convexe comme ici). D'après la seconde expression, on peut aussi dire que l'opposé du gradient projeté, , est la projection orthogonale de l'opposé du gradient, , sur le cône tangent .

Propriétés[modifier | modifier le code]

Expression de l'optimalité[modifier | modifier le code]

Le gradient projeté peut être utilisé pour exprimer l'optimalité du problème au premier ordre. On sait en effet que, si est solution du problème et si est différentiable en , alors est dans le cône dual du cône tangent à en , ce qui veut dire que , pour toute direction tangente . Cela s'écrit de manière compacte comme suit

On montre facilement que cette condition d'optimalité du premier ordre géométrique est équivalente à la nullité du gradient projeté :

Descente[modifier | modifier le code]

S'il est non nul, l'opposé du gradient projeté est une direction de descente de en , car on a

Projection du chemin de plus forte pente[modifier | modifier le code]

Dans l'algorithme du gradient projeté, on examine depuis un itéré , l'allure de la fonction à minimiser le long du chemin obtenu en projetant sur le chemin , où . Cette projection se confond avec le chemin , où , tant que reste dans . C'est ce qu'affirme le résultat suivant.

Projection du chemin de plus forte pente — Quel que soit , on a

De plus, lorsque est polyédrique, ces propriétés ont lieu pour tout petit.

Exemple[modifier | modifier le code]

Le concept de gradient projeté s'utilise surtout lorsque la projection sur l'opposé du cône tangent est une opération aisée. C'est le cas si est le pavé

où les bornes et peuvent prendre des valeurs infinies et vérifient .

Soit . Alors, le cône tangent à en est donné par

Dès lors, si l'on munit du produit scalaire euclidien , on a

Donc, la condition d'optimalité du premier ordre s'écrit aussi

Annexe[modifier | modifier le code]

Note[modifier | modifier le code]

  1. Par exemple, Moré et Toraldo (1991) utilisent cette notion, alors que Calamai et Moré (1987) définissent le gradient projeté comme l'opposé de .

Article connexe[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) P.H. Calamai, J.J. Moré (1987). Projected gradient methods for linearly constrained problems. Mathematical Programming, 39, 93-116. doi
  • (en) J.J. Moré, G. Toraldo (1991). On the solution of large quadratic programming problems with bound constraints. SIAM Journal on Optimization, 1, 93–113. doi