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

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

Articles connexes

• Minimum saillant
• Poursuite de base
• Recouvrement par jauge

Bibliographie

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