Algorithme de Newton

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

Algorithme de Newton

Supposons que l'on veuille minimiser une fonctionnelle dépendant d'un paramètre . L'algorithme de Newton consiste en la méthode suivante :

Initialisation : choix d'un point de départ de la minimisation .
Itérations :
- À partir de , on construit la direction de descente
  
  $\displaystyle \displaystyle d_k=-[\nabla^2J(x_k)]^{-1}.\nabla J(x_k)$
  
  qui minimise l'approximation quadratique locale
  
  $\displaystyle J(x)\approx J(x_k)+(x-x_k).\nabla J(x_k) + \displaystyle \frac{1}{2}(x-x_k)^T.\nabla^2J(x_k).(x-x_k).$
- On calcule alors un pas de descente $\rho_k$ le long de la direction de descente par recherche linéaire (on minimise la fonctionnelle le long de ) de sorte que
  
  $\displaystyle J(x_k+\rho_kd_k)\le J(x_k)+\alpha \rho_k [\nabla J(x_k)]^T.d_k$
  
  et
  
  $\displaystyle \vert[\nabla J(x_k+\rho_kd_k)]^T.d_k\vert\le \beta \vert[\nabla J(x_k)]^T.d_k\vert$
  
  avec $0 < \alpha < \beta < 1$ (conditions de Wolfe, [54]).
- On pose alors $x_{k+1}=x_k+\rho_kd_k$ .
On réitère ce procédé jusqu'à convergence de la suite vers le minimum de la fonctionnelle .

Cet algorithme est très efficace, mais dans un cas d'assimilation de données opérationnelles sur un système complexe, il est très coûteux à mettre en $\oe$ uvre puisqu'il nécessite à chaque étape le calcul de la hessienne inverse de la fonctionnelle au point considéré.

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

Retour à la page principale