Fonction convexe-concave

En mathématiques, une fonction convexe-concave est une fonction définie sur un produit d'espaces vectoriels réels, qui est convexe par rapport à la première variable (quelle que soit la seconde variable) et concave par rapport à la seconde (quelle que soit la première). Une fonction concave-convexe est une fonction dont l'opposée est convexe-concave. On rassemble parfois ces deux types de fonctions sous le vocable de fonction de point-selle, qui est donc une notion moins précise (on ne dit pas si la convexité a lieu par rapport à la première ou la seconde variable) et qui prête à confusion (ces fonctions n'ont pas nécessairement de point-selle).

Les fonctions convexes-concaves apparaissent en optimisation (le lagrangien en est un exemple), dans les problèmes d'équilibre (théorie des jeux), etc.

Connaissances supposées : notions de fonctions convexe et concave, de sous-différentiabilité.

Définitions

Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces vectoriels sur l'ensemble des réels $\mathbb {R}$ . On note ${\bar {\mathbb {R} }}:=\mathbb {R} \cup \{-\infty ,+\infty \}$ la droite réelle achevée.

Fonction convexe-concave — Une fonction $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ est dite convexe-concave, si

pour tout $y\in \mathbb {F}$ , la fonction $x\in \mathbb {E} \to \varphi (x,y)\in {\bar {\mathbb {R} }}$ est convexe,
pour tout $x\in \mathbb {E}$ , la fonction $y\in \mathbb {F} \to \varphi (x,y)\in {\bar {\mathbb {R} }}$ est concave.

Une fonction convexe-concave $\varphi$ est dite propre s'il existe un point $(x_{0},y_{0})\in \mathbb {E} \times \mathbb {F}$ tel que $\varphi (\cdot ,y_{0})$ ne prend pas la valeur $-\infty$ et $\varphi (x_{0},\cdot )$ ne prend pas la valeur $+\infty$ (donc $\varphi (x_{0},y_{0})\in \mathbb {R}$ ) ; le domaine effectif de $\varphi$ est l'ensemble des points $(x_{0},y_{0})$ vérifiant cette propriété ; on le note $\operatorname {dom} \varphi$ .

Fonction convexe-concave fermée

La définition d'une fonction convexe-concave fermée ne doit pas être confondue avec celle d'une fonction convexe fermée. Si la fermeture d'une fonction (convexe) est équivalente à sa semi-continuité inférieure, la fermeture d'une fonction convexe-concave ne l'est pas. Cette dernière notion est aussi plus générale (i.e., moins forte) que la semi-continuité inférieure par rapport à la première variable jointe à la semi-continuité supérieure par rapport à la seconde variable. Elle donne en fait des conditions assez générales assurant la monotonie maximale d'un « opérateur dérivé » associé. On s'y prend de la manière suivante^[1].

Fonction convexe-concave fermée — Soit $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ une fonction convexe-concave.

On note $\operatorname {adh} _{x}\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$

la fonction telle que, pour tout $y\in \mathbb {F}$ , $\operatorname {adh} _{x}\varphi (\cdot ,y)$ est la fermeture de la fonction convexe $\varphi (\cdot ,y)$ . De même, on note $\operatorname {adh} _{y}\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$

la fonction telle que, pour tout $x\in \mathbb {E}$ , $-\operatorname {adh} _{y}\varphi (x,\cdot )$ est la fermeture de la fonction convexe $-\varphi (x,\cdot )$ .
On dit que $\varphi$ est équivalente à la fonction convexe-concave ${\tilde {\varphi }}:\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ si
$\operatorname {adh} _{x}\varphi =\operatorname {adh} _{x}{\tilde {\varphi }}\qquad {\mbox{et}}\qquad \operatorname {adh} _{y}\varphi =\operatorname {adh} _{y}{\tilde {\varphi }}.$

C'est une relation d'équivalence.
On dit que $\varphi$ est fermée, si $\operatorname {adh} _{x}\varphi$ et $\operatorname {adh} _{y}\varphi$ sont équivalentes à $\varphi$ , ce qui revient à dire que
$\operatorname {adh} _{x}(\operatorname {adh} _{y}\varphi )=\operatorname {adh} _{x}\varphi \qquad {\mbox{et}}\qquad \operatorname {adh} _{y}(\operatorname {adh} _{x}\varphi )=\operatorname {adh} _{y}\varphi .$

Monotonie

On sait qu'une fonction réelle d'une variable réelle différentiable et convexe a sa dérivée croissante. Ce fait se généralise aux fonctions convexes propres, définies sur un espace vectoriel, par le fait que leur sous-différentiel est un opérateur monotone (voir ici). Le résultat ci-dessous^[2] montre que l'on a aussi une relation de monotonie pour un opérateur sous-différentiel associé à une fonction convexe-concave.

On note $\partial _{x}\varphi (x,y)$ le sous-différentiel de la fonction convexe $\varphi (\cdot ,y)$ en $x$ , $\partial _{y}(-\varphi )(x,y)$ le sous-différentiel de la fonction convexe $-\varphi (x,\cdot )$ en $y$ et $\operatorname {dom} \,T:=\{(x,y)\in \mathbb {E} \times \mathbb {F} :T(x,y)\neq \varnothing \}$ le domaine de l'opérateur multivoque $T$ .

Monotonie — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces vectoriels topologiques localement convexes séparés et $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ une fonction convexe-concave propre. Alors, l'opérateur multivoque $T:\mathbb {E} \times \mathbb {F} \multimap \mathbb {E} '\times \mathbb {F} '$ défini en $(x,y)\in \mathbb {E} \times \mathbb {F}$ par

$T(x,y)=\partial _{x}\varphi (x,y)\times \partial _{y}(-\varphi )(x,y)$

est monotone. De plus

$\operatorname {dom} \,T\subset \operatorname {dom} \,\varphi .$

L'opérateur $T$ introduit dans le résultat de monotonie ci-dessus est appelé l'opérateur monotone associé à $\varphi$ . On vérifie aisément que

$(x^{*},y^{*})\in T(x,y)\qquad \Longleftrightarrow \qquad \left\{{\begin{array}{l}(x,y)~{\mbox{est un point-selle de}}\\(x',y')\mapsto \varphi (x',y')-\langle x^{*},x'\rangle +\langle y^{*},y'\rangle .\end{array}}\right.$

En particulier

$(0,0)\in T(x,y)\qquad \Longleftrightarrow \qquad (x,y)~{\mbox{est un point-selle de}}~\varphi .$

Monotonie maximale

Dans cette section, on examine la monotonie maximale de l'opérateur monotone $T$ associé à une fonction convexe-concave introduit dans la section précédente. Cette propriété joue un rôle essentiel dans le fait que l'inclusion $0\in T(x)$ puisse avoir une solution $x$ , ainsi que dans la convergence des algorithmes calculant de telle solution ; elle est en quelque sorte le pendant de la semi-continuité inférieure des fonctions en optimisation.

On commence par un résultat pour les fonctions convexes-concaves ne prenant que des valeurs finies^[3].

Monotonie maximale I (fonction à valeurs finies) — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces vectoriels topologiques localement convexes séparés et $\varphi :\mathbb {E} \times \mathbb {F} \to \mathbb {R}$ une fonction convexe-concave prenant des valeurs finies et telle que

pour tout $y\in \mathbb {F}$ , $\varphi (\cdot ,y)$ est continue,
pour tout $x\in \mathbb {E}$ , $\varphi (x,\cdot )$ est continue.

Alors, l'opérateur monotone $T$ associé à $\varphi$ est monotone maximal. De plus, pour tout $(x,y)\in \mathbb {E} \times \mathbb {F}$ , $T(x,y)$ est un convexe non vide faible- $*$ compact de $\mathbb {E} '\times \mathbb {F} '$ .

Sachant qu'une fonction convexe ne prenant que des valeurs finies et définie sur un espace vectoriel de dimension finie est nécessairement continue, on obtient tout de suite le corollaire suivant^[4].

Corollaire (dimension finie) — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces vectoriels de dimension finies et $\varphi :\mathbb {E} \times \mathbb {F} \to \mathbb {R}$ une fonction convexe-concave prenant des valeurs finies. Alors, l'opérateur monotone $T$ associé à $\varphi$ est monotone maximal et, pour tout $(x,y)\in \mathbb {E} \times \mathbb {F}$ , $T(x,y)$ est un convexe non vide compact de $\mathbb {E} '\times \mathbb {F} '$ .

Le résultat de monotonie maximale ci-dessous généralise le précédent en permettant la fonction convexe-concave de prendre des valeurs infinies. Cependant cette fonction doit être fermée et les espaces doivent être des espaces de Banach (l'un étant réflexif)^[5].

Monotonie maximale II (fonction avec des valeurs infinies) — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces de Banach dont l'un au moins est réflexif et $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ une fonction convexe-concave propre fermée. Alors, l'opérateur monotone associé à $\varphi$ est monotone maximal.

Si $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ est une fonction convexe-concave propre fermée, $\varphi (\cdot ,y)$ n'est pas nécessairement semi-continue inférieurement et $\varphi (x,\cdot )$ n'est pas nécessairement semi-continue supérieurement^[1], mais si l'on fait ces hypothèses de semi-continuité quels que soient $x\in \mathbb {E}$ et $y\in \mathbb {F}$ , alors $\varphi$ est fermée et on peut appliquer le théorème.

Corollaire (fonction sci-scs) — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces de Banach dont l'un au moins est réflexif et $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ une fonction convexe-concave propre telle que

pour tout $y\in \mathbb {F}$ , $\varphi (\cdot ,y)$ est semi-continue inférieurement,
pour tout $x\in \mathbb {E}$ , $\varphi (x,\cdot )$ est semi-continue supérieurement.

Alors, $\varphi$ est fermée et l'opérateur monotone associé est monotone maximal.

On peut encore particulariser le résultat donné dans le corollaire précédent au cas où la fonction convexe-concave $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ est obtenue par restriction à un produit de convexes $C\subset \mathbb {E}$ et $D\subset \mathbb {F}$ d'une fonction convexe-concave $\varphi _{0}:\mathbb {E} \times \mathbb {F} \to \mathbb {R}$ ne prenant que des valeurs finies.

Corollaire (restriction d'une fonction à valeurs finies) — Soient $\mathbb {E}$ et $\mathbb {F}$ deux espaces de Banach dont l'un au moins est réflexif et $\varphi :\mathbb {E} \times \mathbb {F} \to {\bar {\mathbb {R} }}$ une fonction convexe-concave propre définie en $(x,y)\in \mathbb {E} \times \mathbb {F}$ par

$\varphi (x,y)=\left\{{\begin{array}{lll}\varphi _{0}(x,y)&{\mbox{si}}&x\in C~{\mbox{et}}~y\in D\\+\infty &{\mbox{si}}&x\notin C~{\mbox{et}}~y\in D\\-\infty &{\mbox{si}}&y\notin D,\end{array}}\right.$

où $C\subset \mathbb {E}$ et $D\subset \mathbb {F}$ sont deux convexes fermés non vides et $\varphi _{0}:\mathbb {E} \times \mathbb {F} \to \mathbb {R}$ est une fonction convexe-concave ne prenant que des valeurs finies et telle que, quels que soient $(x,y)\in \mathbb {E} \times \mathbb {F}$ , $\varphi _{0}(\cdot ,y)$ est semi-continue inférieurement et $\varphi _{0}(x,\cdot )$ est semi-continue supérieurement. Alors, $\varphi$ est une fonction convexe-concave propre et l'opérateur monotone associé est monotone maximal.

Annexes

Notes

↑ ^{a et b} Section 34 chez Rockafellar (1970a).
↑ Théorème 1 chez Rockafellar (1970b).
↑ Théorème 2 chez Rockafellar (1970b).
↑ Corollaire 1 chez Rockafellar (1970b).
↑ Théorème 3 chez Rockafellar (1970b).

Articles connexes

Bibliographie

(en) R.T. Rockafellar (1970a). Convex Analysis. Princeton Mathematics Ser. 28. Princeton University Press, Princeton, New Jersey.
(en) R.T. Rockafellar (1970b). Monotone operator associated with saddle functions and minimax problems. In F.E. Browder, éditeur, Nonlinear Functional Analysis, Part 1, pages 397–407. Symposia in Pure Math., vol. 18, Amer. Math. Soc., Providence, R.I.