Combinaison convexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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,‎
  3. a et b (en) Nimrod Megiddo, « Linear-time algorithms for linear programming in \R^3 and related problems », SIAM Journal on Computing (en), vol. 4,‎ , p. 766-769 (DOI 10.1137/0212052, lire en ligne)