Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
– si x est un point extrémal non-dégénéré de C et si x 1 , . . . , x n sont
ses points extrémaux adjacents, alors C est contenu dans le cône convexe
polyédral de sommet x et de génératrices x 1 − x, . . . , x n − x (c’est-à-dire
x + cône{x 1 − x, . . . , x n − x}).
** Exercice V.7. Soit C un polyèdre convexe fermé de R n .
1 ◦ ) On suppose ici que C est borné ; plus précisément on a
C = conv {v 1 , . . . , v k } .
Montrer qu’un point extrémal de C est nécessairement l’un des v i .
2 ◦ ) On suppose C décrit de la manière suivante :
C = C 0 + K,
(5.21)
où C 0 est un polyèdre convexe compact et K un cône convexe fermé polyédrique.
a) Montrer que tout point extrémal de C est nécessairement dans C 0 et qu’il
est aussi extrémal dans C 0 .
b) Donner un exemple de C décrit comme en (5.21) mais sans point extrémal.
Quelle condition portant sur C (ou sur K) assurerait que C a effectivement
des points extrémaux ?
Solution : 1 ◦ ) Soit x un point extrémal de C. Si x n’est pas l’un des v i , il y
a l vecteurs v i , 2 l k, tels que :
x =
l
i=1
α i v i , 0 < α i < 1 pour tout i et
l
i=1
α i = 1.
Il s’ensuit
x = α i 0 v i 0 + (1 − α i 0 )
i = i 0
α i
1 − α i 0
v i ,
et, par conséquent, x n’est pas extrémal (d’accord ?).
Les points extrémaux de C figurent donc nécessairement parmi les v i (mais
tous les v i ne sont pas extrémaux dans C).
2 ◦ ) a) Soit x ∈ C, x = c 0 + d avec c 0 ∈ C 0 et d ∈ K. Si d = 0, x ne saurait
être extrémal dans C ; en effet
c 0 + d =
1
2
c 0 +
1
2
(c 0 + 2d) ,
où c 0 ∈ C, c 0 + 2d ∈ C 0 + 2K = C 0 + K = C et c 0 = c 0 + 2d.
182
– si x est un point extrémal non-dégénéré de C et si x 1 , . . . , x n sont
ses points extrémaux adjacents, alors C est contenu dans le cône convexe
polyédral de sommet x et de génératrices x 1 − x, . . . , x n − x (c’est-à-dire
x + cône{x 1 − x, . . . , x n − x}).
** Exercice V.7. Soit C un polyèdre convexe fermé de R n .
1 ◦ ) On suppose ici que C est borné ; plus précisément on a
C = conv {v 1 , . . . , v k } .
Montrer qu’un point extrémal de C est nécessairement l’un des v i .
2 ◦ ) On suppose C décrit de la manière suivante :
C = C 0 + K,
(5.21)
où C 0 est un polyèdre convexe compact et K un cône convexe fermé polyédrique.
a) Montrer que tout point extrémal de C est nécessairement dans C 0 et qu’il
est aussi extrémal dans C 0 .
b) Donner un exemple de C décrit comme en (5.21) mais sans point extrémal.
Quelle condition portant sur C (ou sur K) assurerait que C a effectivement
des points extrémaux ?
Solution : 1 ◦ ) Soit x un point extrémal de C. Si x n’est pas l’un des v i , il y
a l vecteurs v i , 2 l k, tels que :
x =
l
i=1
α i v i , 0 < α i < 1 pour tout i et
l
i=1
α i = 1.
Il s’ensuit
x = α i 0 v i 0 + (1 − α i 0 )
i = i 0
α i
1 − α i 0
v i ,
et, par conséquent, x n’est pas extrémal (d’accord ?).
Les points extrémaux de C figurent donc nécessairement parmi les v i (mais
tous les v i ne sont pas extrémaux dans C).
2 ◦ ) a) Soit x ∈ C, x = c 0 + d avec c 0 ∈ C 0 et d ∈ K. Si d = 0, x ne saurait
être extrémal dans C ; en effet
c 0 + d =
1
2
c 0 +
1
2
(c 0 + 2d) ,
où c 0 ∈ C, c 0 + 2d ∈ C 0 + 2K = C 0 + K = C et c 0 = c 0 + 2d.
182