IV.3. Premiers pas dans la théorie de la dualité
** Exercice IV.13. Le problème dual augmenté :
1 ◦ ) Considérons le problème de minimisation (de base) suivant :
(P)
Min f (x)
h 1 (x) = 0, . . . , h m (x) = 0.
Pour r > 0 on pose f r (x) := f +
r
2
m
i=1
h 2
i et on considère la version modifiée
(P r ) de (P) ci-dessous :
(P r )
Min f r (x)
h 1 (x) = 0, . . . , h m (x) = 0.
a) Vérifier que les problèmes (P) et (P r ) sont équivalents.
b) Soit
L r : (x, λ) ∈ R
n
× R
m
−→ L r (x, λ) : = f r (x) +
m
i=1
λ i h i (x)
= f (x) +
r
2
m
i=1
[h i (x)]
2 +
m
i=1
λ i h i (x)
(4.5)
le lagrangien usuel pour le problème (P r ) ; on l’appelle lagrangien augmenté
du problème (P).
– Comparer L r et le lagrangien usuel L du problème (P).
– Écrire le problème dual (D r ) (dit augmenté) dérivé de L r .
2 ◦ ) On désire définir un lagrangien augmenté pour le problème de minimisation avec contraintes du type inégalité ci-dessous :
(Q)
Min f (x)
g 1 (x) 0, . . . , g p (x) 0.
Pour ce faire, on considère le problème ( ˆ
Q) suivant, plongement du problème
(Q) dans R n × R p :
ˆ
Q
Min f (x)
g j (x) + y 2
j = 0 pour j = 1, . . . , p.
159