IV.3. Premiers pas dans la théorie de la dualité
2 ◦ ) Étant donné y ∈ Y , on considère le problème de minimisation suivant
(P y )
Minimiser l(x, y)
x ∈ X.
Résoudre complètement (P y ).
3 ◦ ) On suppose que 0 /
∈ X. Déduire de ce qui précède :
• min x∈X x = max y1
a, y −
A −1 y, y
;
• le maximum dans l’expression de droite ci-dessus est atteint en y =
x
x
,
où x désigne la projection de 0 sur X.
Solution : 1 ◦ ) a) X et Y sont des convexes compacts non vides de R n , la
fonction l est convexe-concave sur R n × R n ; par conséquent il y a bien des
points-selles de l sur X × Y.
b) Soit (x, y) un point-selle de l sur X × Y. Alors :
(∗) l(x, y) = min
x∈X
max
y∈Y
l(x, y)
= max
y∈Y
min
x∈X
l(x, y)
;
(∗∗) x minimise la fonction ϕ(x) := max y∈Y l(x, y) sur X
et
y maximise la fonction ψ(y) := min
x∈X
l(x, y) sur Y.
Ici ϕ(x) = max y1 x, y n’est autre que x ; par suite x est le point
de X minimisant la fonction x sur X, c’est-à-dire la projection de l’origine
sur X.
La valeur-selle de l sur X × Y est x , c’est-à-dire la distance de l’origine
à X.
Par suite x, y = x , ce qui conduit à :
y =
x
x
si x = 0, c’est-à-dire lorsque 0 /
∈ X;
y élément quelconque de Y lorsque 0 ∈ X.
2 ◦ ) L’ensemble-contrainte du problème de minimisation (P y ) est décrit sous
la forme g(x) 0 où g : x −→ g(x) := A(x − a), x − a − 1. La fonction g est convexe différentiable (quadratique même) et il existe x 0 tel que
g(x 0 ) < 0 (x 0 = a par exemple). La fonction-objectif dans (P y ) est linéaire,
ce qui fait que, lorsque y = 0, les solutions x y de ( P y ) sont forcément sur la
frontière de X (d’accord ?).
133