Méthode de Quasi-Newton pour la minimisation sans contraintes

Les inconvénients de la méthode de Newton sont bien connus :

En général elle diverge si le point de départ n'est pas assez proche de l'optimum
Il faut calculer le Hessien $\nabla^2 f$ puis résoudre un système linéaire, ce qui peut être très lourd.

Les méthodes de quasi-Newton sont basées sur l'idée d'approcher directement l'inverse du Hessien $[\nabla^2f(x)]^{-1}$ par une matrice H, symétrique et définie positive, que l'on calcule à chaque itération.

Exemple de fonction 'main'
Lancement avec recherche Dichotomique
Lancement avec recherche Armijo
Comparaison des résultats
Exemples d'affichage pour la comparaison de méthodes
Retour au sujet

Exemple de fonction 'main'

function QuasiNewtonTP()

Choix de la fonction à minimiser

f = @f5;

Initialisation du point de départ de la recherche

n = 15;
x = 0.1*ones(1,n);

Initialisation des paramètres

epsilon = 0.0000001;
maxiter = 1000;

Initialisation des compteurs d'évaluation de la fonction et se son gradient

global NB_EVAL_FONC;
global NB_EVAL_GRAD;
NB_EVAL_FONC = 0;
NB_EVAL_GRAD = 0;

Lancement avec recherche Dichotomique

disp('Avec recherche dichotomique');
lineaire = @dichotomic;
tic;
[xD,k] = bfgs(f,x,epsilon,maxiter,lineaire);
toc
disp(['Nombre d''évaluations de la fonction : ',num2str(NB_EVAL_FONC), ' et de son gradient : ', num2str(NB_EVAL_GRAD)]);

Avec recherche dichotomique
Elapsed time is 0.036172 seconds.
Nombre d'évaluations de la fonction : 0 et de son gradient : 179

Lancement avec recherche Armijo

disp('Avec recherche Armijo');
NB_EVAL_FONC = 0;
NB_EVAL_GRAD = 0;
lineaire = @armijo;
tic;
[xA,k] = bfgs(f,x,epsilon,maxiter,lineaire);
toc
disp(['Nombre d''évaluations de la fonction : ',num2str(NB_EVAL_FONC), ' et de son gradient : ', num2str(NB_EVAL_GRAD)]);

Avec recherche Armijo
Elapsed time is 0.029243 seconds.
Nombre d'évaluations de la fonction : 187 et de son gradient : 232

Comparaison des résultats

Prec = norm(xD-xA);
disp(['La variation entre les méthodes de recherche liénaire sur le résulat est de ', num2str(Prec)]);
if Prec<epsilon
    disp('Les deux méthodes ont donné le même résultat.');
else
    disp('Les deux méthodes ne convergent pas vers la même solution, probablement qu''une des deux n''a pas fonctionné...');
end

La variation entre les méthodes de recherche liénaire sur le résulat est de 2.3505e-08
Les deux méthodes ont donné le même résultat.

Exemples d'affichage pour la comparaison de méthodes

Voici des exemple de ce que l'on peut chercher à observer pour comparer les deux approches de recherche linéaire. Une autre idée serait aussi de faire varier les paramètres internes de ces méthodes...

variation(f,epsilon,maxiter);

end