IV.3. Premiers pas dans la théorie de la dualité
Par suite g(z t ) > 0. On a donc z t arbitrairement proche de x en lequel la
valeur prise par g est strictement positive. Ceci contredit l’hypothèse de départ
selon laquelle x est à l’intérieur de {x ∈ R n | g(x) 0} .
En définitive
◦
C = {x ∈ R
n
| g j (x) < 0 pour tout j = 1, . . . , p} ,
et donc
fr C = {x ∈ C | ∃ j tel que g j (x) = 0}
(qui est aussi fr
◦
C car C est un convexe d’intérieur non vide).
b) (P) est un problème de minimisation convexe. La fonction-objectif f
étant continue et l’ensemble-contrainte C compact, le problème (P) a bien des
solutions. Tout ceci conduit à affirmer que l’ensemble S des solutions de (P)
est un convexe compact non vide de C.
La condition (de qualification des contraintes) de Slater étant vérifiée pour
(P) (cela figure parmi les hypothèses du problème), l’ensemble M des multiplicateurs de Lagrange-KKT est donc un convexe compact non vide de (R + )
p
(à tout x ∈ S est associé le même ensemble de multiplicateurs M ).
La fonction duale
ψ : μ ∈
R
+
p −→ ψ (μ) = inf
x∈R n
⎛
⎝ f (x) +
p
j=1
μ j g j (x)
⎞
⎠
est concave semi-continue supérieurement, et on sait que les points maximisant
ψ sur (R + )
p sont exactement ceux de M.
2 ◦ ) a) La fonction g j :
◦
C −→ R −
∗ est convexe et différentiable ; la fonction
y ∈ R −
∗ −→ − ln(−y) est convexe, croissante et différentiable. Il s’ensuit que la
composée des deux, qui n’est autre que x ∈
◦
C −→ − ln(−g j (x)), est convexe
et différentiable sur
◦
C .
Par suite, ϕ α est convexe et différentiable sur
◦
C.
b) f est bornée inférieurement sur C, − ln(−g j (x)) → +∞ quand g j (x) →
0 − . Il s’ensuit
ϕ α (x) → +∞ quand x ∈
◦
C → ˜
x ∈ fr C.
Par conséquent tous les ingrédients sont là pour qu’il existe x α minimisant
ϕ α sur
◦
C . Ces points x α sont caractérisés par :
x α ∈
◦
C et ∇f (x α ) +
p
j=1
−1
αg j (x α )
∇g j (x α ) = 0.
(4.4)
157
Par suite g(z t ) > 0. On a donc z t arbitrairement proche de x en lequel la
valeur prise par g est strictement positive. Ceci contredit l’hypothèse de départ
selon laquelle x est à l’intérieur de {x ∈ R n | g(x) 0} .
En définitive
◦
C = {x ∈ R
n
| g j (x) < 0 pour tout j = 1, . . . , p} ,
et donc
fr C = {x ∈ C | ∃ j tel que g j (x) = 0}
(qui est aussi fr
◦
C car C est un convexe d’intérieur non vide).
b) (P) est un problème de minimisation convexe. La fonction-objectif f
étant continue et l’ensemble-contrainte C compact, le problème (P) a bien des
solutions. Tout ceci conduit à affirmer que l’ensemble S des solutions de (P)
est un convexe compact non vide de C.
La condition (de qualification des contraintes) de Slater étant vérifiée pour
(P) (cela figure parmi les hypothèses du problème), l’ensemble M des multiplicateurs de Lagrange-KKT est donc un convexe compact non vide de (R + )
p
(à tout x ∈ S est associé le même ensemble de multiplicateurs M ).
La fonction duale
ψ : μ ∈
R
+
p −→ ψ (μ) = inf
x∈R n
⎛
⎝ f (x) +
p
j=1
μ j g j (x)
⎞
⎠
est concave semi-continue supérieurement, et on sait que les points maximisant
ψ sur (R + )
p sont exactement ceux de M.
2 ◦ ) a) La fonction g j :
◦
C −→ R −
∗ est convexe et différentiable ; la fonction
y ∈ R −
∗ −→ − ln(−y) est convexe, croissante et différentiable. Il s’ensuit que la
composée des deux, qui n’est autre que x ∈
◦
C −→ − ln(−g j (x)), est convexe
et différentiable sur
◦
C .
Par suite, ϕ α est convexe et différentiable sur
◦
C.
b) f est bornée inférieurement sur C, − ln(−g j (x)) → +∞ quand g j (x) →
0 − . Il s’ensuit
ϕ α (x) → +∞ quand x ∈
◦
C → ˜
x ∈ fr C.
Par conséquent tous les ingrédients sont là pour qu’il existe x α minimisant
ϕ α sur
◦
C . Ces points x α sont caractérisés par :
x α ∈
◦
C et ∇f (x α ) +
p
j=1
−1
αg j (x α )
∇g j (x α ) = 0.
(4.4)
157