Discussion :

[harsh]

Bonjour

J'ai une fonction cout de 4 variables indépendantes à minimiser.

Je dois pour cela utiliser une descente de gradient depuis une solution approchée que j'ai deja pu extraire.

Quelqu'un pourrez t il me rappeller les grandes lignes (les petites ne me rebuteront pas non plus ) de la descente de grandient, je crains de m'être un peu mélanger les pinceaux...

Merci d'avance

[FrancisSourd]

Si tu as une fonction f(x,y,z,t), l'idée est de partir d'un point arbitraire (x0,y0,z0,t0) dans R4 puis de passer à un nouveau point (x1,y1,z1,t1) puis à (x2,y2,z2,t2), etc. On construit ainsi une suite de points susceptible de converger vers l'optimum de la fonction.

Dans la méthode du gradient, on passe d'un point à l'autre en calculant le gradient g(x,y,z,t), égal au vecteur
(df(x,y,z,t)/dx,df(x,y,z,t)/dy,df(x,y,z,t)/dz,df(x,y,z,t)/dt).
Et on construit
(x_i+1,y_i+1,z_i+1,t_i+1) = (xi,yi,zi,ti) + lambda_i g(xi,yi,zi,ti)
lambda_i est un paramètre qui peut être calculé de différentes manières (il y a de meilleures manières de calculer ces valeurs assurant une meilleure convergence de la méthode).

Dans ton cas, il semble difficile d'évaluer f(x,y,z,t). A priori, cela risque donc d'être encore plus difficile d'évaluer son gradient et cette méthode risque d'être difficile à mettre en oeuvre. N'est-ce pas?

[mathieu_t]

(Message Réédité car j'avais pas vu que quelqu'un avait déjà répondu)

Salut !
Dans les très grandes lignes (après ça prendrait des pages), la descente de gradient est une méthode de minimisation locale et donc qui dépend du point initial.
Elle suit itérativement la direction de la plus forte pente négative (indiquée par le gradient) (à chaque itération tu te déplaces d'un certain pas dans cette direction).

Bon c'est bref mais après c'est vraiment calculatoire, je te conseille de faire une recherche sous google.
Tiens là rapido comme ça:
http://lumimath.univ-mrs.fr/~jlm/cou...um/node16.html

Sinon à priori c'est pas un problème d'être dans R^4, ça marche pour R^n, quelque soit n, juste ça fait plus de calculs...
A+

[harsh]

Bonjour

Merci pour ce petit rappel (souvenir souvenir... )

Malheureusement, je ne pense pas que ma solution initiale soit suffisament bonne pour m'eviter tous les minima locaux

Le facteur temps etant important, je pense néanmoins rester sur une solution basée sur le gradient, en connaissez vous des améliorations sympa? ou seriez vous m'orienter sur d'autre algo d'opti pas trop gourmand?

[mathieu_t]

C'est tout le problème d'obtenir des minima globaux ! C'est que c'est gourmand !
Je connais une méthode (mais je suppose qu'il y en a plein d'autres) qui fait un bon compromis : utiliser dans un premier temps un algo génétique, et quand on voit qu'on se rapproche de la solution (c'est à dire qu'on "stagne" entre chaque itération), on commute avec une descente de gradient.
Le fait d'utiliser un algo génétique avant permet de s'assurer d'être dans un min global (si tant est que l'on paramètre correctement l'algo génétique), et la descente permet d'accélérer le mouvement (car c'est à la fin qu'on perd beaucoup de temps lorsqu'on avance d'une itération à l'autre lentement).

A+

[FrancisSourd]

Il y a aussi des variantes de la recherche taboue ou du recuit simulé qui permettent d'intégrer une descente par gradient et quelques idées pour éviter les minima locaux. Par rapport aux algorithmes génétiques, ces méthodes n'utilisent qu'une seule solution: elles seront donc mieux adapter s'il est difficile d'avoir une (bonne) solution de départ.

Sinon (même si ce que je dis ressemble à une tautologie), il est très important d'avoir une bonne heuristique pour construire une bonne solution de départ: cela peut faire gagner beaucoup de temps à la méthode (que ce soit une simple descente par gradient, ou un recuit simulé ou une méthode de recherche taboue).

L'idéal est de disposer de différentes heuristiques capables de construire des solutions avec des caractéristiques différentes (et qui ont donc moins de chance d'aboutir au même minimum local après une descente par gradient). Il est aussi souvent utile d'introduire un peu d'aléatoire dans ces heuristiques de construction de solutions (on les exécute plusieurs fois et on garde la meilleure solution trouvée).