Fonction convexe polyédrique

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

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

Dans la suite, on supposera de plus que ${\displaystyle f}$ est propre, c'est-à-dire qu'elle n'est pas identiquement égale à ${\displaystyle +\infty }$ (${\displaystyle \operatorname {epi} (f)\neq \varnothing }$) et qu'elle ne prend pas la valeur ${\displaystyle -\infty }$ (${\displaystyle \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 ${\displaystyle E}$ un espace vectoriel euclidien et ${\displaystyle f:E\to {\overline {\mathbb {R} }}}$ une fonction polyédrique propre. Alors, pour tout ${\displaystyle x\in E}$ :${\displaystyle {\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ù ${\displaystyle \operatorname {ir} {(C)}}$ désigne l'intérieur relatif d'un convexe non vide ${\displaystyle C}$, ${\displaystyle \operatorname {int} (C)}$ son intérieur, et ${\displaystyle \partial f(x)}$ le sous-différentiel de ${\displaystyle f}$ en ${\displaystyle x}$.

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

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

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