Chapitre IV. Mini-maximisation. Dualisation de problèmes...
Solution : 1 ◦ ) a) L’ensemble-contrainte est un polyèdre convexe compact non
vide (le caractère borné de C se déduit par exemple de l’observation suivante :
si x = (x 1 , . . . , x n ) ∈ C, alors 0 x i 1/(min i b i )), f est continue sur C : le
problème de minimisation (P) a donc des solutions.
La fonction f est strictement convexe sur l’ouvert convexe
Ω := (]−1, +∞[)
n de R
n (car ∇
2 f (x) = diag(. . . ,
2a i
(1 + x i )
3 , . . .)
est définie positive en tout x = (x 1 , . . . , x n ) de Ω).
Par conséquent, le problème (P) a une et une seule solution.
(P) est un problème de minimisation différentiable et convexe, les
contraintes du type égalité ou inégalité sont exprimées à l’aide de fonctions
affines ; par suite, la solution de (P) est caractérisée par les conditions du 1 er
ordre de Karush-Kuhn-Tucker.
b) x = (x 1 , . . . , x n ) ∈ C est solution de (P) si et seulement si les conditions
de KKT suivantes sont vérifiées : il existe (μ 1 , . . . , μ n ) ∈ (R + )
n et λ ∈ R tels
que
(KKT )
⎧
⎨
⎩
−
a i
(1 + x i )
2 − μ i + λb 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
−
a i
(1+x i )
2 + λb i = 0.
Si i est tel que x i = 0, on a −a i + λb i = μ i 0.
D’où la caractérisation annoncée.
2 ◦ ) On considère
(x, λ) ∈ (R + )
n × R −→ L (x, λ) =
n
i=1
a i
1+x i
+ λ
n
i=1
b i x i − 1
.
a) L (·, λ) a une expression « séparée » en les coordonnées x i , ce qui fait
que sa minimisation sous contraintes « séparées » (x i 0 pour tout i) s’en
trouve facilitée.
Supposons λ < 0. Puisque x i peut être pris positif arbitrairement grand et
que b i > 0, il s’ensuit ψ (λ) = −∞.
Si λ = 0, L (x, 0) = f (x) et ψ (0) = 0.
Supposons λ > 0. La fonction L (·, λ) est continue, 0-coercive, strictement
convexe sur (R + )
n : il existe donc un et un seul point x (λ) ∈ (R + )
n minimisant
L (·, λ) sur (R + )
n . Ce point x (λ) est caractérisé par la propriété
−∇ x L (x (λ) , λ) ∈ N (R + )
n (x (λ)) ,
146
Solution : 1 ◦ ) a) L’ensemble-contrainte est un polyèdre convexe compact non
vide (le caractère borné de C se déduit par exemple de l’observation suivante :
si x = (x 1 , . . . , x n ) ∈ C, alors 0 x i 1/(min i b i )), f est continue sur C : le
problème de minimisation (P) a donc des solutions.
La fonction f est strictement convexe sur l’ouvert convexe
Ω := (]−1, +∞[)
n de R
n (car ∇
2 f (x) = diag(. . . ,
2a i
(1 + x i )
3 , . . .)
est définie positive en tout x = (x 1 , . . . , x n ) de Ω).
Par conséquent, le problème (P) a une et une seule solution.
(P) est un problème de minimisation différentiable et convexe, les
contraintes du type égalité ou inégalité sont exprimées à l’aide de fonctions
affines ; par suite, la solution de (P) est caractérisée par les conditions du 1 er
ordre de Karush-Kuhn-Tucker.
b) x = (x 1 , . . . , x n ) ∈ C est solution de (P) si et seulement si les conditions
de KKT suivantes sont vérifiées : il existe (μ 1 , . . . , μ n ) ∈ (R + )
n et λ ∈ R tels
que
(KKT )
⎧
⎨
⎩
−
a i
(1 + x i )
2 − μ i + λb 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
−
a i
(1+x i )
2 + λb i = 0.
Si i est tel que x i = 0, on a −a i + λb i = μ i 0.
D’où la caractérisation annoncée.
2 ◦ ) On considère
(x, λ) ∈ (R + )
n × R −→ L (x, λ) =
n
i=1
a i
1+x i
+ λ
n
i=1
b i x i − 1
.
a) L (·, λ) a une expression « séparée » en les coordonnées x i , ce qui fait
que sa minimisation sous contraintes « séparées » (x i 0 pour tout i) s’en
trouve facilitée.
Supposons λ < 0. Puisque x i peut être pris positif arbitrairement grand et
que b i > 0, il s’ensuit ψ (λ) = −∞.
Si λ = 0, L (x, 0) = f (x) et ψ (0) = 0.
Supposons λ > 0. La fonction L (·, λ) est continue, 0-coercive, strictement
convexe sur (R + )
n : il existe donc un et un seul point x (λ) ∈ (R + )
n minimisant
L (·, λ) sur (R + )
n . Ce point x (λ) est caractérisé par la propriété
−∇ x L (x (λ) , λ) ∈ N (R + )
n (x (λ)) ,
146