next up previous contents
suivant: Algorithme L-BFGS monter: Algorithmes de descente précédent: Algorithme de type quasi-Newton   Table des matières

Algorithme BFGS

L'algorithme BFGS (voir [7]), dû à Broyden, Fletcher, Goldfarb et Shanno, est un algorithme de type quasi-Newton où la formule de mise à jour de l'approximation de la hessienne inverse est :

$\displaystyle W_{k+1}=U(W_k,s_k,y_k)=\left(I-\frac{s_k\otimes y_k}{\langle y_k,... ...{\langle y_k,s_k \rangle}\right) +\frac{s_k\otimes s_k}{\langle y_k,s_k\rangle}$ (3.1)

avec $ s_k=x_{k+1}-x_k$ , $ y_k=\nabla J(x_{k+1})-\nabla J(x_k)$ , et $ u\otimes v: d \to \langle v,d \rangle u$ .

En pratique, on stocke $ W_0$ et les paires $ (s_k,y_k)$ calculées à chaque étape. En effet, il est trop coûteux de stocker toutes les matrices $ W_k$ . L'inconvénient majeur de cet algorithme est le coût de stockage de toutes les paires $ (s_k,y_k)$ , surtout lorsque la dimension du problème est importante (de l'ordre de $ 10^6$ ).


Retour à la page principale