Combinaison convexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En géométrie affine, une combinaison convexe de certains points est un barycentre de ces points avec des coefficients tous positifs[1]. L'ensemble des combinaisons convexes de ces points est donc leur enveloppe convexe.

Définition[modifier | modifier le code]

Étant donnés trois points x_1, x_2, x_3 dans un plan, le point P est une combinaison convexe des trois points, tandis que Q ne l'est pas (Q est seulement une combinaison affine des trois points).

Soit E un espace affine réel (c'est-à-dire que les scalaires sont les nombres réels). Si x_1, \ldots, x_n sont des points de E, une combinaison convexe des x_i est[1] un point p de la forme

p=\sum_{i=1}^n\lambda_ix_i~,

\lambda_1, \ldots, \lambda_n sont des réels positifs de somme 1.

Problème du point extrême[modifier | modifier le code]

Le problème du point extrême consiste à déterminer si un point P0 est ou non une combinaison convexe de points Pi, i ≤ 1 ≤ n. Dobkin et Reiss[2] ont montré que ce problème avait une complexité linéaire, en O(n), dans \mathbb{R} et \mathbb{R}^2. Megiddo[3] a montré que la complexité était linéaire en dimension finie, dans \mathbb{R}^d avec d fini.

La résolution se ramène savoir s'il existe une droite (dans \mathbb{R}^2), un plan (dans \mathbb{R}^3) ou un hyperplan (dans \mathbb{R}^d, d > 3) passant par P0, tel que tous les points Pi sont du même côté de la droite, du plan ou de l'hyperplan. Cela revient donc au problème de séparation : séparer un ensemble de points par un hyperplan.

Dans le plan, la recherche peut se faire de la manière suivante[3]. On effectue une transformation affine de sorte que P0 ait pour coordonnées (0 ; 0) et P1(0 ; 1) ; de ce fait, la droite de séparation, si elle existe, ne peut pas être l'axe des y. Le point Pi a pour coordonnées (xi, yi).

La ligne cherchée passe par P0, l'origine, et a donc pour équation :

y = ax, ce qui s'écrit également si x est non nul y/x = a.

Cette droite délimite deux demi-plans d'équation (y < ax) et (y > ax).

Si P0 n'est pas dans l'enveloppe convexe, alors tous les points sont dans le même demi plan, c'est-à-dire que tous les points doivent être au-dessus de la droite (puisqu'au moins un point, P1, l'est). On doit donc avoir pour tout i

yi > axi

soit

  • si xi > 0, alors yi/xi > a ;
  • si xi < 0, alors yi/xi < a.

On a donc la condition nécessaire et suffisante pour que a existe, c'est-à-dire pour que P0 soit hors de l'enveloppe convexe :

 \left \{ \begin{align}
\max \{y_i/x_i, x_i < 0\} & < \min \{y_i/x_i, x_i > 0\} \\
y_i > 0 & \text{ si } x_i = 0
\end{align} \right .

Note et référence[modifier | modifier le code]

  1. a et b Aviva Szpirglas, Algèbre L3 : Cours complet avec 400 tests et exercices corrigés [détail de l’édition] Définition 4.28
  2. (en) D. P. Dobkin et S. P. Reiss, « The complexity of linear programming », Theoretical Computer Science, no 11,‎ 1980
  3. a et b (en) Nimrod Megiddo, « Linear-time algorithms for linear programming in \R^3 and related problems », SIAM Journal on Computing, vol. 4,‎ 1983, p. 766-769 (DOI 10.1137/0212052, lire en ligne)