Chapitre IV. Mini-maximisation. Dualisation de problèmes...
2 ◦ ) Soit
L : (x, μ) ∈ R
n
× R
m
−→ L(x, μ) = f (x) +
m
j=1
μ j g j (x)
le lagrangien usuel dans (P), et
μ ∈
R
+
m −→ ψ (μ) = inf
x∈R n
L(x, μ)
la fonction duale associée.
Pour μ ∈ (R + )
m on pose
A (μ) := A 0 + μ 1 A 1 + . . . + μ m A m
b (μ) := b 0 + μ 1 b 1 + . . . + μ m b m
c (μ) := c 0 + μ 1 c 1 + . . . + μ m c m .
Déterminer l’expression de ψ (μ) en fonction de A (μ) , b (μ) et c (μ), et
formuler (le plus simplement possible) le problème dual (D) de (P).
Solution : 1 ◦ ) La fonction-objectif f est (quadratique) strictement convexe,
les fonctions g j définissant les contraintes du type inégalité sont (quadratiques)
convexes. Donc, si l’ensemble-contrainte n’est pas vide, le problème de minimisation convexe (P) a une et une seule solution.
2 ◦ ) On a
ψ (μ) = inf
x∈R n
1
2
A (μ) x, x + b (μ) , x + c (μ)
.
A (μ) est symétrique définie positive pour tout μ ∈ (R + )
m . La solution du
problème de minimisation de L(·, μ) sur R n est
x (μ) = − [A (μ)]
−1 b (μ) ,
d’où
ψ (μ) = −
1
2
[A (μ)]
−1 b (μ) , b (μ)
+ c (μ) .
Le problème dual (D) de (P) consiste à maximiser la fonction (concave) ψ
sur (R + )
m .
152