Convexe

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En géométrie, un objet est convexe si pour toute paire de points { A , B } de cet objet, le segment [AB] qui les joint est entièrement contenu dans l'objet. Par exemple, un cube plein, un disque ou une boule sont convexes, mais un objet creux ou bosselé ne l'est pas.

Cette notion concrète a été généralisée dans le cadre des espaces vectoriels et a débouché en analyse sur la notion de fonction convexe.

Le terme convexe est également utilisé :

en optique. Voir à ce sujet l’article sur les lentilles.
en finance. Voir à ce sujet l’article sur le gamma et la convexité.

Sommaire

1 Ensemble convexe
2 Jauge d'un ensemble convexe
3 Projection sur un convexe fermé d'un espace de Hilbert

[modifier] Ensemble convexe

On désigne ici par E un espace vectoriel réel ou complexe. On définit la notion de convexité pour des sous-ensembles de E.

Quels que soient x et y éléments de E, on appelle segment d'extrémités x, y le sous-ensemble de E ainsi défini :

$[x, y] = \{z \in E\, /\, \exists\, t \in [0,\, 1], z = t\, x + (1 - t)\, y\}$

Un sous-ensemble C de E est dit convexe si, pour tous x et y dans C, $[x,\, y] \subset C$ ; la partie vide est convexe.

[modifier] Propriétés élémentaires

Soit C un sous-ensemble convexe de E.

Si $x_1,\, \dots,\, x_p$ sont des points de $\ C$ et $t_1,\, \dots,\, t_p$ des réels positifs ou nuls tels que $t_1 + \cdots + t_p = 1$ , alors la combinaison linéaire (dite convexe) $t_1\, x_1 + \cdots + t_p\, x_p$ est un point de C.

L'intersection d'une famille quelconque de sous-ensembles convexes de E est un sous-ensemble convexe de E.

Combinaison convexe

Soit une partie finie $\quad\ A =\{v_1,v_2,\dots,v_p\}$ de E. Un vecteur w de E est une combinaison convexe de $\quad A$ s'il existe p réels positifs ou nuls $\quad \lambda_1,\lambda_2,\dots,\lambda_p$ de somme égale à 1 tels que $w = \sum_{k=1}^p \lambda_k\, v_k$
Soit une partie $\quad C$ quelconque de E. On appelle combinaison convexe de $\quad C$ toute combinaison convexe d'un sous-ensemble fini A de $\quad C$ .

Si C est un ensemble convexe, toute combinaison convexe de C appartient à C (immédiat par récurrence).

[modifier] Enveloppe convexe

Étant donnée une partie quelconque A de E, il existe au moins un sous-ensemble convexe de E contenant A, à savoir E lui-même ; alors on peut définir l'enveloppe convexe $Conv(A)$ de A : c'est l'intersection de tous les sous-ensembles convexes de E contenant A.

C'est donc le plus petit sous-ensemble convexe de E contenant A, caractérisé par les deux propriétés suivantes :

$\ \mathrm{Conv}(A)$ est convexe et $A \subset \mathrm{Conv}(A)$ ;
si C est un sous-ensemble convexe de E contenant A, alors $\quad \mathrm{Conv}(A) \subset C$ .

Si x, y sont deux points de E, l'enveloppe convexe de la paire {x, y} est le segment [x, y].

Théorème

L'enveloppe convexe d'un ensemble A est l'ensemble des combinaisons convexes de A.

Démonstration
Soit B l'ensemble des combinaisons convexes de A. Toute combinaison convexe de A appartient à $\quad \mathrm{Conv}(A)$ (cf. ci-dessus). Donc $\quad B\subset \mathrm{Conv}(A)$ .
D'autre part l'ensemble de toutes les combinaisons convexes de A est un convexe (facile) contenant A et donc $\quad\mathrm{Conv}(A)$ . Ainsi $\mathrm{Conv}(A)\subset B$ .
Donc $\quad B=\mathrm{Conv}(A)$ .

Théorème

L'enveloppe convexe d'un ensemble A équilibré est équilibrée

Démonstration
Soient $\quad \{ v_1,v_2,...,v_p\}$ une partie finie de A et $\quad\lambda$ un scalaire vérifiant $|\lambda|\le 1$ .
Tout $w \in \mathrm{Conv}(A)$ s'écrit $w=\sum_{k=1}^N \alpha_k v_k$ avec $\alpha_k\ge 0$ et $\sum_{k=1}^N \alpha_k = 1$ .
Alors $\quad \lambda w =\sum_{k=1}^N \alpha_k \lambda v_k$ . Mais pour tout $\quad k\quad \lambda v_k \in A$ puisque A est équilibré. Il en résulte immédiatement que $\quad \lambda w \in \mathrm{Conv}(A)$ .

[modifier] Exemples

Les sous-ensembles convexes de l'ensemble $\R$ des nombres réels sont les intervalles de $\ \R$ .
Étant donnés n intervalles $\ I_1,\, \dots, \, I_n$ de $\ \R$ , leur produit cartésien $\ I_1 \times \cdots \times I_n$ est un sous-ensemble convexe de $\ \R^n$ .
Dans un espace vectoriel (réel ou complexe), tout sous-espace vectoriel est convexe ; il en est de même de tout sous-espace affine.
Dans un espace vectoriel normé (réel ou complexe), toute boule est convexe, qu'elle soit ouverte ou fermée.

[modifier] Jauge d'un ensemble convexe

Soit $K \subset E$ un ensemble convexe contenant l'origine. On appelle jauge de K (relativement à l'origine) la fonction $\quad p_K$ de E dans $\mathbb R_+ \quad \bigcup \quad \{+ \infty \}$ définie par

$p_K(v)= \inf\, \{\lambda ,\lambda>0 \quad et \quad \lambda^{-1}v \in K \}$

et $p_K(v)=+\infty$ si l'ensemble ci-dessus est vide.

Théorème

La jauge $\quad p_K$ d'un convexe K contenant l'origine vérifie les propositions suivantes:

(i)Si $\quad \lambda \ge 0$ alors $\quad p_K(\lambda v)=\lambda p_K(v)$

(ii) $p_K(u+v) \le p_K(u)+p_K(v)$

Démonstration

(i): Ce résultat est immédiat.
(ii):Soient 2 vecteurs $\quad u$ et $\quad v$ quelconques. Le résultat est évident si $p_K(u)=+\infty$ ou $p_K(v)=+\infty$

Sinon:
$\quad \alpha \ge p_K(u)$ équivaut à $\quad \alpha^{-1} u \in K$
$\quad \beta \ge p_K(v)$ équivaut à $\quad \beta^{-1} v \in K$
. En utilisant la convexité, la conjonction de ces 2 propositions entraîne:
$(\alpha+\beta)^{-1} (u+v) = \frac{\alpha}{\alpha+\beta}\alpha^{-1}u + \frac{\beta}{\alpha+\beta}\beta^{-1}v\quad\in K$ , ce qui équivaut à $\alpha+\beta\ge p_K(u+v)$ .
Donc $\quad p_K(u+v)\le \inf_{\alpha \ge p_K(u)}\alpha+\inf_{\beta \ge p_K(v)}\beta =p_K(u)+p_K(v)$

Théorème

Si l'espace E est réel, la jauge d'un convexe symétrique K (par rapport à 0) et absorbant est une semi-norme sur E.

Si l'espace E est complexe, la jauge d'un convexe K équilibré et absorbant est une semi-norme sur E.

Démonstration
Tout d'abord K étant absorbant il en résulte immédiatement que $\forall v \in E \quad p_K(v)<+\infty$ .
De plus, en utilisant le théorème précédent il suffit de vérifier que $\forall \lambda \in \mathbb K\quad p_K(\lambda v)=|\lambda| p_K(v)$

Si l'espace E est réel, la symétrie de $\mathbb K$ montre immédiatement que pour $\lambda <0\quad p_K(\lambda v)=-\lambda p_K(v)=|\lambda|p_K(v).$
Si l'espace E est complexe.

Ecrivons $\quad\lambda=|\lambda|e^{i\theta}$ . K étant équilibré, pour tout $\quad \mu>0\quad \mu^{-1}|\lambda|e^{i\theta}v \in K$ équivaut à $\mu^{-1}|\lambda|v \in K$ puisque $\quad |e^{i\theta}|=|e^{-i\theta}|=1$ . Il en résulte l'égalité des bornes inférieures, c'est à dire $\quad p_K(\lambda v)=p_K(|\lambda|v)=|\lambda|p_K(v)$ .

[modifier] Projection sur un convexe fermé d'un espace de Hilbert

Théorème

Soient $\mathbb H$ un espace de Hilbert sur $\mathbb R$ ou $\mathbb C$ et M un ensemble convexe fermé (non vide) de $\mathbb H$ . Si $\quad v$ désigne un vecteur quelconque de $\mathbb H$ , le problème $\min_{w \in M}\|v-w\|$ admet une solution unique $\quad w^*$ . On note alors $\exists!\,w^*\in M \quad \|v-w^*\|=\min_{w \in M}\|v-w\|$ .

Cette solution est caractérisée par l'inéquation variationnelle:

$\forall w \in M \quad Re(w-w^*|v-w^*) \le 0$

De plus la projection : $p_M: \quad v \longrightarrow w^*$ est 1-lipschitzienne et par conséquent uniformément continue.

Démonstration

Montrons tout d'abord l'équivalence de la définition initiale avec l'inéquation variationnelle.

w *

est une solution du problème, supposons que l'inéquation variationnelle soit fausse: il existe donc $w_1 \in M \,$ tel que $Re(w_1-w^*|v-w^*)>0 \,$ . M étant convexe, pour tout $\lambda \in [0,1]$ le vecteur $\lambda w_1+(1- \lambda)w^*\,$ appartient à M. Mais alors $\|v-(\lambda w_1+(1- \lambda)w^*)\|^2=\|v-w^*\|^2+\lambda^2 \|w_1-w^*\|^2-2 \lambda Re(v-w^*|w_1-w^*)$

Le coefficient de $λ$ est strictement négatif en vertu de notre hypothèse. Pour $λ$ suffisamment petit non nul, le terme en $λ 2$ est strictement dominé par le terme en $λ$ et par conséquent la somme algébrique des deux derniers termes est strictement négative. Par suite dans ce cas $\|v-(\lambda w_1+(1- \lambda)w^*)\|^2<\|v-w^*\|^2$ , ce qui est contradictoire.

Réciproquement supposons que l'inéquation variationnelle soit vraie. Alors pour tout $w \in M \quad \|v-w\|^2=\|v-w^*\|^2 + \|w-w^*\|^2-2Re(v-w^*|w-w^*) \ge \|v-w^*\|^2$ , ce qui est le résultat annoncé.

L'ensemble de réels $\{\|v-w\|\, / w \in M\}$ admet une borne inférieure d (il est minoré par 0). Il existe donc au moins une suite minimisante $(w_n) \quad$ d'éléments de M telle que $\lim_{n \to \infty} \|v-w_n\|=d$ . Nous allons montrer que c'est une suite de Cauchy.

Soient donc $w n$ et $w m$ deux éléments de la suite. Il résulte du théorème de la médiane que, si I désigne le milieu de $\quad [w_n,w_m]$ on a $\|w_n-w_m\|^2=2(\|w_n-v\|^2 \|w_m-v\|^2)-4\|v-I\|^2$ . Comme $I \in M$ (convexité) $\|v-I\|^2 \ge d^2$ . D'autre part puisque $\|v-v_n\|$ et $\|v-v_m\|$ tendent vers d, quel que soit $ε > 0$ on peut trouver N tel que (n > N et m > N) entraîne $2(\|v-w_n\|^2+\|v-w_m\|^2)<4d^2+\epsilon^2$ . Et donc $\|w_n-w_m\|^2<\epsilon^2$ , soit $\|w_n-w_m\|<\epsilon$ . Ceci montre qu'on a bien une suite de Cauchy. Maintenant comme M est fermé et donc complet, la suite $(w n)$ converge vers un élément $w *$ de M. Ceci montre l'existence d'une solution du problème puisque par la définition précédente $\quad w^*$ vérifie $\|v-w^*\|=\lim_{n \to \infty} \|v-w_n\| = d$ .

Prouvons que $w *$ est bien solution unique du problème initial. Si en effet, $w * *$ était une solution différente, on aurait $\|v-w^{**}\|^2=\|v-w^*\|^2+\|w^*-w^{**}\|^2-2Re(v-w^*|w^{**}-w^*)>d^2$ puisque le second terme est strictement positif et le dernier positif (à cause de l'inéquation variationnelle vérifiée par $w * *$ ) . Ceci contredirait le fait que $w * *$ soit solution.
Soient maintenant deux vecteurs $\quad v_1$ et $\quad v_2$ et soient $w^*_1$ et $w^*_2$ leurs projections respectives. Comme on peut écrire

$v_1-v_2=w^*_1-w^*_2+ (v_1-w^*_1)-(v_2-w^*_2)$ on a immédiatement

$\|v_1-v_2\|^2=\|w^*_1-w^*_2\|^2+\|(v_1-w^*_1)-(v_2-w^*_2)\|^2+2Re(w^*_1-w^*_2|(v_1-w^*_1)-(v_2-w^*_2))$

Mais les deux derniers termes du second membre sont positifs (pour le dernier, cela provient des inéquations variationnelles impliquant : $Re(w^*_2-w^*_1|v_1-w^*_1)\le 0$ et $Re(w^*_1-w^*_2|v_2-w^*_2)\le 0$ ).
Par suite $\|v_1-v_2\|^2 \ge \|w^*_1-w^*_2\|^2$ , ce qui prouve bien que la projection est 1-lipschitzienne.