Fonction convexe polyédrique

En analyse convexe, une fonction convexe polyédrique est une application, définie sur un espace vectoriel réel de dimension finie $E$ et à valeurs dans la droite réelle achevée ${\overline {\mathbb {R} }}=\mathbb {R} \cup \{-\infty ,+\infty \}$ , dont l'épigraphe est un polyèdre convexe.

Propriétés[modifier | modifier le code]

Soit $f:E\to {\overline {\mathbb {R} }}$ une fonction convexe polyédrique.

$f$ est une fonction convexe et fermée. En effet, son épigraphe $\operatorname {epi} (f)$ est un convexe fermé de $E\times \mathbb {R}$ , comme intersection d'une famille (finie et non vide) de demi-espaces fermés.
Pour tout $\alpha \in \mathbb {R}$ , l'ensemble de sous-niveau $\alpha$ de $f$ est un polyèdre convexe. En effet, cet ensemble, égal par définition à $\{x\in E\mid f(x)\leqslant \alpha \}$ , est le projeté sur $E$ du polyèdre convexe $\operatorname {epi} (f)\cap \{(x,t)\in E\times \mathbb {R} \mid t\leqslant \alpha \}$ .

Dans la suite, on supposera de plus que $f$ est propre, c'est-à-dire qu'elle n'est pas identiquement égale à $+\infty$ ( $\operatorname {epi} (f)\neq \varnothing$ ) et qu'elle ne prend pas la valeur $-\infty$ ( $\operatorname {epi} (f)$ ne contient pas de droite verticale).

La première équivalence ci-dessous est reprise de Gilbert 2016, la seconde de Polyak 1983.

Ensemble des minimiseurs — Soient

E

un espace vectoriel euclidien et

f:E\to {\overline {\mathbb {R} }}

une fonction polyédrique propre. Alors, pour tout

x\in E

:

{\begin{array}{rcl}x\in \operatorname {ir} {\bigl (}\operatorname {argmin} f{\bigr )}&\quad \Longleftrightarrow \quad &0\in \operatorname {ir} {\bigl (}\partial f(x){\bigr )},\\\operatorname {argmin} f=\{x\}&\quad \Longleftrightarrow \quad &0\in \operatorname {int} {\bigl (}\partial f(x){\bigr )},\end{array}}

où $\operatorname {ir} {(C)}$ désigne l'intérieur relatif d'un convexe non vide $C$ , $\operatorname {int} (C)$ son intérieur, et $\partial f(x)$ le sous-différentiel de $f$ en $x$ .

Dans la première équivalence, aucune des deux implications n'a lieu si $f$ est seulement supposée convexe, fermée et propre :

l'implication « $\Rightarrow$ » n'a pas lieu, par exemple, pour la fonction $f:\mathbb {R} \to \mathbb {R} ,\;t\mapsto \max(t^{2},t)$ , puisque $\operatorname {ir} {(\operatorname {argmin} f)}=\operatorname {ir} {(\{0\})}=\{0\}$ , mais $\operatorname {ir} {(\partial f(0))}=\operatorname {ir} {(\left[0,1\right])}=\left]0,1\right[\not \ni 0$ ;
l'implication « $\Leftarrow$ » n'a pas lieu, par exemple, pour la fonction $f:\mathbb {R} \to \mathbb {R} ,\;t\mapsto \max(0,t)^{2}$ , puisque $0$ est dans l'intérieur relatif de $\partial f(x)=\{0\}$ quel que soit le minimiseur $x$ , mais le minimiseur $x=0$ n'est pas dans l'intérieur relatif de $\operatorname {argmin} f=\left]-\infty ,0\right]$ .

Dans la seconde équivalence, l'implication « $\Leftarrow$ » ne requiert pas la polyédricité de la fonction.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

(en) J. Ch. Gilbert, « On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery », Journal of Optimization Theory and Applications, vol. 1, n^o 1,‎ 2016, p. 1-32 (DOI 10.1007/s10957-016-1004-0), Rapport INRIA
(en) B. T. Polyak, Introduction to Optimization, New York, Optimization Software, 1983

Portail de l'analyse