30/05/2015

Séance du 30/05/2015 de ParisMaths

Ensembles convexes

Dans toute la séance, E désigne un espace vectoriel réel de dimension nie d. On

fera abusivement l'identication de E avec l'espace ane correspondant : on verra les
éléments de E comme des vecteurs ou bien comme des points (en gardant à l'esprit
que la diérence entre deux points est un vecteur). Dans tous les cas, on pourra choisir
brutalement E = Rd si on est un peu perdu avec ces considérations techniques.
L'espace E sera muni de sa structure euclidienne classique : on utilisera sans scrupule
la norme euclidienne k · k et le produit scalaire canonique h·, ·i.

Dénition 1. On dit qu'un ensemble C ⊂ E est convexe si pour tout couple de points
A, B ∈ C , le segment [A, B] est en entier inclus dans C . Ceci est équivalent à la dénition
formelle suivante :

∀(A, B) ∈ C 2 , ∀t ∈ [0, 1], (1 − t)A + tB ∈ C.

Exercice 1
Montrer que les ensembles suivants sont convexes :

1. une intersection d'ensembles convexes ;

B∞ (0, 1) = (x1 , · · · , xd ) ∈ Rd | maxi |xi | ≤


2. la boule unité fermée pour la norme innie
1 ;

(x1 , · · · , xd ) ∈ Rd | maxi |xi | < 1


3. la boule unité ouverte pour la norme innie ;

4. la boule unité fermée pour la norme euclidienne B(0, 1) = x ∈ E | kxk ≤ 1 ;

5. la boule unité fermée pour n'importe quelle norme ;

6. tout cône déni de la manière suivante : si C est un convexe de E, alors le cône C

associé est déni par C = {λx | x ∈ C, λ ∈ R+ }.

Exercice 2
Un convexe C est stable par barycentre : si (Pi )1≤i≤n estP
une collection de points de C
0 ≤ ai ≤ 1 et ni=1 ai = 1), alors ni=1 ai Pi
P
et (ai )1≤i≤n une collection de poids (i.e.
appartient à C.

1 Enveloppe convexe
Exercice 3
Pour un ensemble A ⊂ E, on appelle enveloppe convexe de A, et on note conv(A),
l'intersection de tous les convexes contenant A. Montrer que conv(A) est convexe, puis
qu'il coïncide avec l'ensemble des barycentres de points de A.

Ensembles convexes page 1

 30/05/2015

Exercice 4 (Théorème de Carathéodory)

Attention, cet exercice demande des connaissances de théorie de la dimension. L'en-

veloppe convexe d'un ensemble A deE (de dimension d) est égale à l'ensemble des
barycentres d'au plus d+1 points de A.

Le théorème de Carathéodory sert en particulier à démontrer qu'en dimension nie,

l'enveloppe convexe d'un ensemble compact est elle-même conpacte.

2 Projection sur un convexe compact

Dénition 2. Un ensemble K ⊂ E sera dit compact s'il est fermé et borné . Et un
1

ensemble F ⊂ E est dit fermé si pour toute suite (xn )n∈N de points de F convergeant
vers une limite y , on a aussi y ∈ F .

On pourra utiliser sans le redémontrer le fait suivant : toute fonction continue f :

K → R, avec K un ensemble compact, est bornée et atteint ses bornes.
Dans l'exercice suivant, on aura besoin de la notion de forme linéaire.

Dénition 3. Une forme linéaire est une application linéaire de E dans R.

En particulier, pour toute forme linéaire non nulle `, l'ensemble

ker ` = {x ∈ E | `(x) = 0}

est un hyperplan de E , c'est-à-dire un sous-espace vectoriel de E de dimension dim E −1.

Exercice 5 (Projection sur un convexe compact, et séparation d'un point et d'un

convexe)
Soit C un convexe compact non vide de E, et x ∈ E.
1. Montrer qu'il existe un unique point de E, noté pC (x), tel que

kx − pC (x)k = min kx − yk.

y∈C

2. Montrer que pour tout y ∈ C, on a alors

hx − pC (x), y − pC (x)i ≤ 0.

3. Montrer aussi que pC est 1-lipschitzienne : kpC (x) − pC (y)k ≤ kx − yk.

4. En déduire que si x∈
/ C , il existe une forme linéaire ` de E , et α ∈ R, tels que `(x) > α
et `(y) < α pour tout y ∈ C (on commencera par montrer que kx − pC (x)k > 0).

Avec un soupçon de compacité, on peut montrer l'existence

d'hyperplan d'appui en tout point de la frontière du convexe ,
2 −x
C
c'est-à-dire une forme linéaire ` telle que `(y) ≤ `(x) pour tout
y ∈ C.
1. Attention, ce n'est pas la dénition ocielle !
2. Un point x est à la frontière de C si pour tout r > 0, la boule B(x, r) contient un point de C { .

Ensembles convexes page 2

 30/05/2015

3 Points extrémaux
Dénition 4. Soit C un convexe de E. On dit que x∈C est un point extrémal de C si
C \ {x} est encore convexe.

Exercice 6
Un point x∈C est extrémal si et seulement si pour tout couple de points y, z ∈ C , la
condition il existe λ ∈ [0, 1] tel que x = λy + (1 − λ)z  implique x = y = z.

Exercice 7 (Krein-Milman)
On se propose de démontrer le théorème de Krein-Milman : tout ensemble convexe
compact de E est l'enveloppe convexe de ses points extrémaux.
1. Soient x 6= y deux points de E . Trouver une forme linéaire ` de E (si besoin, consulter
la dénition 3) telle que `(x) < α < `(y). On dit alors que l'hyperplan ker(`−α) sépare
les points x et y .

2. On dit qu'un ensemble non vide F ⊂ C est une face de C si pour tous x, y ∈ C et
λ ∈]0, 1[, λx + (1 − λ)y ∈ F implique que x, y ∈ F . Montrer que pour toute forme
linéaire `, l'ensemble

F` = x ∈ C | `(x) = max `(y)
y∈C
est une face de C . En particulier, ses points extrémaux sont aussi des points extrémaux
de C.
3. En déduire, par récurrence sur dim E , que l'ensemble des points extrémaux de C est
non vide.

4. Conclure en utilisant l'exercice 5.

Dénition 5. Une matrice M ∈ Mn (R) est dite bistochastique si elle est à coecients
positifs et si pour tout 1 ≤ i ≤ n, on a
Xn n
X
mi,j = 1 et mj,i = 1.
j=1 j=1

Une matrice M ∈ Mn (R) est dite de permutation s'il existe une permutation σ ∈ Sn
telle que mi,j = 1 si σ(j) = i, et 0 sinon.

Exercice 8 (Birkho-Von Neumann)

Le but de cet exercice est de démontrer le théorème de Birkho-Von Neumann : l'en-
semble B des matrices bistochastiques est l'enveloppe convexe dans Mn (R) de l'ensemble
des matrices de permutation.

1. Montrer qu'il sut de prouver que les matrices de permutation sont exactement les
points extrémaux de B.
2. Montrer que les matrices de permutation sont des points extrémaux de B.
3. Montrer que si M ∈ B n'est pas une matrice de permutation, alors ce n'est pas un
point extrémal de B . Conclure.

4. En déduire le théorème des mariages de Koenig : tout graphe biparti

3 régulier 4 admet

3. C'est-à-dire qu'il existe une partition E t F de l'ensemble des sommets telle que toute arête relie
un élément de E à un élément de F .
4. C'est-à-dire que le nombre de sommets partant de chaque arête est constant.

Ensembles convexes page 3

 30/05/2015

un couplage parfait .
5

Le théorème de Birkho-Von Neumann doit une partie de son nom au mathématicien Garrett
Moment Birkho, à ne pas confondre avec son père George Birkho, lui aussi mathématicien.
culturel
4 Dualité
Dénition 6. Soit C⊂E un convexe. Le polaire de C est l'ensemble noté C0 et déni
par
C 0 = {y ∈ E | ∀x ∈ C, hx, yi ≤ 1}.

Exercice 9
Quelques propriétés simples du polaire.

1. Le polaire C0 d'un convexe C est lui aussi convexe.

2. Si C contient 0 dans son intérieur, c'est-à-dire qu'il existe r>0 tel que B(0, r) ⊂ C ,
alors C0 est borné.

3. Réciproquement, si C est borné, alors C0 contient 0 dans son intérieur.

4. C⊂ (C 0 )0 .

Exercice 10
Le polaire de quelques ensembles simples

1. Quel est le polaire de la boule unité (pour la norme euclidienne) ?

2. Quel est le polaire d'un ellipsoïde centré en 0 ?


3. Quel est le polaire de la boule unité pour la norme 1, dénie par B1 (0, 1) = (x1 , · · · , xd ) ∈
Rd |
P
i |xi | ≤1 ?

4. Quel est le polaire de la boule unité pour la norme innie, dénie par B∞ (0, 1) =
Rd

(x1 , · · · , xd ) ∈ | maxi |xi | ≤ 1 ?

5 Les polytopes convexes

Dénition 7. Un polytope CA est l'enveloppe convexe d'un ensemble ni de points A.
Un polyèdre est une intersection de demi-espaces de E (i.e. d'ensembles de la forme
`(x) ≤ α, où ` est une forme linéaire et α un réel.

Exercice 11 (Lemme de Farkas)

Soient P1 , · · · , Pm : Rd → R des applications anes 6 . Alors exactement l'une des condi-
tions suivantes est vériée :

(i) le système d'inégalités P1 (x), · · · , Pm (x) ≥ 0 possède au moins une solution x∈

Rd ;
(ii) il existe des réels positifs q1 , · · · , qm ≥ 0 tels que q1 P1 + · · · + qm Pm = −1.
Indication : on pourra raisonner par récurrence sur la dimension d.
5. C'est-à-dire qu'il existe un ensemble d'arêtes deux à deux non adjacentes tel que tout sommet du
graphe est relié à au moins une de ces arêtes.
6. C'est-à-dire que Pi est de la forme `i + αi , où `i est une forme linéaire et αi est un réel.

Ensembles convexes page 4

 30/05/2015

Exercice 12 (Théorème de Hahn-Banach)

Le but de cet exercice est de démontrer une version simpliée du théorème de Hahn-
Banach : pour CA et CB deux polytopes disjoints de E , il existe une application ane
P :E→R telle que P (x) ≤ −1 pour tout x ∈ CA et P (x) ≥ 1 pour tout x ∈ CB .
1. Montrer qu'il sut de vérier les conclusions du théorème pour les points de A et de
B (et non plus de CA et de CB ).
2. En déduire le théorème de Hahn-Banach, en appliquant le lemme de Farkas (exer-
cice 11).

3. Application : montrer que si CA est un polytope, alors

0 )0 = C
(CA (voir la déni-
A
tion 6).

P ≤ −1 P ≥1

A B

Le théorème de Hahn-Banach reste vrai (par exemple) dans le cas où A et B sont

deux convexes compacts.

Exercice 13
Le but de cet exercice est de montrer que tout polytope est un polyèdre borné, et récipro-
quement. On commence par montrer que tout polyèdre borné est un polytope. On dénit
une face d'un polyèdre C comme étant un ensemble de la forme C ∩ {x | `(x) ≤ α}, où
` et α sont utilisés pour dénir C (comme à la dénition 7). Cela permet de dénir les
k -faces de C par récurrence : les d − 1 faces de C sont ses faces, et ses k − 1 faces sont
les faces de ses k -faces.

1. Montrer que les k -faces d'un polyèdre sont en nombre ni.

2. Montrer que les 1-faces d'un polyèdre forment l'ensemble de ses points extrémaux.

3. En déduire que tout polyèdre borné est un polytope.

4. En utilisant la dualité, montrer que tout polytope est un polyèdre borné.

Exercice 14 (Théorème de Helly)

Montrer le théorème de Helly pour les polyèdres : soient C1 , · · · , Cn des polyèdres tels
que pour tout choix de d+1 d'entre-eux, ces d+1 polyèdres se rencontrent. Alors il
existe un point qui appartient à tous le Ci . Question bonus : en déduire le même énoncé,

mais pour des convexes quelconques .

7

6 Volumes
Nous n'avons abordé ici qu'une toute petite partie du thème  convexes en dimension
nie  (et on ne parle même pas de la dimension innie, elle aussi très intéressante !).

7. Spoiler : on pourra commencer par le cas n = d + 2, choisir un point aj ∈ Ci et ∆k =

T
i6=j
conv{aj | j 6= k}.

Ensembles convexes page 5

 30/05/2015

Nous donnons ici un aperçu de ce qu'on aurait aussi pu étudier, en se concentrant autour
des questions traitant du volume des convexes.

On commence par une conjecture, énoncée en 1965.

Conjecture 8 (Busemann-Petty). Soient C et D deux convexes centre-symétriques (i.e.

symétriques par rapport à l'origine). On suppose que pour tout hyperplan H passant par

l'origine, on a Vol(C ∩ H) ≥ Vol(D ∩ H). Alors Vol(C) ≥ Vol(D).

On voit facilement que cette conjecture est vraie pour le plan, et on peut démontrer
qu'elle le reste pour les dimensions 3 et 4. Par contre, un contre-exemple a été trouvé
par Ball en 1986, tout simple : il concerne l'hypercube.
√
Théorème 9 (Ball). Pour tout hyperplan H de E, on a Vol(B∞ (0, 1) ∩ H) ≤ 2, avec

égalité si et seulement si H = u⊥ , où u et un vecteur ayant d − 2 coordonnées nulles et

les deux restantes égales.

À partir de la dimension 10, ce théorème fournit un contre-exemple à la conjecture,

en prenant pour C une boule euclidienne et D l'hypercube B∞ (0, 1) : si on note β(d) le
volume de la boule unité de dimension d, alors

πk 22k+1 π k k!
β(2k) = et β(2k + 1) = .
k! (2k + 1)!

On peut aussi montrer (mais avec d'autres méthodes) que la conjecture 8 est fausse à
partir de la dimension 5.

Citons aussi le résultat suivant :

Théorème 10 (John-Loewner). Soit A un borné de E d'intérieur non vide. On considère

l'ensemble des ellipsoïdes de E centrées en l'origine et contenant A. Alors il en existe un

de volume minimal, et celui-ci est unique ; on l'appelle ellipsoïde de John-Loewner de A.

Ce théorème possède de nombreuses applications ; on peut par exemple en déduire que

√
pour tout convexe centre-symétrique C , il existe un ellipsoïde E tel que E⊂C⊂ DE .
Il sert aussi à montrer que tout sous-groupe compact du groupe linéaire est conjugué à
un groupe d'isométries linéaires.

Enn, on n'a pas du tout parlé de l'addition de Minkowski : la somme de Minkowski

de deux ensembles convexes C et D est dénie simplement par C + D = {c + d | c ∈
C, d ∈ D}. On a deux résultats principaux concernant le volume de la somme. Tout
d'abord l'inégalité de Brunn-Minkowski :

Vol(C + D)1/d ≥ Vol(C)1/d + Vol(D)1/d ;

et ensuite la formule de Steiner-Minkowski : pour tout convexe C, il existe des nombres

(Vi (C))0≤i≤d tels que
d
X
Vol(C + B(0, ε)) = Vi (C)εi .
i=0

Ensembles convexes page 6