Ensemble convexe

Modèle:Autre Un objet géométrique est dit convexe lorsque, chaque fois qu'on y prend deux points Modèle:Formule et Modèle:Formule, le segment Modèle:Formule 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

Fichier:Convex polygon illustration1.svg

Une partie convexe.

Fichier:Convex polygon illustration2.svg

Une partie non convexe.

On suppose travailler dans un contexte où le segment Modèle:Formule reliant deux points quelconques Modèle:Formule et Modèle:Formule a un sens (par exemple dans un espace affine sur ℝ — en particulier dans un espace affine sur ℂ — ou dans un Modèle:Lien).

Sauf précision explicite, tout ce qui suit concerne le seul contexte des convexes dans des espaces affines (ou vectoriels), pour lesquels la notion de segment est défini comme ci-dessus.

On appellera dimension d'un convexe non vide Modèle:Formule la dimension du sous-espace affine engendré par Modèle:Formule.

Exemples

• Les demi-espaces ouverts ou fermés délimités par un hyperplan d'un ℝ-espace vectoriel<ref>Modèle:Ouvrage.</ref> — ou plus généralement : affine — sont convexes.
• 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 d'un espace vectoriel.
• Dans un espace vectoriel normé réel, toute boule (ouverte ou fermée) est convexe.
• Soit <math>P_1, ..., P_n</math> des points d'un espace vectoriel réel V. Soit E l'ensemble de toutes les combinaisons linéaires <math>t_1 P_1+... +t_n P_n</math> avec <math> 0\leqslant t_i </math> pour tout <math> i</math> et <math> t_1+ ... + t_n=1.</math>. L'ensemble E est convexe<ref>Modèle:Ouvrage</ref>.

Propriétés élémentaires et outils fondamentaux

Intersections de convexes

L'intersection de deux convexes (et même d'une famille quelconque de convexes) est elle-même convexe<ref>Modèle:Ouvrage, réimpression avec corrections, Th. 1, Modèle:P.. (Le résultat est énoncé dans ℝⁿ dans cette source, mais la preuve s'adapte évidemment à une situation plus générale.)</ref> (et ce très généralement, dès lors qu'on peut définir la convexité).

Stabilité par barycentres à coefficients positifs

La définition de la convexité repose, après le choix de deux points quelconques Modèle:Formule et Modèle:Formule, sur la considération des points du segment Modèle:Formule, autrement dit des barycentres à coefficients positifs de ces deux points. En utilisant le théorème d'associativité des barycentres, on peut étendre aux barycentres à coefficients positifs d'un nombre quelconque de points<ref>Modèle:Harvsp. (Le résultat est énoncé dans ℝⁿ dans cette source, mais la preuve s'adapte évidemment à une situation plus générale.)</ref> :

Enveloppe convexe

Étant donné une partie quelconque Modèle:Formule de l'espace ambiant Modèle:Formule (espace affine ou contexte plus général), il existe au moins un sous-ensemble convexe de Modèle:Formule contenant Modèle:Formule, à savoir Modèle:Formule lui-même ; ceci autorise à considérer l'intersection de tous les sous-ensembles convexes de Modèle:Formule contenant Modèle:Formule. On l'appelle l'enveloppe convexe de Modèle:Formule et on la note Modèle:Formule<ref name=AB/> ou Modèle:Formule.

On vérifie aussitôt que Modèle:Formule est donc le plus petit sous-ensemble convexe de Modèle:Formule contenant Modèle:Formule, au sens de l'inclusion sur Modèle:Formule. Si Modèle:Formule et Modèle:Formule sont deux points de Modèle:Formule, Modèle:Formule est le segment Modèle:Formule.

Le théorème de la projection

À 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é non vide, pour tout point Modèle:Formule de l'espace, il existe un et un seul point Modèle:Formule du convexe à distance minimale de Modèle:Formule. Ce résultat est accompagné de diverses informations complémentaires, notamment le caractère obtus de l'angle <math>\widehat{x p(x) m}</math> pour tout point Modèle:Formule du convexe, ou le caractère 1-lipschitzien de l'application Modèle:Formule.

Séparation des convexes et structure de la frontière

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

Modèle:Article détaillé L'étude des ensembles convexes peut bénéficier des résultats d'analyse qui concernent les fonctions convexes. Plusieurs telles fonctions peuvent en effet être associées à un convexe non vide Modèle:Formule.

• La plus simple est sa fonction indicatrice, variante de la fonction caractéristique adaptée à la convexité : c'est la fonction qui prend la valeur 0 sur Modèle:Formule, et la valeur Modèle:Formule en dehors ;
• Lorsque l'espace ambiant est un espace vectoriel de dimension finie, muni d'une structure euclidienne, on peut ensuite considérer la fonction conjuguée de la précédente, qu'on appelle alors la fonction d'appui de Modèle:Formule ;
• Enfin, relativement à chacun des points de Modèle:Formule, on peut définir la jauge du convexe, qui est reliée de façon très parlante à sa géométrie et utile notamment dans certaines preuves des théorèmes de séparation des convexes.

Propriétés topologiques

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

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é

Une partie convexe d'un espace affine réel (ou complexe) est connexe par arcs, car tout segment reliant deux points constitue un chemin entre ces deux points. En particulier, elle est donc connexe.

Cependant, une partie convexe d'un espace quelconque n'est pas forcément connexe. Un contre-exemple est donné par l'intervalle fermé des nombres rationnels compris entre 0 et 1 : c'est un ensemble convexe de ℚ qui est totalement discontinu.

Enveloppe convexe-fermée d'un ensemble

Si Modèle:Formule est une partie quelconque de l'espace on désigne par enveloppe convexe-fermée de Modèle:Formule, et l'on note Modèle:Math, l'adhérence Modèle:Math de son enveloppe convexe. On vérifie aisément que Modèle:Formule est aussi l'intersection des convexes fermés contenant Modèle:Formule (« plus petit » convexe fermé contenant Modèle:Formule), et que Modèle:Math a même enveloppe convexe-fermée que Modèle:Math et Modèle:Surligner.

La forme géométrique du théorème de Hahn-Banach permet de montrer que dans un espace localement convexe, Modèle:Math est l'intersection des demi-espaces fermés contenant Modèle:Math<ref>Modèle:Ouvrage.</ref>, ce qui prouve que tout convexe fermé est faiblement fermé.

Dans un espace de Banach — ou plus généralement de Fréchet — l'enveloppe convexe-fermée d'un compact est compacte<ref name=AB>Modèle:Ouvrage.</ref>.

Description à homéomorphisme près en dimension finie

Pour Modèle:Formule, on notera Modèle:Formule une boule fermée de centre 0 et de rayon non nul dans un espace vectoriel séparé de dimension finie Modèle:Math (pour n'importe quelle norme — toutes sont équivalentes).

Les compacts convexes disposent d'une structure simple :

Modèle:Démonstration/début On se place dans le [[sous-espace affine engendré|sous-espace affine Modèle:Formule engendré]] par Modèle:Math, muni de sa topologie canonique. Dans cet espace, [[Adhérence, intérieur et frontière d'un convexe#Intérieur et intérieur relatif d'un convexe|l'intérieur de Modèle:Math est non vide]]. Par translation, on peut donc supposer que Modèle:Math contient une boule Modèle:Math, de rayon Modèle:Math. Notons Modèle:Formule la sphère qui la borde. Pour tout vecteur Modèle:Formule de Modèle:Formule, l'intersection de Modèle:Math avec la demi-droite ℝ₊Modèle:Math est un convexe compact de ℝ₊Modèle:Math contenant Modèle:Math, c'est-à-dire un segment de la forme Modèle:Math. De plus, l'extrémité Modèle:Math appartient à la frontière Modèle:Math (donc Modèle:Math), tandis que tout autre point du segment est intérieur à Modèle:Math (car il est intérieur à l'enveloppe convexe de Modèle:Math).

• L'application Modèle:Math, de Modèle:Math dans Modèle:Math, est un homéomorphisme.
  En effet, d'après ce qui précède, c'est la bijection réciproque de l'application Modèle:Math, continue sur le compact Modèle:Math.
• Modèle:Formule est homéomorphe à Modèle:Math.
  On étend Modèle:Math en une bijection Modèle:Math de Modèle:Math dans Modèle:Math en posant Modèle:Math, pour tout Modèle:Math dans Modèle:Math et tout Modèle:Math dans Modèle:Math. Cette application est continue en tout vecteur non nul. Comme Modèle:Math est bornée (car Modèle:Math est compact), Modèle:Math est aussi continue en 0. C'est donc bien, comme Modèle:Math, un homéomorphisme entre deux compacts.

Plus généralement, les convexes fermés d'une dimension finie Modèle:Formule donnée sont homéomorphes à l'un ou l'autre d'un nombre limité (Modèle:Formule) de modèles simples :

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 : ℝModèle:3 tout entier, la région délimitée par deux plans parallèles, un cylindre, une boule dans ℝModèle: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 Modèle:Formule 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.

Il ne faut pas espérer une classification aussi simple des convexes sans condition topologique : qu'on songe que toute partie de ℝ² contenant le disque unité ouvert et incluse dans le disque unité fermé est convexe<ref>L'ensemble de cette sous-section est issu de Modèle:Berger2, section II-3, tome 3, Modèle:P. dans l'édition de 1978.</ref>.

Ensembles convexes et géométrie combinatoire

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

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) : Modèle:Retrait

Les théorèmes de Radon, Helly et Carathéodory

Modèle:Loupe Considérons un ensemble <math>A = \{a_1, \dots, a_{d+2}\}</math> de Modèle:Formule points dans un espace affine de dimension Modèle:Formule.

Le théorème de Radon affirme que : Modèle:Théorème

Pour énoncer de façon parallèle les théorèmes de Helly et Carathéodory, on va introduire une notation : pour chaque indice Modèle:Formule variant entre 1 et Modèle:Formule, notonsModèle:Retrait l'enveloppe convexe des points de Modèle:Formule autres que le point Modèle:Formule. En dimension 2, chaque Modèle:Math 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.

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.

Notes et références

<references/>

Article connexe

Ensemble absolument convexe