Algorithme de type quasi-Newton

suivant: Algorithme BFGS monter: Algorithmes de descente précédent: Algorithme de Newton Table des matières

Algorithme de type quasi-Newton

L'idée de cet algorithme (voir [13]) est de remplacer la hessienne $H=\nabla^2J$ (ou son inverse $W=[\nabla^2J]^{-1}$ ) par une suite d'approximations symétriques définies positives, que l'on met à jour à chaque itération, pour un coût relativement faible. La mise à jour de cette approximation lors d'une étape de l'algorithme est en général une correction de rang 2 : pour passer de l'étape à l'étape , on pose

$\displaystyle W_{k+1}=W_k+\alpha u.u^T + \beta v.v^T$

où $\alpha$ et $\beta$ sont des scalaires, et

et

des vecteurs.

L'algorithme est donc le suivant :

si on a à l'étape une approximation de $[\nabla^2J(x_k)]^{-1}$ , on définit la direction de descente

$\displaystyle d_k=-W_k.\nabla J(x_k),$
on cherche un pas de descente $\rho_k$ par recherche linéaire,
on pose $x_{k+1}=x_k+\rho_kd_k$ ,
puis on calcule une approximation $W_{k+1}$ de $[\nabla^2J(x_{k+1})]^{-1}$ avec une formule de mise à jour de rang utilisant uniquement , $x_{k+1}$ , $\nabla J(x_k)$ et $\nabla J(x_{k+1})$ .

Toute la difficulté consiste alors à trouver une bonne formule de mise à jour.

suivant: Algorithme BFGS monter: Algorithmes de descente précédent: Algorithme de Newton Table des matières

Retour à la page principale