Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
*** Exercice V.6. Soit A ∈ M m,n (R), b ∈ R m , et C le polyèdre convexe fermé
de R n décrit comme suit
C := {x ∈ R
n
| Ax b} .
On suppose : m n, aucun des vecteurs-lignes a i de A n’est nul.
Pour toute partie non vide I de {1, . . . , m} (de cardinal k par exemple), on
note :
– A I la matrice extraite de A en ne conservant que les lignes de numéro i ∈ I
(ainsi A I ∈ M k,n (R)) ;
– b I le vecteur extrait de b en ne conservant que les coordonnées de numéro
i ∈ I (ainsi b I ∈ R k ).
Soit x un point-frontière de C ; on désigne par I (x) l’ensemble des indices
i ∈ {1, . . . , m} correspondant aux contraintes-inégalités actives en x, c’est-à-dire
I (x) = {i | |a i , x = b i } .
Montrer que x est un point extrémal de C si et seulement si le rang de A I(x)
est égal à n.
Solution : De par la structure de C on a :
◦
C = {x ∈ R
n
| |a i , x < b i pour tout i = 1, . . . , m} ;
frC =
x ∈ C | max
i=1,...,m
{{a i , x − b i } = 0
= {x ∈ C | I(x) = ∅} .
Soient x ∈ fr C et A I(x) la matrice extraite de A correspondante. Le rang
de A I(x) est un entier compris entre 1 et min (n, card I (x)) . On se propose de
montrer que x est un point extrémal de C si et seulement si le rang de A I(x)
est exactement n.
–
rang de A I(x) = n
⇒ (x est un point extrémal de C)
.
Supposons A I(x) de rang n et supposons que x ne soit pas extrémal dans C.
Il existe alors y et z dans C, y = z, et α ∈ ]0, 1[ tels que x = αy+(1 − α) z.
Prenons i ∈ I (x) ; on a :
a i , x = b i , a i , y b i , a i , z b i .
Mais alors a i , y − b i = a i , z − b i = 0 nécessairement. Nous avons démontré que I (x) ⊂ I(y) ∩ I(z).
180