IV.3. Premiers pas dans la théorie de la dualité
*** Exercice IV.11. Soient a 1 , . . . , a m dans R n , b 1 , . . . , b m dans R, et soit
ˆ
P
le problème qui consiste à minimiser ˆ
f (x) := ln
m
j=1
e a j ,x−b j
pour x ∈ R n .
1 ◦ ) Montrer que
ˆ
P
est équivalent (en des termes qu’on précisera) au problème (avec contraintes) (P) posé dans R n × R m suivant :
(P)
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
Minimiserf (x, y) := ln
⎛
⎝
m
j=1
e
y j
⎞
⎠
sous les contraintes Ax − b = y,
où A ∈ M m,n (R) est la matrice dont les lignes sont a 1 , . . . , a m et b le vecteur
de R m de composantes b 1 , . . . , b m .
2 ◦ ) Expliciter la fonction duale
λ ∈ R
m
−→ ψ (λ) =
inf
(x,y)∈R n ×R m
{f (x, y) + λ, Ax − b − y} .
En déduire la forme du problème dual (D) de (P).
Solution : 1 ◦ ) Si x est une solution de
ˆ
P
, on pose y = Ax − b et (x, y)
devient solution de (P). Réciproquement, si (x, y) est solution de (P), on a
Ax − b = y et x est solution de
ˆ
P
.
2 ◦ ) Il s’agit de calculer
inf
(x,y)∈R n ×R m
⎧
⎨
⎩
ln
⎛
⎝
m
j=1
e
y j
⎞
⎠ − −λ, y − −λ, b +
A
λ, x
⎫
⎬
⎭
.
Plusieurs cas sont à distinguer :
a) Si A λ = 0, l’infimum ci-dessus est clairement égal à −∞.
b) Si A λ = 0, on a à déterminer en fait
inf
y∈R m
⎧
⎨
⎩
ln
⎛
⎝
m
j=1
e
y j
⎞
⎠ − −λ, y
⎫
⎬
⎭
.
(4.2)
– Situation où
m
j=1
λ j = 1.
153