MPI - Convexité 1

CONVEXITE

1 Parties convexes d’un espace vectoriel réel

E est un R-espace vectoriel.

1.1 Barycentre
p
Définitions : soit (xi )1≤i≤p ∈ E p (p ∈ N∗ ). Soit (λi )1≤i≤p ∈ Rp tel que
P
λi 6= 0.
i=1
p
1 P
On appelle barycentre des points pondérés ((xi , λi ))1≤i≤p l’élément p
P λ i xi .
λi i=1
i=1
p
1 P
Si tous les λi sont égaux, on parle d’isobarycentre, qui vaut alors p xi .
i=1
Pour p = 2, on parle alors de milieu.

Exemples

α. L’isobarycentre des racines n-ièmes de l’unité est nul (pour n ≥ 2).

β. Le centre de gravité d’un triangle de sommets A, B et C d’affixes respectives a, b et c est le

point d’affixe a+b+c
3 . C’est l’isobarycentre des points A, B et C.

γ. L’espérance d’une varaible aléatoire réelle X prenant les valeurs x1 , . . . , xn avec les probabilités
p1 , . . . , pn n’est autre que le barycentre des réels x1 , . . . , xn pondérés par leurs probabilités i.e.
(xi , P(X = xi ))1≤i≤n .

δ. En physique, on parle de centre de masse

.
Remarque : on ne change pas le barycentre en multipliant toutes les masses par le même réel µ 6= 0.

Proposition 1 (Associativité)
p
P
Soient ((xi , λi ))1≤i≤p et ((yi , µi ))1≤i≤q deux familles de points pondérés. On note s1 = λi et
i=1
q
P
s2 = µi . On suppose que s1 6= 0, s2 6= 0 et s1 + s2 6= 0.
i=1
Alors le barycentre de la famille de points pondérés ((x1 , λ1 ), . . . , (xp , λp ), (y1 , µ1 ), . . . , (yq , µq )) est
le barycentre des points pondérés (b1 , s1 ), (b2 , s2 ) où b1 et b2 sont les barycentres respectifs de
((xi , λi ))1≤i≤p et ((yi , µi ))1≤i≤q .


p q
1 X 1 X
b1 = λ i xi et b2 = µi yi .
s1 s2
i=1 i=1

Alors
p q
!
1 X X 1
p q λi xi + µi yi = (s1 b1 + s2 b2 ). 
P P s1 + s2
λi + µi i=1 i=1
i=1 i=1
MPI - Convexité 2

Remarques
−−→
1. L’ensemble des barycentres de deux points A et B distincts est la droite (AB), i.e. A+ Vect(AB).

2. Si A, B et C ne sont pas alignés, l’ensemble des barycentres de A, B et C est le plan (ABC)

−−→ −→
i.e. A+ Vect(AB, AC).

Définition : on appelle barycentre à coefficients positifs des points x1 , . . . xp tout élément de la forme
p p
λi xi où (λi )1≤i≤p ∈ (R+ )p avec
P P
λi = 1.
i=1 i=1

Remarques

1. Pour deux points A et B, l’ensemble des barycentres à coefficients positifs est [A, B].
c−b a−c
2. Dans le cas où E = R, avec (a, b) ∈ R2 , a < b, pour c ∈ [a, b], c = a−b a + a−b b.

1.2 Parties convexes

Définition : une partie C de E est convexe lorsque

∀(a, b) ∈ C 2 , ∀λ ∈ [0, 1], λa + (1 − λ)b ∈ C.

Exemples

α. Tout sous-espace vectoriel (resp affine) de E est convexe.

β. Si k.k est une norme sur E, pour a ∈ E et r ∈ R∗+ , B(a, r) et B 0 (a, r) sont convexes.

γ. Les parties convexes de R sont les intervalles de R.

Proposition 2
Soit C ⊂ E. C est convexe si et seulement si C est stable par passage au barycentre à coefficients
positifs.

 Supposons C convexe. Montrons par récurrence sur p ∈ N∗

p
X p
X
(Hp ) ∀((xi , λi ))1≤i≤p avec ∀i ∈ [| 1, p|], λi ≥ 0, λi = 1, alors λi xi ∈ C.
i=1 i=1

(H1 ) et (H2 ) sont vraies pour p = 1 et p = 2.

Soit p ∈ N∗ tel que (Hp ) soit vraie et montrons (Hp+1 ).
p
P
Si λp+1 = 1, alors pour tout i ∈ [| 1, p|], λi = 0 et λi xi = xp+1 ∈ C.
i=1
p p p
P P P λi
Si λp+1 6= 1, alors λi > 0. Posons s = λi et b = s xi ∈ C par (Hp ).
i=1 i=1 i=1
p+1
X p
X
λi xi = λi xi + λp+1 xp+1 = sb + (1 − s)xp+1 ∈ C.
i=1 i=1

Réciproquement, soit (a, b) ∈ C 2. Soit λ ∈ [0, 1]. λa + (1 − λ)b ∈ C car λ ≥ 0, 1 − λ ≥ 0 et

λ + 1 − λ = 1. 
MPI - Convexité 3

2 Enveloppe convexe
2.1 Définition
Définition : soit A une partie de E. On appelle enveloppe convexe de A l’intersection de toutes les
parties convexes contenant A.
E est une partie convexe contenant A, donc l’enveloppe convexe de A est bien définie.

Proposition 3
Soit A une partie de E. L’enveloppe convexe de A est une partie convexe de E et c’est la plus petite
partie convexe de E (au sens de l’inclusion) qui contient A.

 Une intersection quelconque de convexes est convexe. 

Proposition 4
Soit A une partie de E. L’enveloppe convexe de A est l’ensemble des barycentres à coefficients positifs
d’un nombre fini d’éléments de A.

 Notons Conv(A) l’enveloppe convexe de A et ∆ l’ensemble des barycentres à coefficients positifs d’un
nombre fini d’éléments de A. Comme A ⊂ Conv(A), et comme Conv(A) est convexe, ∆ ⊂ Conv(A).
Montrons que ∆ est convexe. Comme il contient A, alors Conv(A) ⊂ ∆.
Soient a et b dans ∆. Soit λ ∈ [0, 1]. λa + (1 − λ)b est un barycentre à masses positives de a et de
b. Or a et b sont des barycentres à masses positives d’éléments de A. Par associativité du barycentre,
λa + (1 − λ)b est un barycentre à masses positives d’éléments de A. 

2.2 Théorème de Carathéodory

Théorème 1
On suppose E de dimension finie n. Soit A une partie de E. L’enveloppe convexe de A est l’ensemble
des barycentres à masses positives d’au plus n + 1 points de A.

 On note Conv(A) l’enveloppe convexe de A et Γ l’ensemble des barycentres à masses positives d’au
plus n + 1 points de A. Avec le résultat précédent, on a Γ ⊂ Conv(A).
Montrons Conv(A) ⊂ Γ.
p+1
P
Soit x ∈ Conv(A). Ecrivons x = λi xi avec p ∈ N et pour tout i ∈ [| 1, p + 1|], λi ≥ 0, xi ∈ A et
i=1
p+1
P
λi = 1.
i=1

Si p ≤ n, on a ce qu’on veut. On suppose donc dorénavant, p ≥ n + 1.

La famille (xi − xp+1 )1≤i≤p est donc liée : il existe (αi )1≤i≤p une famille de réels non tous nuls, telle
que
p p p
!
X X X
αi (xi − xp+1 ) = 0, i.e. αi xp+1 = αi xi .
i=1 i=1 i=1
p
P
Si αi 6= 0, on a
i=1
p
X
xp+1 = νi xi
i=1
MPI - Convexité 4

p
P
avec νi = 1 et finalement,
i=1
p+1
X
µ i xi = 0
i=1
p+1
P
avec µi = 0 et µp+1 = 1.
i=1
p
P
Si αi = 0, comme un des αi est non nul, mettons αi0 , en divisant par celui-ci, on aboutit à la
i=1
relation précédente, mais avec µi0 = 1 et non plus µp+1 . On continue la preuve en se plaçant dans le
premier cas.
On choisit k ∈ [| 1, p + 1|] tel que µλkk soit le minimum des µλii pour 1 ≤ i ≤ p + 1 avec µi > 0 (ensemble
λp+1
non vide qui contient au moins µp+1 ). On a alors

p+1
X −µi
xk = xi
µk
i=1,i6=k

et donc
p+1   p+1
X µi X
x= λi − λk xi = δ i xi .
µk
i=1,i6=k i=1,i6=k

Mais, on a
p+1 p+1 p+1 p+1 p+1
X X λk X X λk X
δi = λi − µi = λi − (−µk ) = λi + λk = 1
µk µk
i=1,i6=k i=1,i6=k i=1,i6=k i=1,i6=k i=1,i6=k

et pour i ∈ [| 1, p + 1|], i 6= k, si µi ≤ 0, alors δi = λi − λk µµki ≥ 0 et sinon, comme µλii ≥ µλkk , on a bien,

δi ≥ 0. Finalement, x s’écrit comme un barycentre à masses positives de p éléments de A.
Tant que p > n + 1, on peut itérer le procédé et enlever un élément. En un nombre fini d’étapes, on
arrive bien à p ≤ n + 1. 

Application

Proposition 5
Soit A une partie compacte de E, alors l’enveloppe convexe de A est compacte.