III.4. Conditions de minimalité du second ordre
Commentaire : – La matrice X obtenue comme solution de (P) n’est pas nécessairement définie positive, pour cela il faudrait qu’au moins y, s (=
Xs, s
)
soit > 0. C’est le cas dans la 3 e question où y, s =
W −2 s, s
> 0.
– Cet exercice trouve ses racines dans la nécessité d’expliquer « de manière
variationnelle » les formules de mise à jour dans les méthodes de minimisation
sans contraintes dites de quasi-Newton. Ainsi, dans la 2 e question, parmi les
X ∈ S n (R) vérifiant Xs = y (appelée équation de la sécante ou de quasi-Newton),
on cherche celle qui est la plus proche de A (au sens de la distance dérivée de
·, · ·). La formule de mise à jour qui en résulte est PSB (pour Powellsymétrique-Broyden).
– Le résultat de la 3 e question a un pendant que voici.
Soit W ∈
◦
P n (R) telle que W s = W −1 y, et considérons le problème de minimisation suivant :
(R) Minimiser
1
2
W (X − B)W
2 parmi les X ∈ S n (R) vérifiant Xy = s.
Alors la solution X ∗ de (R) est donnée par
X ∗ := B +
(s − By)s + s(s − By)
s, y
−
s − By, y
(s, y)
2 ss
.
Si B est définie positive, il en est de même de X ∗ et
(X ∗ )
−1 = B
−1 +
yy
y, s
−
B −1 ss B −1
B −1 s, s
·
Les expressions de X ∗ et X ∗ sont à la base des formules de mise à jour de la méthode DFP (pour Davidon-Fletcher-Powell) et BFGS (pour Broyden-FletcherGoldfarb-Shanno).
*** Exercice III.24. Étant donné u = (u 1 , . . . , u n ) ∈ R n , on cherche un élément
x = (x 1 , . . . , x n ) ∈ R n vérifiant x 1 x 2 . . . x n le plus proche possible de u
(au sens de la norme euclidienne usuelle de R n ).
1 ◦ ) Formaliser cette question comme un problème de minimisation convexe,
ou comme un problème de projection sur un cône convexe fermé.
2 ◦ ) Décrire les conditions caractérisant l’unique élément x = (x 1 , . . . , x n )
répondant à la question.
3 ◦ ) On traite ici un exemple dans R 4 : étant donné u = (2, 1, 5, 4), trouver
l’unique x = (x 1 , x 2 , x 3 , x 4 ) vérifiant x 1 . . . x 4 à distance minimale de u.
105
Commentaire : – La matrice X obtenue comme solution de (P) n’est pas nécessairement définie positive, pour cela il faudrait qu’au moins y, s (=
Xs, s
)
soit > 0. C’est le cas dans la 3 e question où y, s =
W −2 s, s
> 0.
– Cet exercice trouve ses racines dans la nécessité d’expliquer « de manière
variationnelle » les formules de mise à jour dans les méthodes de minimisation
sans contraintes dites de quasi-Newton. Ainsi, dans la 2 e question, parmi les
X ∈ S n (R) vérifiant Xs = y (appelée équation de la sécante ou de quasi-Newton),
on cherche celle qui est la plus proche de A (au sens de la distance dérivée de
·, · ·). La formule de mise à jour qui en résulte est PSB (pour Powellsymétrique-Broyden).
– Le résultat de la 3 e question a un pendant que voici.
Soit W ∈
◦
P n (R) telle que W s = W −1 y, et considérons le problème de minimisation suivant :
(R) Minimiser
1
2
W (X − B)W
2 parmi les X ∈ S n (R) vérifiant Xy = s.
Alors la solution X ∗ de (R) est donnée par
X ∗ := B +
(s − By)s + s(s − By)
s, y
−
s − By, y
(s, y)
2 ss
.
Si B est définie positive, il en est de même de X ∗ et
(X ∗ )
−1 = B
−1 +
yy
y, s
−
B −1 ss B −1
B −1 s, s
·
Les expressions de X ∗ et X ∗ sont à la base des formules de mise à jour de la méthode DFP (pour Davidon-Fletcher-Powell) et BFGS (pour Broyden-FletcherGoldfarb-Shanno).
*** Exercice III.24. Étant donné u = (u 1 , . . . , u n ) ∈ R n , on cherche un élément
x = (x 1 , . . . , x n ) ∈ R n vérifiant x 1 x 2 . . . x n le plus proche possible de u
(au sens de la norme euclidienne usuelle de R n ).
1 ◦ ) Formaliser cette question comme un problème de minimisation convexe,
ou comme un problème de projection sur un cône convexe fermé.
2 ◦ ) Décrire les conditions caractérisant l’unique élément x = (x 1 , . . . , x n )
répondant à la question.
3 ◦ ) On traite ici un exemple dans R 4 : étant donné u = (2, 1, 5, 4), trouver
l’unique x = (x 1 , x 2 , x 3 , x 4 ) vérifiant x 1 . . . x 4 à distance minimale de u.
105