Chapitre IV. Mini-maximisation. Dualisation de problèmes...
2 ◦ ) (i) Formuler le problème dual (D) de (P).
(ii) Comment caractériser une solution μ de (D) ?
(iii) Donner une condition suffisante pour que (D) ait une solution unique.
(iv) Comment une solution μ de (D) permettrait-elle de retrouver la solution
de (P) ?
Solution : f est une fonction (quadratique) fortement convexe, l’ensemble
C := {x ∈ R n | Ax + b 0} défini par la conjonction des contraintes a j , x +
b j 0 pour j = 1, . . . , m (inégalités définies par des fonctions affines) est
un convexe fermé. Donc, si C = ∅, (P) a une et une seule solution x. Les
contraintes étant qualifiées (puisque les fonctions les définissant sont affines),
x est caractérisée par :
∃ μ = (μ 1 , . . . , μ m ) ∈
R
+
m tel que
⎧
⎪ ⎨
⎪ ⎩
M x + q + A μ = 0,
(1)
μ, Ax + b = 0
(2)
μ j = 0 si a j , x + b j < 0
.
1 ◦ ) Θ (μ) est par définition inf x∈R n L(x, μ).
À μ fixé, le minimum de L(·, μ) sur R n est atteint en x (μ) =
−M −1
q + A μ
.
D’où :
Θ (μ) = −
1
2
M
−1
A
μ + q
, A
μ + q
+ b, μ
= −
1
2
AM
−1 A
μ, μ
+
b − AM
−1 q, μ
−
1
2
M
−1 q, q
.
2 ◦ ) (i) Le problème dual (D) de (P) est :
(D)
Maximiser Θ (μ)
sous la contrainte μ ∈ (R + )
m .
On sait que ce problème de maximisation d’une fonction quadratique
concave sur (R + )
m a des solutions (ce qui ne se voit pas directement puisque
AM −1 A est certes semi-définie positive, mais pas nécessairement définie positive).
(ii) Une solution μ de (D) est caractérisée par :
μ ∈
R
+
m et ∇Θ (μ) est normal à
R
+
m en μ ;
150