GéométrieNotion · Glossaire
Combinaison convexe
Une combinaison convexe de points (ou de vecteurs) est une combinaison linéaire à coefficients positifs ou nuls dont la somme vaut 1. Géométriquement, toute combinaison convexe de deux points est un point du segment reliant ces deux points. L'enveloppe convexe d'un ensemble est l'ensemble de toutes les combinaisons convexes de ses points. Cette notion est fondamentale en géométrie convexe, en optimisation et dans la théorie des jeux.
Sommaire
Ce que vous allez apprendre
- Reconnaître les conditions sur les coefficients.
- Calculer les coordonnées d'une combinaison convexe de trois points.
- Interpréter le résultat dans un segment, un triangle ou une enveloppe convexe.
- Distinguer combinaison convexe, affine et linéaire.
En clair
Placez deux points A et B, puis choisissez 30 % de A et 70 % de B. Le point obtenu reste sur le segment AB : les deux poids sont positifs ou nuls et leur total vaut 100 %.
Avec trois points, le même partage produit un point à l'intérieur du triangle, bords compris. Une combinaison convexe est donc une moyenne pondérée qui ne sort pas de la forme délimitée par les points choisis.
Définition
Considérons un nombre fini de points ou de vecteurs, notés x1, …, xn, dans un espace vectoriel réel. À chacun est associé un nombre réel appelé coefficient, noté λi. Leur combinaison est convexe lorsque chaque coefficient est positif ou nul et que leur somme vaut 1. Le point obtenu, noté x, s'écrit :
Pour deux points A et B, les coefficients peuvent être écrits t et 1 − t, avec 0 ≤ t ≤ 1. Toutes les valeurs obtenues parcourent exactement le segment AB, extrémités comprises. Pour trois points non alignés, toutes les combinaisons convexes remplissent le triangle qu'ils déterminent, bord compris. Plus généralement, l'ensemble de toutes les combinaisons convexes finies des points d'un ensemble est son enveloppe convexe.
Un exemple, pas à pas
On considère les points A de coordonnées (0 ; 0), B de coordonnées (4 ; 0) et C de coordonnées (1 ; 3). Les poids respectifs sont 0,2, 0,3 et 0,5.
1. Additionnez les poids : 0,2 + 0,3 + 0,5 = 1. Ils sont tous positifs ou nuls ; les deux conditions sont satisfaites.
2. Calculez l'abscisse du point P : 0,2 × 0 + 0,3 × 4 + 0,5 × 1 = 1,7.
3. Calculez son ordonnée : 0,2 × 0 + 0,3 × 0 + 0,5 × 3 = 1,5.
Le résultat est donc P(1,7 ; 1,5). La figure matérialise sa position dans le triangle ABC. Pour contrôler le calcul, on peut vérifier que P reste du même côté que l'intérieur du triangle par rapport à chacun de ses trois côtés ; ses poids non négatifs de somme 1 garantissent ce résultat.
En pratique
En géométrie convexe, on combine des points connus pour décrire toute la zone qu'ils engendrent. Si l'on veut seulement suivre une droite sans rester entre les points, une combinaison affine ou linéaire convient mieux.
En optimisation sur un ensemble convexe, on teste un point intermédiaire entre deux solutions admissibles. La combinaison convexe est adaptée lorsque ce mélange doit rester admissible ; si le domaine présente un trou, cette garantie disparaît.
En théorie des jeux, des probabilités peuvent pondérer plusieurs stratégies. Le choix est une combinaison convexe lorsque les probabilités sont positives ou nulles et totalisent 1 ; des poids de somme différente ne décrivent pas une répartition probabiliste.
À ne pas confondre
Combinaison linéaire. Ses coefficients peuvent être négatifs et leur somme n'est pas imposée. Ainsi, 2A − B est une combinaison linéaire, mais pas une combinaison convexe de A et B.
Combinaison affine. La somme des coefficients vaut 1, mais leur signe est libre. Avec les poids 2 et −1, le point reste sur la droite AB et sort généralement du segment AB : la combinaison est affine, non convexe.
Enveloppe convexe. Une combinaison convexe produit un point à partir de points choisis. L'enveloppe convexe est l'ensemble de tous les points que toutes ces combinaisons permettent d'obtenir.
Limites et pièges
Un coefficient négatif. Dès qu'un poids est inférieur à 0, la combinaison n'est plus convexe. Le point peut alors sortir du segment, du triangle ou de l'enveloppe convexe ; il faut parler de combinaison affine si la somme reste égale à 1.
Une somme différente de 1. Même avec des coefficients tous positifs, une somme de 0,9 ou de 1,1 ne donne pas une combinaison convexe. Il faut normaliser les poids en divisant chacun par leur somme, à condition que cette somme soit non nulle.
Un cas dégénéré. Un coefficient peut valoir 1 et tous les autres 0 : le résultat est alors exactement l'un des points de départ. Des points alignés ou confondus donnent aussi une enveloppe aplatie, sans invalider la définition.
Une famille infinie. La définition usuelle de l'enveloppe convexe repose sur des combinaisons finies. Une somme ou une moyenne portant sur une infinité de points demande en plus un cadre de convergence ; elle ne doit pas être assimilée automatiquement au cas fini.
Pour aller plus loin
Enveloppe convexe — Passez d'un point obtenu par pondération à l'ensemble complet de tous les points accessibles.
Combinaison linéaire — Situez la combinaison convexe dans le cadre plus large où les signes et la somme des coefficients sont libres.
barycentre — Reliez les coefficients à l'interprétation d'un point comme moyenne pondérée.
La géométrie convexe — Replacez segments, enveloppes et mélanges de points dans le domaine qui étudie leur structure.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres