IV.3. Premiers pas dans la théorie de la dualité
b) – Le lagrangien usuel L pour le problème (P) est
(x, λ) ∈ R
n
× R
m
−→ L(x, λ) = f (x) +
m
i=1
λ i h i (x),
c’est-à-dire la fonction-limite lim
r→0
L r (x, λ). En fait,
L r = L +
r
2
m
i=1
h
2
i
est la somme du lagrangien usuel et d’un terme positif d’« augmentation » ou
de « pénalisation extérieure » mesurant d’une certaine manière la violation des
contraintes du problème.
– La fonction duale dérivée de L r est
Θ r := λ ∈ R
m
−→ Θ r (λ) := inf
x∈R n
L r (x, λ),
d’où le problème dual correspondant :
(D r )
Max Θ r (λ)
λ ∈ R m .
2 ◦ ) a) Par définition,
ˆ
L r (x, y, λ) = f (x) +
r
2
p
j=1
[g j (x) + y
2
j ]
2 +
p
j=1
λ j [g j (x) + y
2
j ]
= f (x) +
p
j=1
r
2
y
4
j + [λ j + rg j (x)]y
2
j + λ j g j (x) +
r
2
g j (x)
2
.
La structure « séparée » de ˆ
L r (x, y, λ) en les variables y j facilite la minimisation de ˆ
L r (x, ·, λ) sur R p . En posant u := y 2
j , on est en fait réduit à la
minimisation de la fonction quadratique convexe u −→
r
2 u 2 + [λ j + rg j (x)]u +
λ j g j (x) +
r
2 g j (x) 2 sur R + . Deux cas sont alors à envisager :
• g j (x) −
λ j
r , auquel cas la fonction en question est minimisée en
u = −
λ j +rg j (x)
r
;
• g j (x) > −
λ j
r , auquel cas la fonction en question est minimisée en u = 0.
En somme, u = max
0, −
λ j +rg j (x)
r
.
Par suite, g j (x) + u = max
g j (x), −
λ j
r
et
161