Méthode de quasi newton BFGS
Il existe plusieurs méthodes pour construire la matrice approchée H. Nous allons utiliser celle mise au point par Broyden, Fletcher, Goldfarb et Shanno (BFGS).
Contents
function [x,k] = bfgs(f,x,epsilon,maxiter,lineaire)
Initialisation
La première matrice approchée est initialisée par la matrice identité. Ainsi la première direction sera celle du gradient.
n = length(x);
g = feval(f,x);
H = eye(n);
k = 0;
while (norm(g)>epsilon) && (k<maxiter)
Calcul de la direction à l'aide du Hessien
d = -g*H;
Recherche linéaire
Le recherche linéaire peut être effectuée de différentes manières, plus ou moins adaptées ou efficaces. C'est pourquoi ce choix est laissé en paramètre de l'algorithme ( lineaire )
t = feval(lineaire,f,x,d);
Mise à jour de la solution et du gradient
x = x+t*d; gk = feval(f,x);
Réinitialisation
Comme pour les gradients conjugués, on réinitialise les valeurs approchées successivement tous les pas, afin d'éviter une dérive numérique.
if (mod(k,n)==0) H = eye(n); else
Calcul de l'approximation de l'inverse du Hessien
La formule mise au point par BFGS est la suivante :
delta = t*d; gamma = (gk-g); prodScal = delta*gamma'; mat1 = (delta'*gamma*H+H*gamma'*delta)/prodScal; mat2 = (1+((gamma*H*gamma')/prodScal))*((delta'*delta)/prodScal); H = H-mat1+mat2; end k = k+1; g = gk; end
end