Théorème de projection sur un convexe fermé

En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance dont le principal corollaire est l'existence d'un supplémentaire orthogonal, donc d'une projection orthogonale sur un sous-espace vectoriel. Dans le cadre particulier d'un espace de Hilbert, il remplace avantageusement le théorème de Hahn-Banach. Il est en effet plus simple à démontrer et plus puissant dans ses conséquences.

Il possède de nombreuses applications, en analyse fonctionnelle, en algèbre linéaire, en théorie des jeux, pour la modélisation mathématiques des sciences économiques ou encore pour l'optimisation linéaire.

Énoncé du théorème

Dans cet article E désigne un espace préhilbertien réel, c'est-à-dire un espace vectoriel sur R muni d'un produit scalaire, x désigne un vecteur et C un ensemble convexe complet de E. La distance entre x et C désigne la borne inférieure des distances entre x et un point de C.

La version la plus générale du théorème est la suivante :

Théorème de la projection sur un convexe complet —  Il existe une unique application t de E dans C, dite projection sur le convexe, qui à x associe le point t(x) de C, tel que la distance de x à C soit égale à celle de x à t(x). Le vecteur t(x) est l'unique point de C vérifiant les deux propositions suivantes, qui sont équivalentes :

$(1) \quad \forall y \in C \quad \| x - t(x) \| \le \| x - y \|$ $(2) \quad \forall y \in C \quad \langle x - t(x) \, , \, y - t(x) \rangle \; \le \; 0$

Dans le cas où l'espace E est de Hilbert, c'est-à-dire complet, supposer que C est complet équivaut à supposer qu'il est fermé. L'application t est parfois dénommée projecteur de meilleure approximation^[1].

Démonstration

• Montrons l'existence de t(x) vérifiant (1) :

Soit δ la distance entre x et C, (y_n) une suite de C tel que le carré de la distance entre x et y_n soit inférieur ou égal à δ² + 1/n. Soit n et m deux entiers, alors d'après l'identité du parallélogramme,

$2\|y_n -x\|^2 + 2\|y_m -x\|^2=\|y_n + y_m-2x\|^2+\| y_n - y_m \|^2,$

ce qui se réécrit :

$\| y_n - y_m \|^2 = 2\|y_n -x\|^2 + 2\|y_m -x\|^2 - 4\| \frac{y_n + y_m}2 -x \|^2.$

En majorant les deux premiers termes du second membre de l'égalité et en remarquant que le milieu de y_n et y_m est un point de C donc à une distance supérieure ou égale à δ de x, on obtient :

$\| y_n - y_m \|^2 \; \le \; 2(\delta^2 + \frac 1n) + 2(\delta^2 + \frac 1m) - 4\delta^2=2\Big( \frac 1n + \frac 1m\Big)$

La dernière majoration établit le fait que la suite (y_n) est de Cauchy donc convergente dans C qui est complet. La limite est un point de C, dont la distance à x est minimale.

• Montrons l'unicité de t(x) vérifiant (1) :

Soient y₁ et y₂ deux points de C à distance δ de x. Par le même calcul que ci-dessus,

$\| y_1 - y_2 \|^2 \le 2\delta^2 + 2\delta^2 - 4\delta^2=0$

donc y₁=y₂.

Rappelons les deux majorations du théorème.

$(1) \quad \forall y \in C \quad \| x - t(x) \| \le \| x - y \|$ $(2) \quad \forall y \in C \quad \langle x - t(x) \, , \, y - t(x) \rangle \; \le \; 0$

• Montrons que la propriété (1) implique (2) :

Soient y un élément de C et θ un réel compris entre 0 et 1, alors le barycentre θ y + (1 - θ) t(x), élément de C, est plus éloigné de x que t(x), d'après la propriété (1), donc :

$\| x - t(x) \|^2 \le \| x - t(x) -\theta (y-t(x))\|^2$

On en déduit la majoration :

$2\theta\ \langle x - t(x) \, , \, y - t(x)\rangle\le \theta^2 \| y - t(x) \|^2$

Il suffit alors de diviser par θ puis de passer à la limite quand θ tend vers 0 (par valeurs strictement positives) pour obtenir le résultat.

• Montrons que la propriété (2) implique (1) :

$\|x -y\|^2=\|x -t(x)\|^2-2 \langle x - t(x) \, , \, y - t(x)\rangle+\|y -t(x)\|^2\ge \|x -t(x)\|^2$.

Remarquons qu'ici, la convexité de C n'est pas utile.

Elle possède de plus les propriétés suivantes :

Propriétés de la projection —  La projection t est idempotente, c'est-à-dire que la composée de l'application t avec elle-même est égale à t ; elle est 1-lipschitzienne, c'est-à-dire que les images de deux points sont à une distance moindre que leurs antécédents ; enfin elle est monotone au sens suivant :

$\forall x_1,x_2 \in E \quad \langle t(x_1) - t(x_2) , x_1 - x_2\rangle \ge 0$

Démonstration

• L'application t est idempotente :

En effet, si x est un élément de E, t(x) est élément de convexe, son image est donc lui-même.

• L'application t est "monotone" :

C'est une conséquence directe du fait que <t(x₁) - x₁ , t(x₁) - t(x₂)> et <t(x₂) - x₂ , t(x₂) - t(x₁> sont tous deux négatifs ou nuls. En sommant ces deux inégalités on obtient que

$\langle t(x_1) - t(x_2) , x_1 - x_2\rangle \ge \| t(x_1) - t(x_2) \|^2,$

qui est positif ou nul.

• L'application t est 1-lipschitzienne :

se déduit aussi de la minoration ci-dessus, grâce à l'inégalité de Cauchy-Schwarz.

Principaux corollaires

Dans ce paragraphe E désigne un espace de Hilbert réel.

Supplémentaire orthogonal

Article détaillé : Théorème du supplémentaire orthogonal d'un fermé dans un espace de Hilbert.

Le théorème de projection est l'un des outils possibles pour prouver l'existence d'un supplémentaire orthogonal pour tout sous-espace vectoriel fermé d'un Hilbert (ou plus généralement, pour tout sous-espace vectoriel complet d'un préhilbert), donc l'existence d'une projection orthogonale sur ce sous-espace. (Une autre approche pour prouver ce corollaire est d'utiliser simplement l'inégalité de Bessel.)

Ce corollaire est le principal ingrédient de preuve du théorème de représentation de Riesz. Joint à ce dernier, il permet de démontrer le théorème de Lax-Milgram, qui aide à la résolution d'équation aux dérivées partielles.

Ce corollaire permet également, dans le cadre particulier hilbertien, de démontrer une version simplifiée du théorème de Hahn Banach sans faire appel au lemme de Zorn.

Séparation des convexes

Article détaillé : Séparation des convexes.

Il existe une autre forme du théorème de Hahn-Banach :

Premier théorème de séparation —  Soient A et B deux parties de E non vides et disjointes telles que A - B soit un convexe fermé. Il existe alors une forme linéaire continue f telle que :

$\sup_{x \in A} f(x) < \inf_{y \in B} f(y)$.

Ce résultat s'exprime encore sous la forme suivante :

Deuxième théorème de séparation — Soient A et B deux parties de E non vides et disjointes telles que A soit un convexe fermé et B un convexe compact. Alors il existe une forme linéaire continue f telle que :

$\sup_{x \in A} f(x) < \inf_{y \in B} f(y)$.

Dans le cas de la dimension finie, une forme du théorème de la séparation ne nécessite plus le caractère fermé du convexe :

Séparation en dimension finie —  Si E est de dimension finie, soient x un élément de E et C un convexe ne contenant pas x, alors il existe une forme linéaire f non nulle telle que :

$f(x) \ge \sup_{y \in C} f(y)$.

Démonstration

Pour démontrer les théorèmes de séparation, montrons tout d'abord un résultat préliminaire (qui est, dans les deux théorèmes, le cas particulier où B est un singleton)  :

• Soient C un convexe fermé non vide de E et x un élément de E hors de C. Alors il existe une forme linéaire continue f telle que

$f(x) > \sup_{y \in C} f(y)$.

Soient t la projection sur C et f la forme linéaire définie par :

$\forall y \in E \quad f(y) = \langle x-t(x),y\rangle$.

La deuxième caractérisation du projecteur montre que :

$\sup_{y \in C} f(y)\le f(t(x))$.

D'autre part, les vecteurs x et t(x) ne sont pas confondus car x n'est pas élément de C, par conséquent le carré de la norme de leur différence est strictement positif, d'où :

$f(t(x))<f(x)\,$,

ce qui démontre le résultat préliminaire.

• Soient A et B deux parties de E non vides et disjointes telles que A - B soit un convexe fermé. Il existe alors une forme linéaire continue f telle que :

$\sup_{x \in A} f(x) < \inf_{y \in B} f(y)$.

L'ensemble A - B est un convexe fermé non vide ne contenant pas le vecteur nul. Le résultat précédent montre l'existence d'une forme f telle que :

$\sup_{x\in A\; y \in B} f(x)-f(y) < 0 ,$

ce qui démontre la proposition.

• Le resultat précédent reste vrai si A est un convexe fermé et B un convexe compact.

Montrons que A - B est fermé. Soit c un élément de l'adhérence de cet ensemble, alors

$0=d(c,A-B)=\inf_{a\in A}d(a,c+B).$

Par compacité de A et continuité de l'application qui à tout a associe d(a,c+B), il existe donc un élément a de A tel que

$0=d(a,c+B)=d(a-c,B).\,$

Comme B est fermé, il contient alors a-c, donc c appartient à A-B. Ceci démontre que A - B est fermé. Les hypothèses de la proposition précédente sont rassemblées car A - B est convexe, elles permettent de conclure.

• Si E est de dimension finie, soient x un élément de E et C un convexe ne contenant pas x, alors il existe une forme linéaire non nulle telle que :

$\forall y\in C,\qquad f(x) \ge f(y).$

Pour tout élément y de C, notons T_y l'ensemble des formes linéaires f de norme 1 telles que f(x)-f(y) soit positif ou nul. L'objectif est donc de montrer que l'intersection de tous ces T_y est non vide. Or la sphère unité des formes linéaires est compacte car la dimension est finie, et chaque T_y est un fermé de ce compact (comme image réciproque d'un fermé par une application continue). D'après la propriété de Borel-Lebesgue, pour montrer que l'intersection des T_y est non vide, il suffit donc de montrer que pour toute partie finie non vide D de C, l'intersection des T_y quand y varie dans D est non vide.

Soit K l'enveloppe convexe d'une telle partie finie D. Elle forme un convexe fermé non vide et ne contient pas x. Le résultat préliminaire montre l'existence d'une forme linéaire f telle que f(x)>f(y) pour tout y dans K, en particulier pout tout y dans D, ce qui termine la démonstration.

Autres applications

Ce théorème possède de multiples autres applications.

Il est utilisé en analyse fonctionnelle. Il peut donner lieu à des algorithmes programmables en dimension finie. Un exemple est donné par le théorème de Stampacchia.

En théorie des jeux, John von Neumann établit un théorème fondamental montrant l'existence de stratégies optimales pour les différents joueurs dans un contexte très général^[2]. Ce résultat est une conséquence du théorème de projection dans le cadre d'un Hilbert. Il possède de nombreuses conséquences, dont l'une célèbre est l'existence d'un Optimum de Pareto sous des hypothèses pas trop contraignantes en sciences économiques^[3].

En optimisation linéaire, ce théorème est utilisé pour, par exemple dans le cas des théorèmes de l'alternative trouver des solutions à des systèmes d'inéquations linéaires^[4].

Notes et références

Notes

1. ↑ (Aubin 1987) p. 28
2. ↑ (de) John von Neumann, « Zur Theorie der Gesellschaftsspiele » dans Mathematische Annalen, vol. 100 (1928), p. 295-320
3. ↑ Les textes sur ce sujet sont nombreux, par exemple : (en) M. Voorneveld, « Pareto-Optimal Security Strategies as Minimax Strategies of a Standard Matrix Game » dans Journal of Optimization Theory and Applications, 2004, p. 203-210.
4. ↑ G. Dantzig et M. Thapa Linear Programming 2: Theory and Extensions, Springer, 2003 (ISBN 978-0387986135)

Références

• Jean-Pierre Aubin, Analyse fonctionnelle appliquée, Puf, 1987 (ISBN 978-2130392644) 

L'essentiel des démonstrations ainsi que des exemples proviennent de ce livre.

• Haïm Brezis, Analyse fonctionnelle : théorie et applications [détail des éditions]

Ce sujet est rapidement traité en page 79.

Liens externes

• Projection dans un espace de Hilbert sur le site les-mathematiques.net
• Espaces de Hilbert un cours de maîtrise d'analyse fonctionnelle par P. Courilleau, de l'université de Cergy-Pontoise (2006)