Chapitre VI. Ensembles et fonctions convexes. Projection...
2 e partie
Soit f : R n → R continûment différentiable.
1 ◦ ) Rappeler, sous ses différentes formes équivalentes, la condition de minimalité du 1 er ordre nécessairement vérifiée en x lorsque x est un minimum local
de f sur C.
2 ◦ ) Considérons g x : R + → R définie par g x (t) := f [p C (x − t∇f (x))].
(i) Montrer que la dérivée à droite de g x en 0 existe et vaut
− − p T (C,x) (−∇f (x)) 2 .
(ii) Vérifier que la dérivée à droite de g x en 0 est strictement négative
lorsque x ne vérifie pas la condition de minimalité du 1 er ordre rappelée à la 1 re
question.
3 ◦ ) On propose l’algorithme suivant (dit du gradient projeté) :
x 0 ∈ C, x k+1 := p C (x k − t k ∇f (x k )),
où t k est choisi minimisant g x k : t ∈ R + −→ g x k (t) := f [p C (x k − t∇f (x k ))] sur
R + (on suppose qu’un tel t k existe).
Démontrer que toute limite d’une sous-suite convergente de {x k } est un
point x de C vérifiant la condition nécessaire de minimalité du 1 er ordre.
Solution : 1 re partie
1 ◦ ) D’après la caractérisation de u = p D (u) pour différents D et u (qui est,
rappelons-le : u ∈ D et δ − u, u − u 0 pour tout δ ∈ D), on a :
(x + tv = p C (x + td)) ⇔
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
x + tv ∈ C
i .e. v ∈
C − x
t
et
(x + td) − (x + tv), c − (x + tv) 0
pour tout c ∈ C
(i.e., t 2
d − v,
c−x
t − v
0 pour tout c ∈ C) ;
v = p C−x
t
(d)
⇔
v ∈
C − x
t
et
d − v,
c − x
t
− v
0 pour tout c ∈ C
.
Donc :
p C (x + td) − x
t
= p C−x
t
(d).
2 ◦ ) a) Si 0 < t 1 < t 2 et y ∈ C,
y−x
t 2
=
y −x
t 1
avec y :=
1 −
t 1
t 2
x +
t 1
t 2
y ∈ C.
Par conséquent, (C − x)/t 2 ⊂ (C − x)/t 1 .
254