Gradient projeté

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

${\displaystyle (P_{X})\qquad \inf _{x\in X}\;f(x),}$

dans lequel on cherche à minimiser une fonction différentiable ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$ sur une partie convexe ${\displaystyle X}$ d'un espace euclidien ${\displaystyle \mathbb {E} }$, dont le produit scalaire est noté ${\displaystyle \langle \cdot ,\cdot \rangle }$. Soit ${\displaystyle x}$ un point de ${\displaystyle X}$. On note

• ${\displaystyle \nabla f(x)\in \mathbb {E} }$ le gradient de ${\displaystyle f}$ en ${\displaystyle x}$,
• ${\displaystyle T_{x}X}$ le cône tangent à ${\displaystyle X}$ en ${\displaystyle x}$,
• ${\displaystyle P_{C}}$ le projecteur orthogonal sur un convexe fermé non vide ${\displaystyle C}$ de ${\displaystyle \mathbb {E} }$.

Alors le gradient projeté en ${\displaystyle x}$ est le vecteur ${\displaystyle g^{\rm {\scriptscriptstyle P}}(x)\in \mathbb {E} }$ défini par[1]

${\displaystyle g^{\rm {\scriptscriptstyle P}}(x)=P_{-T_{x}X}\nabla f(x)=-P_{T_{x}X}(-\nabla f(x)).}$

D'après la première expression, il s'agit de la projection orthogonale du gradient ${\displaystyle \nabla f(x)}$ sur ${\displaystyle -T_{x}X}$, qui est l'opposé du cône tangent à ${\displaystyle X}$ en ${\displaystyle x}$ (c'est un cône convexe fermé lorsque ${\displaystyle X}$ est convexe comme ici). D'après la seconde expression, on peut aussi dire que l'opposé du gradient projeté, ${\displaystyle -g^{\rm {\scriptscriptstyle P}}(x)}$, est la projection orthogonale de l'opposé du gradient, ${\displaystyle -\nabla f(x)}$, sur le cône tangent ${\displaystyle T_{x}X}$.

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 ${\displaystyle X}$ est le pavé

${\displaystyle [l,u]:=\{x\in \mathbb {R} ^{n}:l\leqslant x\leqslant u\},}$

où les bornes ${\displaystyle l\in {\bar {\mathbb {R} }}^{n}}$et ${\displaystyle u\in {\bar {\mathbb {R} }}^{n}}$ peuvent prendre des valeurs infinies et vérifient ${\displaystyle l<u}$.

Soit ${\displaystyle x\in [l,u]}$. Alors, le cône tangent à ${\displaystyle [l,u]}$ en ${\displaystyle x}$ est donné par

${\displaystyle d\in T_{x}[l,u]\qquad \Longleftrightarrow \qquad \forall \,i\in [\![1,n]\!]:\quad d_{i}~\left\{{\begin{array}{lll}\geqslant 0&{\mbox{si}}&l_{i}=x_{i}\\\leqslant 0&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.}$

Dès lors, si l'on munit ${\displaystyle \mathbb {R} ^{n}}$ du produit scalaire euclidien ${\displaystyle (u,v)\in \mathbb {R} ^{n}\times \mathbb {R} ^{n}\mapsto \sum _{i=1}^{n}\,u_{i}v_{i}}$, on a

${\displaystyle \forall \,i\in [\![1,n]\!]:\quad [g^{\rm {\scriptscriptstyle P}}(x)]_{i}=~\left\{{\begin{array}{lll}\textstyle \min(0,{\frac {\partial f}{\partial x_{i}}}(x))&{\mbox{si}}&l_{i}=x_{i}\\\textstyle {\frac {\partial f}{\partial x_{i}}}(x)&{\mbox{si}}&l_{i}<x_{i}<u_{i}\\\textstyle \max(0,{\frac {\partial f}{\partial x_{i}}}(x))&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.}$

Donc, la condition d'optimalité du premier ordre ${\displaystyle g^{\rm {\scriptscriptstyle P}}(x)=0}$ s'écrit aussi

${\displaystyle \forall \,i\in [\![1,n]\!]:\quad {\frac {\partial f}{\partial x_{i}}}(x)~\left\{{\begin{array}{lll}\geqslant 0&{\mbox{si}}&l_{i}=x_{i}\\=0&{\mbox{si}}&l_{i}<x_{i}<u_{i}\\\leqslant 0&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.}$