Descente de gradient

[Anonyme]

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.

[Anonyme]

"Laly" 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

[Anonyme]

OK merci mais pourquoi rechercher dans la direction du gradient ? Et
comment déterminer un bon lambda ?


Laly.

"FDH" wrote in message news:...
> "Laly" a écrit dans le message de news:
> 3fc57925$0$27034$626a54ce@news.free.fr...[color=green]
> > 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[/color]

[Anonyme]

> 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 :
http://www.essi.fr/~leroux/moindrescarresbis/node9.html
membres.lycos.fr/projetdeamath2003/Projet1/p2p2.htm

[Anonyme]

Ok, j'ai compris.


Merci beaucoup pour votre temps et vos explications.