Inclusion fonctionnelle

Un problème variationnel est une inclusion fonctionnelle de la forme ${\displaystyle (P_{IF})}$, dans laquelle ${\displaystyle \mathbb {F} =\mathbb {E} }$ et la multifonction ${\displaystyle N:\mathbb {E} \multimap \mathbb {E} }$ est le cône normal ${\displaystyle \operatorname {N} _{X}}$ à un ensemble fermé non vide ${\displaystyle X\subset \mathbb {E} }$ (la notation ${\displaystyle N}$ vient de là). Le problème s'écrit et s'interprète comme ci-dessous :

${\displaystyle (P_{V})\qquad F(x)+\operatorname {N} _{X}(x)\ni 0.}$

Avec la convention ${\displaystyle \operatorname {N} _{X}(x)=\varnothing }$ si ${\displaystyle x\notin X}$, on cherche donc un point ${\displaystyle x\in X}$ tel que ${\displaystyle -F(x)}$ soit dans le cône normal à ${\displaystyle X}$ en ${\displaystyle x}$.

Un problème d'inéquation variationnelle est un problème variationnel ${\displaystyle (P_{V})}$ dans lequel l'ensemble ${\displaystyle X}$ est un convexe fermé non vide ${\displaystyle C}$. Alors le problème variationnel s'exprime par ${\displaystyle -F(x)\in \operatorname {N} _{C}(x)}$ ou encore

${\displaystyle (P_{IV})\qquad \left\{{\begin{array}{l}x\in C\\[-1ex]\langle F(x),y-x\rangle \geqslant 0,\quad \forall \,y\in C.\end{array}}\right.}$

Un problème de complémentarité est un problème d'inéquation variationnelle ${\displaystyle (P_{IV})}$ dans lequel l'ensemble ${\displaystyle C}$ est un cône convexe fermé non vide ${\displaystyle K}$. Alors en prenant ${\displaystyle y=2x}$ et ${\displaystyle y=x/2}$ comme élément-test dans ${\displaystyle (P_{IV})}$, on voit que le problème se récrit comme suit

${\displaystyle (P_{CNL})\qquad K\ni x\perp F(x)\in K^{+},}$

où ${\displaystyle K^{+}}$ est le cône dual de ${\displaystyle K}$. Ce problème requiert que trois conditions soient satisfaites, à savoir ${\displaystyle x\in K}$, ${\displaystyle F(x)\in K^{+}}$ et ${\displaystyle x\perp F(x)}$.

La condition d'optimalité nécessaire du premier ordre de Peano-Kantorovitch est un problème variationnel de la forme ${\displaystyle (P_{V})}$, dans lequel ${\displaystyle F}$ est le gradient d'une fonction ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$.

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

${\displaystyle (P_{G})\quad \left\{{\begin{array}{l}\inf _{x}\,f(x)\\c(x)\in G,\end{array}}\right.}$

dans lequel le critère ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$ est défini sur un espace euclidien ${\displaystyle \mathbb {E} }$, ${\displaystyle c:\mathbb {E} \to \mathbb {F} }$ est une fonction à valeurs dans l'espace euclidien ${\displaystyle \mathbb {F} }$ et ${\displaystyle G}$ est un convexe fermé non vide de ${\displaystyle \mathbb {F} }$.

Son système d'optimalité du premier ordre peut également s'exprimer comme un problème d'inclusion fonctionnelle de la forme ${\displaystyle (P_{IF})}$ avec ${\displaystyle x\curvearrowright (x,\lambda )\in \mathbb {E} \times \mathbb {F} }$,

${\displaystyle F(x,\lambda )={\begin{pmatrix}\nabla f(x)+c'(x)^{*}\lambda \\-\lambda \end{pmatrix}}\quad {\mbox{et}}\quad N(x,\lambda )=\{0\}\times \operatorname {N} _{c(x)}G.}$

Lorsque ${\displaystyle G}$ est un cône convexe fermé, le système d'optimalité du premier ordre de ${\displaystyle (P_{G})}$ peut également s'exprimer comme un problème de complémentarité de la forme ${\displaystyle (P_{CNL})}$ avec ${\displaystyle x\curvearrowright (x,\lambda )\in \mathbb {E} \times \mathbb {F} }$,

${\displaystyle F(x,\lambda )={\begin{pmatrix}\nabla f(x)+c'(x)^{*}\lambda \\-c(x)\end{pmatrix}}\quad {\mbox{et}}\quad K=\mathbb {E} \times G^{-}.}$

Le système d'optimalité du premier ordre de Karush, Kuhn et Tucker du problème ${\displaystyle (P_{EI})}$ peut également s'exprimer comme un problème de complémentarité non linéaire de la forme ${\displaystyle (P_{CNL})}$ avec ${\displaystyle x\curvearrowright (x,\lambda )\in \mathbb {E} \times \mathbb {R} ^{m}}$, ${\displaystyle m=m_{E}+m_{I}}$ :

${\displaystyle F(x,\lambda )={\begin{pmatrix}\nabla f(x)+c'(x)^{*}\lambda \\-c(x)\end{pmatrix}}\quad {\mbox{et}}\quad K=\mathbb {E} \times (\mathbb {R} ^{m_{E}}\times \mathbb {R} _{+}^{m_{I}}).}$

L'appartenance de ${\displaystyle (x,\lambda )}$ à ${\displaystyle K}$ exprime la positivité de ${\displaystyle \lambda _{I}}$. L'appartenance de ${\displaystyle F(x,\lambda )}$ à ${\displaystyle K^{+}=\{0_{\mathbb {E} }\}\times (\{0_{\mathbb {R} ^{m_{E}}}\}\times \mathbb {R} _{+}^{m_{I}})}$ exprime la nullité du gradient du lagrangien et l'admissibilité de ${\displaystyle x}$. Enfin l'orthogonalité entre ${\displaystyle (x,\lambda )}$ et ${\displaystyle F(x,\lambda )}$ exprime la complémentarité.

Lorsque ${\displaystyle N}$ est la multifonction constante ${\displaystyle x\mapsto \{0_{\mathbb {R} ^{m_{E}}}\}\times \mathbb {R} _{+}^{m_{I}}\subset \mathbb {R} ^{m}\equiv \mathbb {F} }$ où ${\displaystyle E}$ et ${\displaystyle I}$ forment une partition de ${\displaystyle [1\,{:}\,m]}$, ${\displaystyle (P_{IF})}$ revient à trouver un point ${\displaystyle x\in \mathbb {E} }$ satisfaisant les égalités ${\displaystyle F_{i}(x)=0}$ pour ${\displaystyle i\in E}$ et les inégalités ${\displaystyle F_{i}(x)\leqslant 0}$ pour ${\displaystyle i\in I}$.

Cette notion est motivée par le souhait d'avoir des itérés de l'algorithme de Josephy-Newton qui convergent localement rapidement vers une solution ayant cette propriété.

Pour introduire la notion de semi-stabilité, supposons dans un premier temps que ${\displaystyle N\equiv \{0\}}$, si bien que le problème consiste à résoudre ${\displaystyle F(x)=0}$ par des itérations de Newton ${\displaystyle x_{k+1}=x_{k}-F'(x_{k})^{-1}F(x_{k})}$. On suppose que l'on est dans un voisinage ${\displaystyle V}$ d'un zéro ${\displaystyle x_{*}}$ de ${\displaystyle F}$ et que la suite générée par l'algorithme converge vers ce point. Supposons que ${\displaystyle F}$ soit continûment différentiable sur ${\displaystyle V}$. Alors, en utilisant l'équation définissant l'itération et le développement de ${\displaystyle F(x_{k+1})}$ avec reste intégral, on obtient

${\displaystyle {\begin{array}{rcl}F(x_{k+1})&=&F(x_{k+1})-F(x_{k})-F'(x_{k})(x_{k+1}-x_{k})\\&=&\int _{0}^{1}\left[F'{\bigl (}x_{k}+t(x_{k+1}-x_{k}){\bigr )}-F'(x_{k})\right](x_{k+1}-x_{k})\,{\rm {d}}t\\&=&o(\|x_{k+1}-x_{k}\|).\end{array}}}$

La convergence superlinéaire de ${\displaystyle \{x_{k}\}}$ vers ${\displaystyle x_{*}}$, c'est-à-dire ${\displaystyle x_{k+1}-x_{*}=o(\|x_{k}-x_{*}\|)}$, se déduit alors de l'inversibilité de ${\displaystyle F'(x_{*})}$. En effet, par la différentiabilité de ${\displaystyle F}$ en ${\displaystyle x_{*}}$ et la nullité de ${\displaystyle F(x_{*})}$, il vient ${\displaystyle F(x_{k+1})=F'(x_{*})(x_{k+1}-x_{*})+o(\|x_{k+1}-x_{*}\|)}$ et donc

${\displaystyle \|F(x_{k+1})\|\geqslant C\|x_{k+1}-x_{*}\|,}$

où ${\displaystyle C}$ est une constante strictement positive (on peut prendre ${\displaystyle C}$ dans ${\displaystyle ]0,1/\|F(x_{*})^{-1}\|[}$). Puis l'estimation de ${\displaystyle F(x_{k+1})}$ ci-dessus conduit à ${\displaystyle x_{k+1}-x_{*}=o(\|x_{k+1}-x_{k}\|)}$ et donc à ${\displaystyle x_{k+1}-x_{*}=o(\|x_{k}-x_{*}\|)}$ qui exprime la convergence superlinéaire de la suite. C'est cette dernière conséquence de l'inversibilité de ${\displaystyle F'(x_{*})}$ que l'on choisit de préserver dans la définition de la semi-stabilité ci-dessous : si ${\displaystyle F(x)=p}$ et ${\displaystyle x}$ est proche de ${\displaystyle x_{*}}$, alors ${\displaystyle x-x_{*}=O(\|p\|)}$.

Semi-stabilité — On dit qu'une solution ${\displaystyle x_{*}}$ de ${\displaystyle (P_{IF})}$ est semi-stable s'il existe des constantes ${\displaystyle \sigma _{1}>0}$ et ${\displaystyle \sigma _{2}>0}$ telles que pour tout couple ${\displaystyle (x,p)\in \mathbb {E} \times \mathbb {F} }$ vérifiant

${\displaystyle F(x)+N(x)\ni p\quad {\mbox{et}}\quad \|x-x_{*}\|\leq \sigma _{1},}$

on a

${\displaystyle \|x-x_{*}\|\leq \sigma _{2}\|p\|.}$

Voici quelques observations sur cette définition.

1. Cette propriété n'affirme rien sur l'existence d'une solution de ${\displaystyle F(x)+N(x)\ni p}$ pour les ${\displaystyle p}$ considérés.
2. Cette propriété n'est contraignante que pour de petites perturbations ${\displaystyle p}$ puisque dès que ${\displaystyle \|p\|\geqslant \sigma _{1}/\sigma _{2}}$, la condition est toujours vérifiée.
3. Une solution semi-stable est nécessairement isolée puisque si ${\displaystyle x_{*}'\in B(x_{*},\sigma _{1})}$ est une autre solution, on a ${\displaystyle F(x_{*}')+N(x_{*}')\ni 0}$ et donc ${\displaystyle \|x_{*}'-x_{*}\|\leqslant \sigma _{2}\|0\|}$ ou encore ${\displaystyle x_{*}'=x_{*}}$. Il n'y a donc pas d'autre solution que ${\displaystyle x_{*}}$ dans la boule ${\displaystyle B(x_{*},\sigma _{1})}$.
4. La notion de semi-stabilité en ${\displaystyle x_{*}}$ se ramène à celle d'injectivité de ${\displaystyle F'(x_{*})}$ en l'absence de ${\displaystyle N}$ (et donc de son inversibilité si ${\displaystyle \operatorname {dim} \mathbb {E} =\operatorname {dim} \mathbb {F} }$).
5. On peut montrer qu'une solution fortement régulière est semi-stable[3].

Si une solution semi-stable de ${\displaystyle (P_{IF})}$ en est une solution isolée, c'est aussi une solution isolée de cette inclusion fonctionnelle linéarisée en ${\displaystyle x_{*}}$. La réciproque est d'ailleurs vraie lorsque ${\displaystyle N}$ est l'application cône normal à un polyèdre convexe (voir ci-dessous).

Solution isolée de l'inclusion fonctionnelle linéarisée — Soit ${\displaystyle x_{*}}$ une solution semi-stable de l'inclusion fonctionnelle ${\displaystyle (P_{IF})}$, dans laquelle ${\displaystyle F}$ est différentiable en ${\displaystyle x_{*}}$. Alors ${\displaystyle x_{*}}$ est une solution isolée de l'inclusion foncitonnelle linéarisée

${\displaystyle F(x_{*})+F'(x_{*})(x-x_{*})+N(x)\ni 0.}$

Le résultat suivant donne diverses propriétés d'une solution d'un problème d'inclusion fonctionnelle qui deviennent équivalentes à la semi-stabilité lorsque la multifonction ${\displaystyle N}$ est le cône normal ${\displaystyle \operatorname {N} _{C}}$ à un convexe polyédrique non vide ${\displaystyle C}$, c'est-à-dire lorsque l'inclusion fonctionnelle est un problème d'inéquation variationnelle sur un polyèdre convexe non vide. La condition (2) peut être utilisée pour caractériser la semi-stabilité d'un point stationnaire d'un problème d'optimisation sous contraintes et la condition (3) pour caractériser la semi-stabilité d'un minimum local de ce même problème.

La semi-stabilité n'assure en rien l'existence d'une solution de l'équation linéarisée et donc d'un nouvel itéré de l'algorithme de Josephy-Newton, même si cet itéré est proche d'une solution. C'est la raison d'être de la propriété d'hémi-stabilité introduite dans cette section.

Hémi-stabilité — On dit qu'une solution ${\displaystyle x_{*}}$ de ${\displaystyle (P_{IF})}$ est hémi-stable si pour tout ${\displaystyle \alpha >0}$, il existe ${\displaystyle \beta >0}$ tel que, pour tout ${\displaystyle x_{0}\in B(x_{*},\beta )}$, l'inclusion en ${\displaystyle x}$ suivante

${\displaystyle F(x_{0})+F'(x_{0})(x-x_{0})+N(x)\ni 0}$

a une solution dans ${\displaystyle B(x_{*},\alpha )}$.

On notera que l'hémitabilité ne dit rien sur l'unicité de la solution de l'inclusion linéarisée. Seule l'existence d'une solution de cette inclusion linéarisée, proche de la solution hémi-stable, est demandée.

• Algorithme de Josephy-Newton
• Inéquation variationnelle
• Optimisation quadratique successive

• (en) J.Ch. Gilbert (2015). Advanced Continuous Optimization, planches du cours du M2 Optimization à l'université Paris-Saclay.

• (en) J.F. Bonnans (1994). Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Applied Mathematics and Optimization, 29, 161–186.
• (en) A.L. Dontchev, R.T. Rockafellar (2009). Implicit Functions and Solution Mappings - A View from Variational Analysis. Springer Monographs in Mathematics. Springer.
• (en) A.F. Izmailov, M.V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer.
• (en) S.M. Robinson (1980). Strongly regular generalized equations. Mathematics of Operations Research, 5, 43–62.