Chapitre IV. Mini-maximisation. Dualisation de problèmes...
la fonction duale usuelle associée au problème de minimisation (P), et pour
tout α > 0 soit
ϕ α : x ∈
◦
C −→ ϕ α (x) := f (x) −
1
α
p
j=1
ln (−g j (x)) .
a) Vérifier que ϕ α est convexe et différentiable sur
◦
C.
b) Montrer qu’il existe des points de
◦
C minimisant ϕ α sur
◦
C .
c) Soit x α un minimum de ϕ α sur
◦
C et on désigne par μ α le vecteur de (R + )
p
dont les composantes sont
−1
αg j (x α )
.
– Montrer que x α minimise x −→ f (x) +
p
j=1
μ α
j g j (x) sur R n .
– Vérifier que la fonction duale ψ prend une valeur finie en μ α .
– Établir l’encadrement suivant
f (x α ) f f (x α ) −
p
α
,
où f désigne la valeur minimale dans (P).
d) Commenter la pertinence de l’approche proposée dans cet exercice pour
résoudre le problème originel (P).
Solution : 1 ◦ ) a) Il est clair que C = {x ∈ R n | g(x) 0} , où on a posé
g := max j g j . La fonction g est convexe, mais pas différentiable en général.
De par la continuité de g, on a :
(g(x) < 0) ⇒
x ∈
◦
C
(la convexité de g n’est pas essentielle ici).
Soit à présent x à l’intérieur de C et montrons que g(x) < 0 nécessairement.
Supposons g(x) = 0 et montrons que cela conduit à une contradiction.
Pour t ∈ ]0, 1[, posons y t := x − t(x − x 0 ) et z t := x + t(x − x 0 ), où x 0 est
un point en lequel g j (x 0 ) < 0 pour tout j = 1, . . . , p (et dont l’existence figure
en hypothèse).
Comme x =
1
2
(y t + z t ) et que g est
convexe,
0 = g(x)
1
2
g(y t ) +
1
2
g(z t ).
Toujours en raison de la convexité de g,
g(y t ) (1 − t) g(x) + tg(x 0 ) < 0.
156
la fonction duale usuelle associée au problème de minimisation (P), et pour
tout α > 0 soit
ϕ α : x ∈
◦
C −→ ϕ α (x) := f (x) −
1
α
p
j=1
ln (−g j (x)) .
a) Vérifier que ϕ α est convexe et différentiable sur
◦
C.
b) Montrer qu’il existe des points de
◦
C minimisant ϕ α sur
◦
C .
c) Soit x α un minimum de ϕ α sur
◦
C et on désigne par μ α le vecteur de (R + )
p
dont les composantes sont
−1
αg j (x α )
.
– Montrer que x α minimise x −→ f (x) +
p
j=1
μ α
j g j (x) sur R n .
– Vérifier que la fonction duale ψ prend une valeur finie en μ α .
– Établir l’encadrement suivant
f (x α ) f f (x α ) −
p
α
,
où f désigne la valeur minimale dans (P).
d) Commenter la pertinence de l’approche proposée dans cet exercice pour
résoudre le problème originel (P).
Solution : 1 ◦ ) a) Il est clair que C = {x ∈ R n | g(x) 0} , où on a posé
g := max j g j . La fonction g est convexe, mais pas différentiable en général.
De par la continuité de g, on a :
(g(x) < 0) ⇒
x ∈
◦
C
(la convexité de g n’est pas essentielle ici).
Soit à présent x à l’intérieur de C et montrons que g(x) < 0 nécessairement.
Supposons g(x) = 0 et montrons que cela conduit à une contradiction.
Pour t ∈ ]0, 1[, posons y t := x − t(x − x 0 ) et z t := x + t(x − x 0 ), où x 0 est
un point en lequel g j (x 0 ) < 0 pour tout j = 1, . . . , p (et dont l’existence figure
en hypothèse).
Comme x =
1
2
(y t + z t ) et que g est
convexe,
0 = g(x)
1
2
g(y t ) +
1
2
g(z t ).
Toujours en raison de la convexité de g,
g(y t ) (1 − t) g(x) + tg(x 0 ) < 0.
156