Chapitre I. Révision de bases : calcul différentiel...
B – Lagrangien et lagrangien augmenté :
Étant donné r 0, on définit les applications L et L r de R N × R M dans R
par :
L(x, λ) := f (x) + λ, Bx (lagrangien usuel) ;
L r (x, λ) := L(x, λ) +
r
2
Bx
2 (lagrangien augmenté).
On dit que (x, λ) ∈ R N ×R M est un point-selle (ou un col) de L sur R N ×R M
lorsque :
∀(x, λ) ∈ R
N
× R
M , L(x, λ) L(x, λ) L(x, λ).
Définition analogue d’un point-selle de L r .
1 ◦ ) a) Montrer que l’on a toujours :
sup
λ∈R M
inf
x∈R N
L(x, λ)
inf
x∈R N
sup
λ∈R M
L(x, λ)
(Cette inégalité est dans R ∪ {±∞}, et sa démonstration ne fait pas appel à
l’expression particulière de L comme fonction de x et λ).
b) Soit (x, λ) un point-selle de L. Montrer :
L(x, λ) = max λ∈R M (inf x∈R N L(x, λ)) = min x∈R N (sup λ∈R M L(x, λ)) .
2 ◦ ) Soit r 0 et (x, λ) ∈ R N × R M .
a) Établir les équivalences suivantes :
L r (x, λ) L r (x, λ) pour tout λ ∈ R
M
⇔ (Bx = 0) ;
L r (x, λ) L r (x, λ) pour tout x ∈ R
N
⇔
A + rB
B
x + B
λ = b
.
b) Quelles conclusions peut-on tirer de ce qui précède concernant les liens
existant entre les points-selles de L r et la solution de (P) ?
C – Algorithme d’Arrow-Uzawa (à pas variable) :
Les données sont : r 0, λ 0 ∈ R M , (ρ n ) une suite de réels > 0. On considère
les suites (x n ) de R N , (λ n ) de R M construites de manière récurrente comme
suit :
∀n ∈ N, x n minimise L r (·, λ n ) sur R N ,
λ n+1 = λ n + ρ n Bx n .
Soit (x, λ) un point-selle de L r .
34