Fonction convexe polyédrique
# 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.

$E$

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

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

