Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
** Exercice V.4. Soit C := {x ∈ R n | Ax b, x 0}, où A ∈ M m,n (R), et
˜
C := {(x, u) ∈ R
n
× R
m
| Ax + u = b, x 0, u 0} .
Il y a ainsi une correspondance entre les points x de C et les points ˜
x =
(x, u = b − Ax) de ˜
C.
Montrer l’équivalence suivante :
(x est extrémal dans C) ⇔
(x, u = b − Ax) est extrémal dans ˜
C
.
Solution : Considérons x extrémal dans C. Posons u = b − Ax, de sorte que
(x, u) soit le point de ˜
C correspondant à x. Montrons que (x, u) est extrémal
dans ˜
C.
On va pour cela raisonner par l’absurde : en supposant que (x, u) n’est pas
extrémal dans ˜
C, on va être conduit à une contradiction.
Si (x, u) n’est pas extrémal dans ˜
C, il existe α ∈ ]0, 1[ , (x 1 , u 1 ) et (x 2 , u 2 )
dans ˜
C, (x 1 , u 1 ) = (x 2 , u 2 ), tels que
(x, u) = α (x 1 , u 1 ) + (1 − α) (x 2 , u 2 ) .
Cette dernière relation induit entre autres
x = αx 1 + (1 − α) x 2 ,
ce qui, en raison du caractère extrémal de x dans C, n’est possible que si
x 1 = x 2 .
Mais alors u 1 = b − Ax 1 = b − Ax 2 = u 2 , d’où (x 1 , u 1 ) = (x 2 , u 2 ), ce qui
est contraire à l’une des propriétés de départ de (x 1 , u 1 ) et (x 2 , u 2 ) .
Donc (x, u) est bien extrémal dans ˜
C.
Réciproquement, soit (x, u) extrémal dans ˜
C et montrons que x est nécessairement extrémal dans C.
Raisonnons à nouveau par l’absurde. Supposons que x ne soit pas extrémal dans C : il existe α ∈ ]0, 1[ , x 1 et x 2 dans C, x 1 = x 2 , tels que
x = αx 1 + (1 − α) x 2 .
Mais alors, puisque u = b − Ax,
(x, u) = α (x 1 , b − Ax 1 ) + (1 − α) (x 2 , b − Ax 2 )
= αz 1 + (1 − α) z 2,
où z 1 et z 2 ∈ ˜
C, z 1 = z 2 . Ceci contredit le caractère extrémal de (x, u) dans ˜
C.
Donc x est bien extrémal dans C.
178