IV.3. Premiers pas dans la théorie de la dualité
et la fonction duale ψ associée, i.e. :
∀λ ∈ R, ψ (λ) = inf
x∈(R + )
n
L(x, λ)
(dualisation de la contrainte du type égalité seulement).
a) Vérifier que ψ (λ) = −∞ si λ < 0, et que pour tout λ > 0 il existe un et
un seul x (λ) minimisant L(·, λ) sur (R + )
n .
En utilisant la caractérisation de x (λ) fournie par les conditions nécessaires
et suffisantes d’optimalité, montrer :
∀ λ 0, ψ (λ) = −
n
i=1
a i
1 −
λ
a i b i
+
+ λ
n
i=1
1
b i
ln
a i b i
λ
+
− 1
.
b) En étudiant les propriétés de ψ sur R + (notamment sa dérivabilité) montrer qu’il existe un et un seul λ > 0 maximisant ψ sur R + .
Exprimer alors les coordonnées x i de la solution de (P) en fonction de λ et
a 1 , . . . , a n , b 1 , . . . , b n .
Solution : 1 ◦ ) a) L’ensemble-contrainte est compact et f est continue : le
problème de minimisation (P) a donc des solutions.
b) Les contraintes du type égalité ou inégalité sont exprimées à l’aide de
fonctions affines ; il n’y a donc pas d’hypothèse de qualification des contraintes
qu’il faudrait vérifier. Ainsi, toute solution de (P) vérifie nécessairement les
conditions de minimalité du 1 er ordre de Karush-Kuhn-Tucker.
c) Puisque ∇f (x) =
f
1 (x 1 ) , . . . , f
n (x n )
et que la fonction
h : x = (x 1 , . . . , x n ) −→ h(x) :=
n
i=1
x i − 1 définissant la contrainte de type
égalité a un gradient constant (1, . . . , 1)
, nous avons le résultat suivant : si x
est une solution de (P), il existe (μ 1 , . . . , μ n ) ∈ (R + )
n et λ ∈ R tels que
(KKT )
f
i (x i ) − μ i + λ = 0
μ i x i = 0
pour tout i = 1, . . . , n.
Si i est tel que x i > 0 (il y a nécessairement de tels i), μ i = 0 de sorte que
f
i (x i ) + λ = 0.
Si i est tel que x i = 0,
f
i (x i ) + λ = μ i 0.
D’où le résultat escompté.
141
et la fonction duale ψ associée, i.e. :
∀λ ∈ R, ψ (λ) = inf
x∈(R + )
n
L(x, λ)
(dualisation de la contrainte du type égalité seulement).
a) Vérifier que ψ (λ) = −∞ si λ < 0, et que pour tout λ > 0 il existe un et
un seul x (λ) minimisant L(·, λ) sur (R + )
n .
En utilisant la caractérisation de x (λ) fournie par les conditions nécessaires
et suffisantes d’optimalité, montrer :
∀ λ 0, ψ (λ) = −
n
i=1
a i
1 −
λ
a i b i
+
+ λ
n
i=1
1
b i
ln
a i b i
λ
+
− 1
.
b) En étudiant les propriétés de ψ sur R + (notamment sa dérivabilité) montrer qu’il existe un et un seul λ > 0 maximisant ψ sur R + .
Exprimer alors les coordonnées x i de la solution de (P) en fonction de λ et
a 1 , . . . , a n , b 1 , . . . , b n .
Solution : 1 ◦ ) a) L’ensemble-contrainte est compact et f est continue : le
problème de minimisation (P) a donc des solutions.
b) Les contraintes du type égalité ou inégalité sont exprimées à l’aide de
fonctions affines ; il n’y a donc pas d’hypothèse de qualification des contraintes
qu’il faudrait vérifier. Ainsi, toute solution de (P) vérifie nécessairement les
conditions de minimalité du 1 er ordre de Karush-Kuhn-Tucker.
c) Puisque ∇f (x) =
f
1 (x 1 ) , . . . , f
n (x n )
et que la fonction
h : x = (x 1 , . . . , x n ) −→ h(x) :=
n
i=1
x i − 1 définissant la contrainte de type
égalité a un gradient constant (1, . . . , 1)
, nous avons le résultat suivant : si x
est une solution de (P), il existe (μ 1 , . . . , μ n ) ∈ (R + )
n et λ ∈ R tels que
(KKT )
f
i (x i ) − μ i + λ = 0
μ i x i = 0
pour tout i = 1, . . . , n.
Si i est tel que x i > 0 (il y a nécessairement de tels i), μ i = 0 de sorte que
f
i (x i ) + λ = 0.
Si i est tel que x i = 0,
f
i (x i ) + λ = μ i 0.
D’où le résultat escompté.
141