Ensemble convexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Pour les autres sens du mot « convexe », voir convexité.

Un objet géométrique est dit convexe lorsque, chaque fois qu'on y prend deux points A et B, le segment [A, B] qui les joint y est entièrement contenu. Ainsi un cube plein, un disque ou une boule sont convexes, mais un objet creux ou bosselé ne l'est pas.

Définition[modifier | modifier le code]

Une partie convexe.
Une partie non convexe.

On suppose travailler dans un contexte où le segment [x, y] reliant deux points quelconques x et y a un sens (par exemple dans un espace affine sur — en particulier dans un espace affine sur — ou dans un espace hyperbolique (en)).

Définition — Un ensemble C est dit convexe lorsque, pour tous x et y de C, le segment [x, y] est tout entier contenu dans C, i.e. :

\forall x,y\in C,\quad\forall t\in[0,1],\qquad tx+(1-t)y\in C.

Sauf précision explicite, tout ce qui suit concerne le seul contexte des convexes dans des espaces affines (ou vectoriels).

On appellera dimension du convexe non vide C la dimension du sous-espace affine engendré par C.

Exemples[modifier | modifier le code]

  • Les sous-ensembles convexes de l'espace ℝ des nombres réels sont les intervalles de ℝ.
  • Dans un espace affine, tout sous-espace affine est convexe ; c'est en particulier le cas des sous-espaces vectoriels des espaces vectoriels.
  • Dans un espace vectoriel normé réel, toute boule (ouverte ou fermée) est convexe.

Propriétés élémentaires et outils fondamentaux[modifier | modifier le code]

Intersections de convexes[modifier | modifier le code]

L'intersection de deux convexes (et même d'une famille quelconque de convexes) est elle-même convexe[1] (et ce très généralement, dès lors qu'on peut définir la convexité).

Stabilité par barycentres à coefficients positifs[modifier | modifier le code]

La définition de la convexité fait intervenir le choix de deux points quelconques x et y, puis la considération des points du segment [x, y], autrement dit des barycentres à coefficients positifs de ces deux points. En utilisant le théorème d'associativité des barycentres, on voit sans mal que cela n'aurait rien changé de considérer des barycentres à coefficients positifs d'un nombre quelconque de points. Autrement dit[2] :

Proposition — Un sous-ensemble C d'un espace affine E est convexe si et seulement si toute combinaison convexe d'une famille finie de points de C est elle-même dans C.

Enveloppe convexe[modifier | modifier le code]

Article détaillé : Enveloppe convexe.

Étant donnée une partie quelconque A de l'espace ambiant E (espace affine ou contexte plus général), il existe au moins un sous-ensemble convexe de E contenant A, à savoir E lui-même ; ceci autorise à considérer l'intersection de tous les sous-ensembles convexes de E contenant A. On l'appelle l'enveloppe convexe de A et on la note co(A)[3] ou Conv(A).

On vérifie aussitôt que co(A) est donc le plus petit sous-ensemble convexe de E contenant A, au sens de l'inclusion sur P(E). Si x et y sont deux points de E, co({x, y}) est le segment [x, y].

Le théorème de la projection[modifier | modifier le code]

À condition de travailler dans un espace euclidien (ou plus généralement dans un espace de Hilbert), on dispose d'un résultat remarquable : étant donné un convexe fermé, pour tout point x de l'espace, il existe un et un seul point p(x) du convexe à distance minimale de x. Ce résultat est accompagné de diverses informations complémentaires, notamment le caractère obtus de l'angle \widehat{x p(x) m} pour tout point m du convexe, ou le caractère 1-lipschitzien de l'application p.

Séparation des convexes et structure de la frontière[modifier | modifier le code]

Une technique utile est celle de la « séparation » de deux convexes. Elle consiste, étant donné deux convexes sans point commun d'un même espace, à découper cet espace en deux par un hyperplan (donc un plan, si la dimension est 3) qui laisse les convexes de part et d'autre de ce mur de séparation. Les démonstrations de la possibilité d'un tel découpage sont multiples, permettant d'obtenir des énoncés plus ou moins généraux ; certaines utilisent le théorème de Hahn-Banach, outil d'analyse fonctionnelle particulièrement pertinent pour l'étude en dimension infinie.

Cette méthode permet tout particulièrement de justifier de l'existence en chaque point de la frontière d'un convexe d'un « hyperplan d'appui » : un hyperplan passant par ce point et laissant le convexe tout entier dans l'un des deux demi-espaces qu'il borde. Ce résultat est à son tour fondamental pour étudier plus en détail la structure de la frontière des convexes (divisions en faces, arêtes, etc.) et particulièrement des polyèdres convexes. On est ainsi amenés à distinguer diverses catégories de points (points extrémaux, sommets) qui joueront un rôle central dans les problèmes d'optimisation sur le convexe, par exemple en optimisation linéaire.

Fonctions convexes associées à un ensemble convexe[modifier | modifier le code]

Articles détaillés : Fonction convexe et Jauge (mathématiques).

L'étude des ensembles convexes peut bénéficier des résultats d'analyse qui concernent les fonction convexes. Plusieurs telles fonctions peuvent en effet être associées à un convexe non vide C.

Propriétés topologiques[modifier | modifier le code]

Dans cette section, on suppose l'espace ambiant muni d'une topologie compatible avec sa structure géométrique (c'est toujours le cas dans les espaces de dimension finie ; si on est dans un espace vectoriel de dimension infinie cela revient à exiger qu'il s'agisse d'un espace vectoriel topologique).

Adhérence, intérieur, frontière[modifier | modifier le code]

Les opérateurs d'adhérence et d'intérieur préservent la convexité. En outre, lorsque le convexe considéré n'est pas d'intérieur vide (et on peut facilement se ramener à ce cas en le considérant comme partie de son enveloppe affine et non de l'espace global), le convexe, son intérieur et son adhérence ont tous trois la même frontière.

On peut montrer très facilement qu'un convexe compact est l'enveloppe convexe de sa frontière (hors le cas dégénéré de la dimension 0).

Connexité[modifier | modifier le code]

Une partie convexe est évidemment connexe par arcs donc connexe.

Enveloppe convexe-fermée d'un ensemble[modifier | modifier le code]

Si A est une partie quelconque de l'espace on désigne par enveloppe convexe-fermée de A, et l'on note co(A), l'adhérence co(A) de son enveloppe convexe. On vérifie aisément que co(A) est aussi l'intersection des convexes fermés contenant A (« plus petit » convexe fermé contenant A).

Dans un espace de Banach — ou plus généralement de Fréchet — l'enveloppe convexe-fermée d'un compact est compacte[3].

Description à homéomorphisme près en dimension finie[modifier | modifier le code]

Pour r ≥ 0, on notera Br la boule euclidienne fermée de centre 0 et de rayon 1 dans ℝr.

Les compacts convexes disposent d'une structure simple :

Théorème — Soit C un convexe compact de ℝr, il existe un entier positif d, inférieur ou égal à r tel que C soit homéomorphe à Bd.

Les convexes fermés d'une dimension finie d donnée sont homéomorphes à l'un ou l'autre d'un nombre limité (d + 2) de modèles simples.

Théorème — Soit d ≥ 1 et soit C un convexe de dimension d, fermé dans son espace ambiant. Alors :

  • soit il existe r avec 0 ≤ rd tel que C soit homéomorphe à Br×ℝd – r,
  • soit C est homéomorphe à un demi-espace fermé dans ℝd.

Dans tous les cas, l'homéomorphisme envoie la frontière relative de C sur la frontière relative du modèle.

Pour lire ce théorème sur un exemple instructif, celui de la dimension 3, les convexes fermés de dimension 3 sont homéomorphes à un des cinq modèles suivants : ℝ3 tout entier, la région délimitée par deux plans parallèles, un cylindre, une boule dans ℝ3 ou un demi-espace.

Les intérieurs relatifs de tous les modèles énumérés au théorème précédent sont homéomorphes entre eux, c'est-à-dire homéomorphes à ℝd. L'homéomorphisme donné par le théorème précédent échangeant les intérieurs relatifs, on peut donc en conclure que tous les ouverts convexes de dimension d sont homéomorphes entre eux (ce qui, en réalité, était une étape de la preuve). On peut en fait obtenir mieux, à savoir un difféomorphisme.

Théorème — Soit d ≥ 0 et soit C un convexe de dimension d, ouvert dans son espace ambiant. Alors C est difféomorphe à ℝd.

Il ne faut pas espérer une classification aussi simple des convexes sans condition topologique : qu'on songe que pour toute partie A du cercle-unité de ℝ2 l'ensemble obtenu en réunissant le disque-unité ouvert et A est convexe[4].

Ensembles convexes et géométrie combinatoire[modifier | modifier le code]

Les ensembles convexes jouent un rôle central en géométrie combinatoire, ne serait-ce que parce que, face à un nombre fini de points d'un espace affine, l'opération géométrique la plus évidente qu'on puisse leur appliquer est d'examiner leur enveloppe convexe : ce qu'on appelle un polytope.

Polytopes[modifier | modifier le code]

Article détaillé : Polytope.

L'objet de base de la géométrie combinatoire convexe, c'est le polytope, qu'on peut définir comme enveloppe convexe d'un nombre fini de points.

Pour ne citer ici que l'exemple sans doute le plus fameux de résultat de géométrie combinatoire, en dimension 3, les nombres de sommets, d'arêtes et de faces d'un polytope sont liés par la formule d'Euler (voir à ce sujet l'article Caractéristique d'Euler) : S - A + F = 2.

Les théorèmes de Radon, Helly et Carathéodory[modifier | modifier le code]

Considérons un ensemble A = \{a_1, \dots, a_{d+2}\} de d + 2 points dans un espace affine de dimension d.

Le théorème de Radon affirme que :

Théorème (Radon) — A admet une partition en deux parties A1, A2 dont les enveloppes convexes Conv(A1) et Conv(A2) se rencontrent.

Pour énoncer de façon parallèle les théorèmes de Helly et Carathéodory, on va introduire une notation : pour chaque indice i variant entre 1 et d + 2, notons\Delta_i=\mathrm{Conv}\left(a_1, \dots, a_{i-1}, a_{i+1}, \ldots, a_{d+2}\right) l'enveloppe convexe des points de A autres que le point ai. En dimension 2, chaque Δi serait un triangle (et il y en aurait quatre) ; en dimension 3 on aurait affaire à une collection de cinq tétraèdres, et ainsi de suite.

Les deux énoncés suivants sont des cas particuliers des énoncés les plus courants des théorèmes de Helly et Carathéodory, mais qui en contiennent essentiellement toute l'information : on reconstitue facilement les énoncés généraux à partir des versions fournies ci-dessous.

Théorème (Helly) — Il existe un point commun aux d + 2 simplexes Δi.

Théorème (Carathéodory) — Les d + 2 simplexes Δi recouvrent tout le polytope enveloppe convexe de A.

Ces théorèmes sont étroitement liés : la démonstration la plus courante de Helly est fondée sur Radon, tandis qu'on prouve facilement Carathéodory indépendamment, mais il est aussi possible par exemple de déduire Helly de Carathéodory ou le contraire.

D'innombrables variantes les précisent ou les généralisent.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

Dans les sections renvoyant à un article détaillé, on se réfèrera à cet article détaillé pour les sources à l'appui des informations qui y figurent.

Les références à un auteur sans mention d'ouvrage renvoient au livre de cet auteur mentionné en bibliographie.

  1. Eggleston, Th. 1, p. 8. (Le résultat est énoncé dans ℝn dans cette source, mais la preuve s'adapte évidemment à une situation plus générale.)
  2. Eggleston, p. 4-5. (Le résultat est énoncé dans ℝn dans cette source, mais la preuve s'adapte évidemment à une situation plus générale.)
  3. a et b (en) Charalambos D. Aliprantis (en) et Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide, Springer,‎ 2007 (lire en ligne), p. 185-186.
  4. L'ensemble de cette sous-section est issu de Berger, section II-3, tome 3, p. 29-38 dans l'édition de 1978.
  5. Les détails sont donnés dans l'article Topologie d'un espace vectoriel de dimension finie.

Bibliographie[modifier | modifier le code]