espace convexe

Imaginez une forme pleine et choisissez deux points n'importe où à l'intérieur. Tendez un fil bien droit entre eux. Si le fil reste entièrement dans la forme, quels que soient les deux points choisis, cette forme est convexe.

Un disque ou un triangle plein possède cette propriété. Une forme en croissant ne l'a pas : certains fils traversent une zone extérieure. La convexité exprime ainsi l'absence de creux, mais avec un test précis fondé sur tous les segments.

Soit E un sous-ensemble d'un espace affine réel. L'ensemble E est convexe lorsque le segment joignant deux quelconques de ses points reste tout entier dans E. Dans un espace vectoriel réel, choisissons deux vecteurs u et v appartenant à E, puis un nombre réel t compris entre 0 et 1. Le point du segment correspondant à t est le vecteur w défini par :

La convexité exige que w appartienne à E pour chaque choix de u, de v et de t. Les coefficients 1 − t et t sont positifs ou nuls et leur somme vaut 1 : w est donc une combinaison convexe de u et v. La même idée s'étend à un nombre fini de points, avec des coefficients positifs ou nuls dont la somme vaut 1. L'ensemble vide et tout singleton sont convexes, car aucun segment ne peut en sortir. Cette propriété dépend de l'ensemble de points, non de sa couleur, de son contour dessiné ou de l'échelle choisie.

Le cadre comprend d'abord un espace affine réel, dans lequel les points et les segments ont un sens, puis un sous-ensemble E à tester. Deux points u et v de E déterminent un segment. Un paramètre réel t compris entre 0 et 1 repère chaque point de ce segment, tandis que les coefficients 1 − t et t indiquent sa position entre les extrémités.

Les deux coefficients dépendent l'un de l'autre puisque leur somme vaut 1. Le point obtenu dépend à la fois des extrémités et de t. Ces données suffisent à construire tout le segment et à vérifier si celui-ci reste dans E. Ce sont l'appartenance des extrémités et celle de tous les points intermédiaires qui définissent la convexité ; l'orientation ou l'apparence du dessin n'intervient pas.

Considérons le triangle plein T formé des points de coordonnées (x, y) qui vérifient x ≥ 0, y ≥ 0 et x + y ≤ 6. Prenons A = (1, 1), B = (3, 3) et le paramètre t = 1/2. Les deux points appartiennent à T : leurs coordonnées sont positives et leurs sommes valent respectivement 2 et 6.

1. On calcule le point M situé à mi-chemin entre A et B.
2. On remplace A et B par leurs coordonnées.
3. On vérifie les trois inégalités qui définissent T.

Les coordonnées de M sont positives et 2 + 2 = 4 ≤ 6, donc M appartient à T. Le même contrôle fonctionne pour tout t entre 0 et 1 : les trois inégalités sont conservées par combinaison convexe. La figure matérialise ce contrôle en montrant le segment rouge entièrement contenu dans le triangle.

En géométrie, le test du segment permet de reconnaître les régions sans creux. Pour un polygone plein, on préfère ce test à une simple inspection du contour dès qu'un angle rentrant peut tromper l'œil.

En optimisation, un domaine convexe autorise le mélange de deux solutions admissibles sans quitter le domaine. Si ce test échoue, les méthodes propres à l'optimisation convexe ne s'appliquent pas directement et il faut traiter plusieurs régions ou employer une méthode non convexe.

En analyse, la convexité du domaine est une hypothèse naturelle pour comparer les valeurs d'une fonction le long d'un segment. C'est le cadre de l'inégalité de Jensen, qui relie une moyenne de points à la moyenne des valeurs d'une fonction convexe.

Ensemble convexe et fonction convexe. Un ensemble convexe contient les segments entre ses points. Une fonction convexe vérifie une inégalité entre ses valeurs le long de ces segments. Un disque est un ensemble convexe ; ce n'est pas une fonction.

Convexe et connexe. Tout ensemble convexe non vide est connexe, car un segment relie deux de ses points. La réciproque est fausse : un croissant plein peut être d'un seul tenant tout en laissant certains segments sortir de la forme.

Ensemble convexe et enveloppe convexe. L'enveloppe convexe d'un ensemble est le plus petit ensemble convexe qui le contient. Trois points non alignés ne forment pas un ensemble convexe, tandis que leur enveloppe convexe est le triangle plein délimité par ces points.

Tester quelques segments ne suffit pas. Une forme peut réussir plusieurs essais et posséder un petit creux ailleurs. Le critère porte sur tous les couples de points et sur chaque valeur de t dans l'intervalle fermé [0, 1].

Le contour seul peut échouer. Le bord d'un disque n'est pas convexe comme ensemble de points : le milieu de deux points opposés se trouve au centre, hors du bord. Il faut distinguer le cercle de la région pleine qu'il délimite.

Les unions sont piégeuses. L'union de deux ensembles convexes n'est pas nécessairement convexe. Deux disques disjoints donnent un symptôme immédiat : un segment reliant leurs centres traverse des points qui n'appartiennent à aucun disque. Il faut tester l'union elle-même ou prendre son enveloppe convexe si tel est l'objet recherché.

Les cas dégénérés restent valides. L'ensemble vide, un point isolé et un segment sont convexes. Ils n'ont pas forcément d'intérieur dans l'espace ambiant ; l'absence d'aire ou de volume ne constitue donc pas un échec du critère.

La combinaison convexe généralise le point d'un segment à plusieurs points et précise le rôle des coefficients positifs de somme 1.

L'inégalité de Jensen montre comment la convexité intervient lorsqu'on compare la valeur d'une fonction en une moyenne avec la moyenne de ses valeurs.

L'article La géométrie convexe replace ces ensembles dans un domaine qui étudie leurs formes, leurs mesures et leurs propriétés.