Scribd
Importer
119 vues2 pages

Comparaison des algorithmes de gradient

Transféré par

sam
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
119 vues2 pages

Comparaison des algorithmes de gradient

Transféré par

sam
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université de Poitiers Année 2009-2010

Master de Mathématiques et Applications


MATH 2M15 Optimisation

Corrigé TP 1 : Algorithme de gradient

Solution du dernier exercice : comparaison de la vitesse de l’algorithme de gradient à


pas fixe, à pas optimal et à pas optimal “randomisé” pour la résolution de
1
Ax = b ⇐⇒ min hAx, xi − hb, xi.
x∈RN 2
On a choisi

A = diag([1 : 1 : 100]), xsol = ones(N, 1) et x0 = rand(N, 1).

//Gradient a pas optimal random pour probleme quadratique


clear
clf
N=100;
//A=2*diag(ones(N,1),0)-diag(ones(N-1,1),-1)-diag(ones(N-1,1),1);
A=diag([1:1:N]);
xsol=ones(N,1);
b=A*xsol;
x0=rand(N,1);
itermax=100;
//1.gradient pas fixe
x=x0;
Tfixe=[norm(x-xsol,’inf’)];
mu=0.01;
for k=1:itermax
d=A*x-b;
x=x-mu*d;
err=norm(x-xsol,’inf’);
Tfixe=[Tfixe err];
end

//2.gradient pas optimal


x=x0;
Topt=[norm(x-xsol,’inf’)];
for k=1:itermax
d=A*x-b;
mu=d’*d/(d’*A*d);
x=x-mu*d;
err=norm(x-xsol,’inf’);
Topt=[Topt err];
end

1
//gradient a pas optimal randomis
x=x0;
Trand=[norm(x-xsol,’inf’)];
for k=1:itermax
d=A*x-b;
mu=d’*d/(d’*A*d);
th=2*rand(1,1);
x=x-th*mu*d;
err=norm(x-xsol,’inf’);
Trand=[Trand err];
end

plot2d([0:1:itermax]’,[Tfixe’ Topt’ Trand’],logflag=’nl’,style=[1 2 3]);


xtitle(’’,’k’,’||xk-x||’)
legends([’pas fixe’;’pas optimal’;’randomis’],[1 2 3],opt=’ll’)

0
10

−1
10
||xk−x||

−2
10

−3
10
pas fixe

pas optimal
randomisé
−4
10 0 10 20 30 40 50 60 70 80 90 100
k

Figure 1: Vitesse de convergence des algorithmes de gradient

Vous aimerez peut-être aussi