Qui pourrais m'expliquer de manière intuitive le principe de la descente de
gradient pour optimiser une fonction de plusieurs variables et pourquoi ca
marche ?
Merci par avance et bonne journée.
Laly.
Posted by: FDH
"Laly" <lalystar@free.fr> a écrit dans le message de news:
3fc57925$0$27034$626a54ce@news.free.fr...
> Bonjour,
>
>
> Qui pourrais m'expliquer de manière intuitive le principe de la descente
de
> gradient pour optimiser une fonction de plusieurs variables et pourquoi ca
> marche ?
>
>
> Merci par avance et bonne journée.
>
>
> Laly.
>
>
Tu as une fonction f définie sur R^n (on suppose qu'elle admet un minimum
ou, mieux, qu'elle est convexe et tend vers +infini à l'infini)
Tu te donnes un vecteur u0
Tu "cherches" un réel lambda tel que f(u0+lambda grad f(u0)) réalise de
minimum de f sur la droite u0+R.grad f(u0) (ce qui revient à minimiser une
fonction d'une variable réelle)
Tu poses u1=u0+lambda grad f(u0)
Tu recommences avec u1...
Il y a des hypothèses sur f qui assurent la convergence de la suite (u_n)
De mémoire ça doit être : f est C^2 et il existe une constante m>0 telle que
pour tout x, pour tout h : (d2f(x)h,h)>=m||h||^2
Posted by: Laly
OK merci mais pourquoi rechercher dans la direction du gradient ? Et
comment déterminer un bon lambda ?
Laly.
"FDH" <fdgp@free.fr> wrote in message news:<3fc5a5c1$0$26794$636a55ce@news.free.fr>...
> "Laly" <lalystar@free.fr> a écrit dans le message de news:
> 3fc57925$0$27034$626a54ce@news.free.fr...
> > Bonjour,
> >
> >
> > Qui pourrais m'expliquer de manière intuitive le principe de la descente
> de
> > gradient pour optimiser une fonction de plusieurs variables et pourquoi ca
> > marche ?
> >
> >
> > Merci par avance et bonne journée.
> >
> >
> > Laly.
> >
> >
>
> Tu as une fonction f définie sur R^n (on suppose qu'elle admet un minimum
> ou, mieux, qu'elle est convexe et tend vers +infini à l'infini)
>
> Tu te donnes un vecteur u0
>
> Tu "cherches" un réel lambda tel que f(u0+lambda grad f(u0)) réalise de
> minimum de f sur la droite u0+R.grad f(u0) (ce qui revient à minimiser une
> fonction d'une variable réelle)
> Tu poses u1=u0+lambda grad f(u0)
>
> Tu recommences avec u1...
>
> Il y a des hypothèses sur f qui assurent la convergence de la suite (u_n)
> De mémoire ça doit être : f est C^2 et il existe une constante m>0 telle que
> pour tout x, pour tout h : (d2f(x)h,h)>=m||h||^2
Posted by: FDH
> OK merci mais pourquoi rechercher dans la direction du gradient ? Et
> comment déterminer un bon lambda ?
>
>
> Laly.
Faisons un DL à l'ordre 1 de f en x :
f(x+h)=f(x)+h.grad f(x)+o(||h||)
Donc le terme de "variation principale" h.grad f(x) sera d'autant plus grand
que h (le vecteur de descente) formera un angle petit avec le gradient
Donc c'est suivant le gradient que la fonction "varie le plus"
Comment déterminer le bon lambda ?
Il s'agit de minimiser une fonction d'une variable réelle
g(lambda)=f(x-lambda.grad f(x)) (x fixé)
Pour cela, il existe de nombreuses méthodes.
On peut penser à la Méthode de Newton appliquée à g' :
lambda(0)=0
lambda(n+1)=lambda(n)-g'(lambda(n))/g''(lambda(n))
Remarque : pour limiter le temps de calcul, on doit pouvoir se contenter
d'une ou deux itérations de Newton à chaque descente de gradient (il y a
sûrement des études qui ont été faites à ce sujet)
Remarque : si ta fonction f est quadratique elliptique (polynôme de degré 2
qui tend vers +inf à l'inf), le méthode de "descente de gradient" n'est pas
la plus adaptée. Le "gradient conjugué" converge plus rapidement
Je n'ai malheureusement pas le temps de l'expliquer ici, mais on trouve
facilement sur google : www.essi.fr/~leroux/moindrescarresbis/node9.html
membres.lycos.fr/projetdeamath2003/Projet1/p2p2.htm
Posted by: Laly
Ok, j'ai compris.
Merci beaucoup pour votre temps et vos explications.