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
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]
![{\displaystyle g^{\rm {\scriptscriptstyle P}}(x)=P_{-T_{x}X}\nabla f(x)=-P_{T_{x}X}(-\nabla f(x)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eea5ef888c42aa48e23f53f3c9057e41d0d01120)
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
Expression de l'optimalité
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é :
![{\displaystyle \nabla f({\bar {x}})\in (T_{\bar {x}}X)^{+}\qquad \Longleftrightarrow \qquad g^{\rm {\scriptscriptstyle P}}({\bar {x}})=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48639c461fdf1eb63fcfcd142e8851c63c7eebdc)
Descente
S'il est non nul, l'opposé du gradient projeté est une direction de descente de
en
, car on a
![{\displaystyle \langle \nabla f(x),-g^{\rm {\scriptscriptstyle P}}(x)\rangle \leqslant -\|g^{\rm {\scriptscriptstyle P}}(x)\|^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b124726e99fcee65e9aba1e62baec4bdc8e53156)
Projection du chemin de plus forte pente
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.
Exemple
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
Note
- ↑ 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
Lien externe
- J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.
Bibliographie
- (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
Portail des mathématiques