Combinaison convexe
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]![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Convex_combination_illustration.svg/220px-Convex_combination_illustration.svg.png)
Soit E un espace affine réel (c'est-à-dire que les scalaires sont les nombres réels). Si et sont des points de E, une combinaison convexe des est[1] un point de la forme
où 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, 1 ≤ i ≤ n. Dobkin et Reiss[2] ont montré que ce problème avait une complexité linéaire, en O(n), dans et . Megiddo[3] a montré que la complexité était linéaire en dimension finie, dans avec d fini.
La résolution se ramène à savoir s'il existe une droite (dans ), un plan (dans ) ou un hyperplan (dans , 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 droite 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 :
Notes et références
[modifier | modifier le code]- Aviva Szpirglas, Algèbre L3 : Cours complet avec 400 tests et exercices corrigés [détail de l’édition] Définition 4.28
- (en) D. P. Dobkin et S. P. Reiss, « The complexity of linear programming », Theoretical Computer Science, no 11,
- (en) Nimrod Megiddo, « Linear-time algorithms for linear programming in and related problems », SIAM Journal on Computing, vol. 4, , p. 766-769 (DOI 10.1137/0212052, MR 721011, lire en ligne)