IV.3. Premiers pas dans la théorie de la dualité
** Exercice IV.6. Étant donnés r 1 , . . . , r n des réels tous strictement positifs,
A ∈ M m,n (R) et c ∈ R m , on considère le problème de minimisation suivant :
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser
n
i=1
x i ln
x i
r i
sous les contraintes x ∈ Λ n et Ax c.
Dans cette formulation, Λ n désigne le simplexe-unité de R n , et α ln(α) est
prise égale à 0 pour α = 0.
Soient (x, μ) ∈ Λ n × (R + )
m −→ L (x, μ) =
n
i=1
x i ln
x i
r i
+ μ, Ax − c le
lagrangien dans le problème (P) et
μ ∈
R
+
m −→ ψ (μ) = inf
x∈Λn
L (x, μ)
la fonction duale associée.
Déterminer la forme explicite de ψ et formuler (le plus simplement possible)
le problème dual (D) de (P).
Solution : Pour déterminer ψ (μ) , μ ∈ (R + )
m , on a à minimiser L (·, μ) sur
Λ n . En raison de la compacité de Λ n , de la continuité de L (·, μ) sur Λ n et de
la stricte convexité de L (·, μ), il existe un et un seul x (μ) minimisant L (·, μ)
sur Λ n . Un tel x (μ), s’il est dans l’intérieur relatif de Λ n (i.e. vérifie x (μ) i > 0
pour tout i), est caractérisé par la propriété :
∃ λ ∈ R
n tel que ∇ x L (x (μ) , μ) + λ (1, . . . , 1)
= 0.
(4.1)
Cette condition se détaille en
ln
x (μ) i
r i
+ 1 +
A
μ
i
+ λ = 0 pour tout i = 1, . . . , n.
Sachant que
n
i=1
x (μ) i = 1, cela conduit à
x (μ) i =
r i e
−(A μ) i
n
i=1
r i e
−(A μ) i
·
Cet x (μ) vérifie (4.1) et est donc bien l’unique minimum de L (·, μ) sur Λ n .
139
** Exercice IV.6. Étant donnés r 1 , . . . , r n des réels tous strictement positifs,
A ∈ M m,n (R) et c ∈ R m , on considère le problème de minimisation suivant :
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser
n
i=1
x i ln
x i
r i
sous les contraintes x ∈ Λ n et Ax c.
Dans cette formulation, Λ n désigne le simplexe-unité de R n , et α ln(α) est
prise égale à 0 pour α = 0.
Soient (x, μ) ∈ Λ n × (R + )
m −→ L (x, μ) =
n
i=1
x i ln
x i
r i
+ μ, Ax − c le
lagrangien dans le problème (P) et
μ ∈
R
+
m −→ ψ (μ) = inf
x∈Λn
L (x, μ)
la fonction duale associée.
Déterminer la forme explicite de ψ et formuler (le plus simplement possible)
le problème dual (D) de (P).
Solution : Pour déterminer ψ (μ) , μ ∈ (R + )
m , on a à minimiser L (·, μ) sur
Λ n . En raison de la compacité de Λ n , de la continuité de L (·, μ) sur Λ n et de
la stricte convexité de L (·, μ), il existe un et un seul x (μ) minimisant L (·, μ)
sur Λ n . Un tel x (μ), s’il est dans l’intérieur relatif de Λ n (i.e. vérifie x (μ) i > 0
pour tout i), est caractérisé par la propriété :
∃ λ ∈ R
n tel que ∇ x L (x (μ) , μ) + λ (1, . . . , 1)
= 0.
(4.1)
Cette condition se détaille en
ln
x (μ) i
r i
+ 1 +
A
μ
i
+ λ = 0 pour tout i = 1, . . . , n.
Sachant que
n
i=1
x (μ) i = 1, cela conduit à
x (μ) i =
r i e
−(A μ) i
n
i=1
r i e
−(A μ) i
·
Cet x (μ) vérifie (4.1) et est donc bien l’unique minimum de L (·, μ) sur Λ n .
139