Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
On suppose que les ensembles-contraintes de (P) et de (D) ne sont pas vides
(hypothèse qui sera renforcée par la suite) et que A est de rang m.
1 ◦ ) Vérifier que si x est admissible pour (P) et si (y, u) est admissible
pour ( ˜
D), alors :
x, u 0,
et
(x, u = 0) ⇔ (x est solution de (P) et (y, u) est solution de ( ˜
D)).
En déduire la caractérisation suivante des solutions de (P) et de ( ˜
D) :
⎛
⎜
⎝
x est solution de (P)
et
(y, u) est solution de ( ˜
D)
⎞
⎟
⎠ ⇔
⎛
⎜
⎝
Ax = b, x 0
A y + u = c, u 0
x, u = 0
⎞
⎟
⎠ .
(SO)
Désignons par C l’association des ensembles-contraintes de (P) et de ( ˜
D), i.e.
C :=
(x, y, u) ∈ R
n
× R
m
× R
n
| Ax = b, x 0, A
y + u = c, u 0
,
et par (P ˜
D) le couplage des problèmes (P) et ( ˜
D) suivant :
(P ˜
D)
Minimiser x, u
(x, y, u) ∈ C
(appelé problème primal-dual ).
Pour toute la suite on fait les hypothèses que voici : A est de rang m et il existe
(x, y, u) ∈ C tel que x > 0 et u > 0 (v > 0 dans R n signifie que toutes les
composantes v i de v sont > 0).
Étant donné σ > 0, on propose une approximation de (P ˜
D) par pénalisation
intérieure (ou addition d’une fonction-barrière) définie comme suit :
(P ˜
D) σ
Minimiser f σ (x, y, u)
(x, y, u) ∈ C 0 ,
où C 0 := {(x, y, u) ∈ C | x > 0 et u > 0} et f σ : (x, y, u) ∈ C 0 −→ f σ (x, y, u) :=
x, u − σ
n
i=1
ln(x i u i ).
2 ◦ ) Montrer que (P ˜
D) σ a au plus une solution et que cette solution est
caractérisée comme suit :
(x(σ), y(σ), u(σ)) est
solution de (P ˜
D) σ
⇔
⎛
⎜
⎝
Ax(σ) = b
A y(σ) + u(σ) = c
x(σ) i u(σ) i = σ pour tout i
⎞
⎟
⎠ .
(SO) σ
210