VI.3. Fonctions convexes
2 ◦ ) On suppose que f est quadratique, i.e. f (x) =
1
2 Ax, x + b, x + c, avec
A symétrique semi-définie positive, et que C est un polyèdre convexe fermé.
Montrer que l’ensemble des points minimisant f sur C est un polyèdre
convexe fermé que l’on exprimera en fonction de C, A, b et x.
Solution : 1 ◦ ) Soit ˜
x un point de C vérifiant la condition (6.34) . De part la
convexité de f, on a
f (x) f (˜ x) + ∇f (˜ x), x − ˜
x ,
d’où f (x) f (˜ x) à l’aide de (6.3.4) . Ainsi, ˜
x minimise aussi f sur C.
Réciproquement, soit ˜
x un point de C minimisant f sur C. On a alors :
f (x) = f (˜ x) f (x) + ∇f (x), ˜
x − x , d’où ∇f (x), ˜
x − x 0,
∇f (x), ˜
x − x 0 (c’est la condition de minimalité),
en définitive ∇f (x), ˜
x − x = 0.
En échangeant le rôle de x et ˜
x, on obtient de même ∇f (˜ x), x − ˜
x = 0.
Or
∇f (x) − ∇f (˜ x) =
1
0
∇
2 f (˜ x + t(x − ˜
x))(x − ˜
x)dt
(6.35)
= H(x − ˜
x), où H :=
1
0
∇
2 f (˜ x + t(x − ˜
x))dt.
Comme
0 = ∇f (x) − ∇f (˜ x), x − ˜
x = H(x − ˜
x), x − ˜
x ,
et que H est symétrique semi-définie positive, H(x − ˜
x) = 0 nécessairement.
D’où ∇f (x) − ∇f (˜ x) = 0 d’après l’évaluation (6.35) .
2 ◦ ) L’ensemble des points minimisant f sur C est
C ∩ {˜ x ∈ R
n
| |b, ˜
x = b, x et A˜ x = Ax} .
269