II.2. Conditions de minimalité du second ordre
Remarque : Dans le cas particulier où C est un convexe fermé non vide et h la
fonction indicatrice de C (h(x) = 0 si x ∈ C, +∞ sinon), ce que dit le résultat de
l’exercice est :
(x minimise g sur C) ⇔ (∇g(x), x − x 0 pour tout x ∈ C)
( caractérisation classique)
⇔ (∇g(x), x − x 0 pour tout x ∈ C)
(caractérisation nouvelle).
** Exercice II.8. Soit f : R n −→ R définie par
x ∈ R
n
−→ f (x) :=
1
2
Ax, x + b, x + c,
où A ∈ S n (R) est supposée définie positive, b ∈ R n et c ∈ R. On considère le
problème d’optimisation suivant :
(P) Minimiser f (x), x ∈ R
n .
1 ◦ ) Rappeler pourquoi (P) a une et une seule solution x, caractérisée comme
étant l’unique solution de l’équation ∇f (x) = 0.
Pour approcher x, on utilise l’algorithme du gradient à pas optimal, qui
consiste à construire une suite (x k ) de la manière itérative suivante :
Initialisation : x 0 ∈ R n ;
Définition de l’itéré x k+1 à partir de x k (lorsque ∇f (x k ) = 0) :
x k+1 := x k + t k d k ,
où d k := −∇f (x k ), et t k est l’unique réel (positif) minimisant t −→ f (x k + td k )
sur R.
Le but de l’exercice est de donner une idée de la vitesse de convergence de
(x k ) vers x en fonction d’un réel associé à A appelé conditionnement de A.
2 ◦ ) Vérifier les relations suivantes : Pour tout k ∈ N,
t k =
d k 2
Ad k , d k
, d k+1 = d k − t k Ad k , d k+1 , d k = 0,
f (x k+1 ) − f = [f (x k ) − f ]
1 −
d k 4
Ad k , d k A −1 d k , d k
,
(2.5)
où f désigne la valeur optimale dans (P).
53