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{ℝ}=ℝ\cup \{-\mathrm{\infty },+\mathrm{\infty }\}$, dont l'épigraphe est un polyèdre convexe.

Propriétés

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

• $f$ est une fonction convexe et fermée. En effet, son épigraphe $\mathrm{epi}(f)$ est un convexe fermé de $E\times ℝ$, comme intersection d'une famille (finie et non vide) de demi-espaces fermés.
• Pour tout $\alpha \in ℝ$, 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)⩽\alpha \}$, est le projeté sur $E$ du polyèdre convexe $\mathrm{epi}(f)\cap \{(x,t)\in E\times ℝ\mid t⩽\alpha \}$.

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

La première équivalence ci-dessous est reprise de Modèle:Harvsp, la seconde de Modèle:Harvsp.

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:ℝ\to ℝ,t\mapsto \max (t^2,t)$, puisque $\mathrm{ir}(\mathrm{argmin}f)=\mathrm{ir}(\{0\})=\{0\}$, mais $\mathrm{ir}(\partial f(0))=\mathrm{ir}([0,1])=]0,1[\ni ̸0$ ;
• l'implication « $\Leftarrow$ » n'a pas lieu, par exemple, pour la fonction $f:ℝ\to ℝ,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 $\mathrm{argmin}f=]-\mathrm{\infty },0]$.

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

• Modèle:Article, Rapport INRIA
• Modèle:Ouvrage