Inclusion fonctionnelle

Une inclusion fonctionnelle est un problème de la forme

$(P_{IF})\qquad F(x)+N(x)\ni 0,$

où $F:\mathbb {E} \to \mathbb {F}$ est une fonction entre les deux espaces vectoriels $\mathbb {E}$ et $\mathbb {F}$ et $N:\mathbb {E} \multimap \mathbb {F}$ est une multifonction entre les mêmes espaces. Ce type de problème est aussi appelé équation généralisée. Il signifie que l'on cherche un point $x\in \mathbb {E}$ tel que l'ensemble $F(x)+N(x)$ contienne l'élément nul de $\mathbb {F}$ ou encore tel que l'ensemble $N(x)$ contienne $-F(x)$. Si $N\equiv \{0\}$, on cherche à résoudre une «simple» équation $F(x)=0$. On pourrait bien sûr enlever la fonction $F$ du modèle, car $x\mapsto F(x)+N(x)$ est une multifonction qui peut être prise en compte par $N$, mais certains problèmes d'inclusion ont une partie fonctionnelle comme ici, que certains résultats (comme le théorème des fonctions implicites, ci-dessous) ou certains algorithmes de résolution (comme l'algorithme de Josephy-Newton) exploitent, en utilisant la possibilité de dériver $F$.

Ce modèle de problème $(P_{IF})$ est suffisamment général pour englober les problèmes variationnels, les problèmes d'inéquation variationnelle, les problèmes de complémentarité et les conditions d'optimalité du premier ordre des problèmes d'optimisation.

Lorsque $F$ est différentiable et que certaines propriétés de régularité ont lieu, ce problème peut être résolu numériquement par diverses techniques, notamment l'algorithme de Josephy-Newton.

Exemples d'inclusions fonctionnelles

Problème variationnel

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

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

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

Problème d'inéquation variationnelle

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

$(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.$

Problème de complémentarité

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

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

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

Conditions d'optimalité du premier ordre en optimisation

Contrainte abstraite

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

Contrainte d'inclusion fonctionnelle

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

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

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

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

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

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

Contraintes d'égalité et d'inégalité

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

$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 $(x,\lambda )$ à $K$ exprime la positivité de $\lambda _{I}$. L'appartenance de $F(x,\lambda )$ à $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 $x$. Enfin l'orthogonalité entre $(x,\lambda )$ et $F(x,\lambda )$ exprime la complémentarité.

Système d'égalités et d'inégalités

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

Théorème des fonctions implicites

Un théorème des fonctions implicites peut être obtenu pour une inclusion fonctionnelle sous l'hypothèse de régularité suivante.

Solution fortement régulière — On dit que $x_{*}$ est une solution fortement régulière de $(P_{IF})$ de module $L\geqslant 0$ s'il existe des voisinages $U$ de $x_{*}$ dans $\mathbb {E}$ et $V$ de 0 dans $\mathbb {F}$, tels que pour tout $p\in V$, l'inclusion fonctionnelle linéarisée perturbée

$F(x_{*})+F'(x_{*})(x-x_{*})+N(x)\ni p$

a une solution $x(p)$, unique dans $U$, et si $x(\cdot )$ est $L$-lipschitzienne sur $V$.

Nécessairement $x(0)=x_{*}$. Par ailleurs, si $N=\{0\}$, la régularité forte devient l'inversibilité de $F'(x_{*})$.

On se place dans le cadre suivant. Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces de dimension finie et $P$ un espace topologique. Pour un paramètre $p\in P$ donné, on considère l'inclusion fonctionnelle perturbée

$F(x,p)+N(x)\ni 0,$

où $F:\mathbb {E} \times P\to \mathbb {F}$ et $N:\mathbb {E} \multimap \mathbb {F}$ est une multifonction.

Théorème des fonctions simplicites — Soient $(x_{0},p_{0})\in \mathbb {E} \times P$ et $\Omega$ un voisinage de $x_{0}$ dans $\mathbb {E}$. Supposons que $F'_{x}$ existe sur $\Omega \times P$ et que $F$ et $F'_{x}$ soient continues en $(x_{0},p_{0})$. Si $x_{0}$ est une solution de $F(x,p_{0})+N(x)\ni 0$, qui est fortement régulière de module $L$, alors pour tout $\varepsilon >0$, il existe un voisinage $U$ de $x_{0}\in \mathbb {E}$ et un voisinage $W$ de $p_{0}\in P$, ainsi qu'une fonction univoque $x:W\to U$ telle que pour tout $p\in W$, $x(p)$ est l'unique solution de $F(x,p)+N(x)\ni 0$. De plus, pour tout $p$ et $p'\in W$,

$\|x(p')-x(p)\|\leq (L+\varepsilon )\|F(p',x(p))-F(p,x(p))\|.$

Dans le cas où $F(x,\cdot )$ est lipschitzienne, uniformément en $x$, on a le corollaire plus explicite suivant.

Corollaire — On suppose que les conditions du résultat précédent ont lieu, que $P$ est une partie d'un espace normé et qu'il existe une constante $\mu$ telle que pour tout $p$ et $p'\in P$ et tout $x\in U$, on a

$\|F(x,p')-F(x,p')\|\leq \mu \|p'-p\|.$

Alors $x(\cdot )$ est lipschitzienne sur $W$ de module $\mu (L+\varepsilon )$.

Semi-stabilité et hémi-stabilité

Le bon comportement local d'un algorithme de linéarisation requiert une hypothèse de différentiabilité de la fonction dont on cherche un zéro (ne fût-ce que parce que la fonction est linéarisée par l'algorithme) et une hypothèse d'inversibilité de la dérivée de cette fonction en ce zéro (pour que localement on puisse définir la direction de déplacement d'un itéré à l'autre). Pour l'inclusion fonctionnelle $(P_{IF})$, l'hypothèse de différentiabilité est naturellement celle de $F$ lorsque l'algorithme considéré est celui de Josephy-Newton puisque seule $F$ est différentiée dans cet algorithme. L'hypothèse d'inversibilité est, quant à elle, plus difficile à définir : on l'exprime au moyen de deux concepts, la semi-stabilité et l'hémi-stabilité. La semi-stabilité s'occupe de la vitesse de convergence de l'algorithme de Josephy-Newton et l'hémi-stabilité du caractère bien posé de celui-ci.

Semi-stabilité

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

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

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

où $C$ est une constante strictement positive (on peut prendre $C$ dans $]0,1/\|F(x_{*})^{-1}\|[$). Puis l'estimation de $F(x_{k+1})$ ci-dessus conduit à $x_{k+1}-x_{*}=o(\|x_{k+1}-x_{k}\|)$ et donc à $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 $F'(x_{*})$ que l'on choisit de préserver dans la définition de la semi-stabilité ci-dessous : si $F(x)=p$ et $x$ est proche de $x_{*}$, alors $x-x_{*}=O(\|p\|)$.

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

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

on a

$\|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 $F(x)+N(x)\ni p$ pour les $p$ considérés.
2. Cette propriété n'est contraignante que pour de petites perturbations $p$ puisque dès que $\|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 $x_{*}'\in B(x_{*},\sigma _{1})$ est une autre solution, on a $F(x_{*}')+N(x_{*}')\ni 0$ et donc $\|x_{*}'-x_{*}\|\leqslant \sigma _{2}\|0\|$ ou encore $x_{*}'=x_{*}$. Il n'y a donc pas d'autre solution que $x_{*}$ dans la boule $B(x_{*},\sigma _{1})$.
4. La notion de semi-stabilité en $x_{*}$ se ramène à celle d'injectivité de $F'(x_{*})$ en l'absence de $N$ (et donc de son inversibilité si $\operatorname {dim} \mathbb {E} =\operatorname {dim} \mathbb {F}$).
5. On peut montrer qu'une solution fortement régulière est semi-stable.

Si une solution semi-stable de $(P_{IF})$ en est une solution isolée, c'est aussi une solution isolée de cette inclusion fonctionnelle linéarisée en $x_{*}$. La réciproque est d'ailleurs vraie lorsque $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 $x_{*}$ une solution semi-stable de l'inclusion fonctionnelle $(P_{IF})$, dans laquelle $F$ est différentiable en $x_{*}$. Alors $x_{*}$ est une solution isolée de l'inclusion foncitonnelle linéarisée

$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 $N$ est le cône normal $\operatorname {N} _{C}$ à un convexe polyédrique non vide $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.

Caractérisations de la semi-stabilité pour une IV polyédrique — On suppose que $\mathbb {E} =\mathbb {F}$ et que $x_{*}\in \mathbb {E}$ est une solution de l'inclusion fonctionnelle $(P_{IF})$, dans laquelle $F$ est différentiable en $x_{*}$ et $N$ est l'application cône normal $\operatorname {N} _{C}$ à un convexe fermé non vide $C$ de $\mathbb {E} .$ Alors les implications (1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (4) ont lieu pour les affirmations données ci-dessous :

1. $x_{*}$ est semi-stable,
2. $x_{*}$ est solution isolée de
   $F(x_{*})+F'(x_{*})(x-x_{*})+\operatorname {N} _{C}(x)\ni 0,$
   
3. tout $x\in C\setminus \{x_{*}\}$ solution de
   ${\begin{array}{c}\langle F(x_{*}),x-x_{*}\rangle =0\\[-0.3ex]F(x_{*})+F'(x_{*})(x-x_{*})+\operatorname {N} _{C}(x_{*})\ni 0,\end{array}}$
   est tel que $\langle F'(x_{*})(x-x_{*}),x-x_{*}\rangle >0$,
4. le système en $x$
   ${\begin{array}{c}\operatorname {N} _{C}(x)\subset \operatorname {N} _{C}(x_{*})\\[-0.3ex]\langle F(x_{*}),x-x_{*}\rangle =0\\[-0.3ex]\mathbb {R} _{+}\,F(x_{*})+F'(x_{*})(x-x_{*})+\operatorname {N} _{C}(x)\ni 0,\end{array}}$
   n'a pas d'autre solution que $x_{*}$.

Si, de plus, $C$ est polyédrique, alors les quatre propriétés (1)-(4) sont équivalentes.

Hémi-stabilité

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 $x_{*}$ de $(P_{IF})$ est hémi-stable si pour tout $\alpha >0$, il existe $\beta >0$ tel que, pour tout $x_{0}\in B(x_{*},\beta )$, l'inclusion en $x$ suivante

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

a une solution dans $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.

Annexes

Articles connexes

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

Lien externe

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

Bibliographie

• (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.