Algorithme pour minimiser des fonctions

[invite4ef352d8]

Bonjour !

existe t'il des algorithme efficace pour rechercher le minimum d'une fonction de R->R... et pour des fonction de R^n-> R ?



(un peu comme la methode de Newton pour la recherche de Zeros par exemple...)
-----

[invitec314d025]

Oui il y a beaucoup de méthodes, mais il faut généralement connaîter un peu la fonction pour pouvoir espérer s'approcher d'un minimum global. Tu peux regarder notamment du côté de la descente du gradient ou du recuit simulé.

[invite6de5f0ac]

Bonjour,

Il y en a, et des kilotonnes... Voir p.ex. "Numerical Recipes" (www.nr.com), mais il y a des centaines de bouquins consacrés au sujet.

En général, les fonctions de R -> R se comportent pas trop mal à condition d'être "raisonnablement régulières", c'est-à-dire sans variations trop brutales, et aussi avec des optimums bien séparés (pas de fonction trop "plate" avec plein de minima locaux p.ex.)

De R^n -> R, c'est la foire d'empoigne: à peu près tous les coups sont permis. Il faut que le Jacobien lui-même soit à peu près régulier, que ses directions propres ne soient pas trop mal fichiues... Il y a autant de méthodes que de classes de problèmes, plus en général LA méthode à laquelle personne n'avait pensé (parce qu'elle est nulle en général) mais qui précisément marche remarquablement bien dans ce cas précis...

-- françois

[invite4ef352d8]

dans mon cas il s'agit de trouver la position d'equilibre la plus stable d'un ensemble (finit) de charge. donc je pense que sa donne une fonction plutot corecte (dans son comportement, pas dans la facilité de calcule evidement) aux voisinages des minimas.


je vais faire une recherche sur les references que vous m'avez donné... je verai bien...


Merci !

[A voir en vidéo sur Futura]

[invite4ef352d8]

bon j'ai repris une couche de matrice Hessienne, Jacobienne et je me suis lancé dans les recherches...

j'ai lu quelque page (sur la methode de la descente du gradient principalement, le recuit simulé sa ma pas l'air trop compliqué pour etre efficace ) et je me pose deux/trois question.

comment on fait pour choisir la valeur du "pas" (le coeficient par lequel on multiplie le gradient avant de l'ajouté au 'Xt-1' ) ? le choix influe fortement visiblement. on dirait que pour une fonction donné, il y a une valeur critique qui marche extrement bien et des qu'on s'en eloigne sa se degrade tres vite...

sinon dans cette article "Methode de la descente du gradient et Methode de Newton" ils parlent d'utiliser la methode de Newton pour chercher un minima (ce qui regle le probleme du "pas" ), mais je ne comprend pas en quoi la methode aboutit a un Minimum et non pas a n'importe qu'elle point critique ?

d'ailleur je les mis en oeuvre et elle n'aboutit certe pas tous a fait a n'importe qu'elle point critique, mais par contre elle donne aussi souvent un maximum qu'un minimum... j'ai raté quelque chose, ou c'est normale ?

[invitec314d025]

La méthode du recuit simulé doit au contraire donner de meilleurs résultats dans le cas général que la descente du gradient.
Pour le choix du pas dans la descente du gradient, c'est un problème compliqué, tu trouveras une littérature abondante là-dessus. Prendre un pas fixe est rarement une bonne idée, mais c'est bien pour commencer et faire des essais.
Sinon tu as du faire une erreur, tu ne devrais pas aboutir à un maximum local, puisque par définition tu suis la plus grande pente (donnée par le gradient) dans la direction qui fait diminuer la valeur prise par la fonction.

[invite6de5f0ac]

j'ai lu quelque page (sur la methode de la descente du gradient principalement, le recuit simulé sa ma pas l'air trop compliqué pour etre efficace ) et je me pose deux/trois question.

J'ai personnellement utilisé le recuit simulé, avec succès. Son gros problème est de ne converger que très très lentement. Dans ton cas, ça devrait marcher plutôt bien, mais comme ta fonction a probablement une "bonne" tête (en tout cas tu en connais certainment pas mal de propriétés), autant utiliser toutes les infos disponibles.

Le recuit simulé ne se justifie que lorsque les minima sont mal séparés, ou très sensibles aux conditions initiales. Ou, plus souvent, lorsqu'on ne connaît pas assez bien la fonction (i.e. parce qu'on a la flemme de l'étudier de plus près)

Mes souvenirs sur la méthode de descente du gradient sont un peu loin, mais le phénomène que tu décris me rappelle quelque chose. J'ai probablement eu le même problème à l'époque... Il faut voir que souvent les méthodes d'optimisation détectent n'importe quel extrémum, maximum ou minimum, et si en plus on espère qu'il soit global... dans tes rêves!

-- françois

[invite4ef352d8]

euh c'est pas a propos de la descente du gradient que j'avais un probleme de convergence , mais avec l'autre methode presenté juste en dessous qui est une adaptation de la methode de Newton.

[invitec314d025]

euh c'est pas a propos de la descente du gradient que j'avais un probleme de convergence , mais avec l'autre methode presenté juste en dessous qui est une adaptation de la methode de Newton.

Ah, pardon, je vais regarder le doc dont tu t'es servi alors.

Le recuit simulé ne se justifie que lorsque les minima sont mal séparés, ou très sensibles aux conditions initiales. Ou, plus souvent, lorsqu'on ne connaît pas assez bien la fonction (i.e. parce qu'on a la flemme de l'étudier de plus près)

Bon c'est vrai que c'est pas forcément très rapide, mais dans la pratique il est fréquent d'avoir pleins de minima locaux très génants. Et puis la méthode et son origine physique sont très belles, ce serait dommage de ne pas s'y intéresser.

Il faut voir que souvent les méthodes d'optimisation détectent n'importe quel extrémum, maximum ou minimum, et si en plus on espère qu'il soit global... dans tes rêves!

Euh, non, quand même. Pour converger sur un maximum local, il faut vraiment tomber pile poil dessus, et encore ça ne pose pas de problème avec les méthodes stochastiques. Par contre c'est vrai que dès que la fonction est un chouya bizarre, on se contente souvent d'un minimum local.

[invite6de5f0ac]

Bonsoir,

C'est vrai que le principe du recuit simulé est très élégant, et que ça vaut le coup d'être essayé, ne serait-ce que pour la culture générale.

En plus, je suis persuadé que ça s'applique très bien à une répartition de charges dans l'espace -- il y a parfois des solutions "doubles" avec bifurcation. Mais dans ce cas on connaît la forme explicite du potentiel...

En revanche (ça, c'est plus précisément destiné à matthias), dire qu'il y a souvent des tas de minima locaux mal séparés, et tout de suite après dire qu'il faut vraiment tomber pile poil dessus pour les voir, je m'interroge. La loi de Murphy dit que l'ensemble des minima locaux est dense dans tout voisinage d'un extrémum global...

L'intérêt du recuit simulé est d'ignorer les minima locaux qui ne sont pas "solides". Mais c'est une autre paire de manches de prouver qu'on a bien atteint l'extrémum global!

Les méthodes plus classiques permettent de localiser très précisément un extrémum global, à condition d'avoir une bonne idée préalable de sa position. Ce qui n'est pas donné à tout le monde.

-- françois

[invitec314d025]

En revanche (ça, c'est plus précisément destiné à matthias), dire qu'il y a souvent des tas de minima locaux mal séparés, et tout de suite après dire qu'il faut vraiment tomber pile poil dessus pour les voir, je m'interroge.

Peut-être parce que dans un cas je parle de minimum et dans l'autre de maximum
Mais peut-être que j'avais moi-même mal compris ta remarque sur la "détection" des extrema locaux quels qu'ils soient (minimum ou maximum).

[invitec314d025]

euh c'est pas a propos de la descente du gradient que j'avais un probleme de convergence , mais avec l'autre methode presenté juste en dessous qui est une adaptation de la methode de Newton.

Tu peux regarder ce document. Il n'est pas très détaillé (pas de démo notamment) mais tu y trouveras pas mal de variantes avec les noms, donc ça peut être une bonne base pour une recherche plus approfondie. Il y a des bidouilles pour éviter de partir dans le mauvais sens avec la méthode de Newton quand le Hessien n'est pas défini positif.

[GrisBleu]

Salut

Ayant eu l occasion le mois dernier de faire un tour de ces methodes, voila mon petit resume

- descente de gradient : tu descend le long du gradient. C est intuitif, simple mais lent. De plus tu restes bloques dans un minimum local.
- gradient conjuges : tu descend le long de gradient mais les notions d ortogonalites dependent de la metrique engendree par le hessienne (que tu ne calcules jamais, donc c est rapide)
- Newton : au lieu de se servir d un DL a l ordre 1 comme les gradients, tu vas a l ordre 2. Pb il faut calculer la hessienne a chaque fois. C est bien plus rapide que les methodes du graident.
- levenberg marquard : C est une approximation de la hessienne qui n utilise que des DL d ordre 1. C est la methode de reference pour la minimisation (c est la de base dans Matlab). Rapide et pas trop idiote.

Le probleme de ces methodes c est qu elles seront bloques dans des minimums locaux. tu peux alors sortir l artillerie lourde (le recuit simule donc) qui converge vers le vrai minimum, mais qui est largement (et de beaucoup) plus lent. Ca depnd donc du temps maximal de calcul et de la performance souhaitee

Si ta fonction est de R^n dans R, attention, tu risques d avoir beaucoup de minimum locaux.

++

[invite4ef352d8]

Merci beaucoup pour le Document matthias, et pour ces precisions Wlad_von_tokyo , c'est exactement le genre de renseignement que je cherchais !

[invite4ef352d8]

Re-bonjour !


j'ai potasé tous les articles/cours/exemple que j'ai trouvé sur l'optimisation et j'ai essayé de les appliqué a la resolution de mon probleme (Position d'equilibre de n charge ponctuelle a la surface d'une sphere)


Visiblement ma fonction rentre dans la categorie "vraiment moche"

-pour ce qui est des minima locaux ils sont suffisement peu marqué pour ne pas poser probleme,

-en revanche toute les methode basé sur la methode de newton diverge systematiquement (et tres rapidement), a part Levenberg marquardt que j'ai pas vraiment reussit a faire fonctioner :S


-la descente du gradient marche bien tant que je regle le coeficient a la main tous au long de la recherche (qui est quand meme assez longue...)

-j'ai essayé d'appliquer une des methodes proposer pour choisir le coeficient du gradient : prendre grad*grad/(gradT*Hessien*grad) (ce qui revien a faire un "pas" de la methode de newton dans la direction du gradient) mais la sa donne un comportement curieux... la convergence est initialement tres rapide, mais assez rapidement sa "stagne" avec la norme du gradient et le coeficient a peu pres constant.
a ce moment le je remplace le coeficient 'grad*grad/(gradT*Hessien*grad)' par la valeur qu'il avait a la fin (quitte a avoir un truc constant, autant evité de le recalculer) mais je maintien du coef pour voir comment il est evolu...
et le resultat est surprenant, la convergence reprend (comme avec le gradient, lentement) mais la valeur de 'grad*grad/(gradT*Hessien*grad)' devient enorme (elle passe de 0.15, 0.10 a 70/40)

quelqu'un a t'il deja vu ce genre de phenomene ... parceque c'est vraiment curieux la :S

[invite643d458e]

Je vous conseille ce lien sur l'optimisation par descente de gradient et en particulier le chapitre traitant de l'optimisation par encadrements successifs

[invite9cf21bce]

Salut.

Bonsoir,
La loi de Murphy dit que l'ensemble des minima locaux est dense dans tout voisinage d'un extrémum global...

Si Murphy t'entendait il te répondrait :

"l'ensemble des minima locaux est dense dans tout voisinage d'un extrémum global...", sauf si ça t'arrangerait bien qu'il le soit

Les méthodes plus classiques permettent de localiser très précisément un extrémum global, à condition d'avoir une bonne idée préalable de sa position. Ce qui n'est pas donné à tout le monde.

Pourquoi personne ne parle des algorithmes génétiques ??

Apparemment, ça marche (et cette fois, ce n'est pas une blague), surtout dans des problèmes du type voyageur de commerce mixtes discret-continu (et non, je ne sais pas vraiment ce que ça veut dire), dixit un copain qui en a fait son métier (même que désormais il voyage pour vendre ses algorithmes).

Taar.

[invite4ef352d8]

Je vous conseille ce lien sur l'optimisation par descente de gradient et en particulier le chapitre traitant de l'optimisation par encadrements successifs

euh... oui c'est gentil, mais le post a plus d'un ans et demi... et le projet en question est terminé maintenant

[invite74b500b2]

Je cherche à faire un programme qui trouve le minimum d'une fonction de R^n dans R. (n=2).
La méthode choisie est celle de levenberg marquard (pas de possibilité de changer)

Salut
- levenberg marquard : C est une approximation de la hessienne qui n utilise que des DL d ordre 1. C est la méthode de référence pour la minimisation (c est la de base dans Matlab).
++

Donc en parcourant un peu les documents disponible sur le net j'ai pas trop compris. surtout que les algorithmes présentés n'étais pas très explicite (en tout cas du moins pour moi car j'ai pas de grande connaissance en matheux).
Donc si vous pouvez m'aider à mettre un peu de lumière sur toutes ces formule.

Cordialement