J'ai par exemple y=f(x) dont je cherche le max sans connaître la formulation de la fonction (c'est une boîte noire).
Il y a une méthode pour faire ça, en prenant deux bornes x0 et x2, puis en prenant x1 = (x0+x2)/2 ...etc... Quel est le véritable nom de cette méthode svp ?
Merci
La dichotomie à tout hasard ?
C'est plus généralement une méthode qui peut être utilisée pour trouver des valeurs approchées de fonctions en tout point ( à condition qu'elle soit continue ^^ )
Tu dois pouvoir faire mieux, si ta fonction, quoique inconnue, n'est pas trop bizzare, en calculant une approximation de la dérivée et en "suivant la pente".
Envoyé par jobherzt
La dichotomie à tout hasard ?
C'est plus généralement une méthode qui peut être utilisée pour trouver des valeurs approchées de fonctions en tout point ( à condition qu'elle soit continue ^^ )
Ca fait quand-même déjà beaucoup de considérer continuité et dérivabilité...
bah oui et non, un paquet de fonction "naturelles" sont quand meme plus ou moins derivables, je veux dire que meme si elles ne le sont pas en tout point, cette methode d'approximation devrait fonctionner.. tout depend du contexte de la question, mais s'il s'agit d'analyse numerique, on peut quand meme imaginer que les choses se passent bien. de toute facon, sa question n'aurait pas vraiment de sens sinon, et meme sa methode ne menerait pas a grand chose.
Et la continuité exigée par la dichotomie reste moins exigeante que la dérivabilitéCertes c'est déjà une hypothèse assez contraignante à vérifier, mais je ne connais pas vraiment d'autres méthodes
)
Quelque chose doit m'échapper, mais comment faites-vous pour trouver le max d'une fonction (même continue) par dichotomie ?
Il faut peut-être regarder du côté des heuristiques...
Dernière modification par Médiat ; 28/11/2007 à 08h56.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
salut,
la méthode du simplexe de Nelder et Mead ne suppose même pas que la fonction f est numérique. Il suffit que pour deux valeurs x et y, on puisse comparer f(x) et f(y).
Ca a été utilisé par exemple pour optimiser un mélange de cafés: en présence de deux mélanges x et y les goûteurs peuvent dire lequel est le meilleur, sans avoir à attribuer une valeur numérique.
Oui, moi aussi ca m'intrigue, en fait... mais je persiste a croire que "suivre la pente" peut prendre un sens meme pour des fonctions pas franchement continue ou derivable. Dans la mesure ou c'est de l'approximation numerique, on doit pouvoir s'en accomoder, a fortiori si la question est posée dans un cas "concret", il est possible que la fonction soit relativement sympathique. Meme si les fonctions franchement moches sont majoritaires mathematiquement parlant, on en rencontre pas tant que ca en pratique.
Moralement, pour "suivre la pente" il suffit presque de savoir comparer plusieurs valeurs, et d'aller vers le coté le plus bas, ca doit quand meme souvent marcher.
Tu risques de ne trouver que des extremums locaux.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Evidemment, mais ca c'est l'eternel probleme en optimisation, et a ma connaissance, il n'existe pas de methode miracle, a fortiori si la fonction n'est pas connue (sinon on a des techniques numeriques assez futé, genre inversion ensemblistes par intervalles...)
Bien sur, mais c'est tout l'intérêt des méthodes genre recuit-simulé, TABOUS, etc. qui ne sont pas miracles, mais qui permettent d'éviter de s'arrêter au premier extremum local venu.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Tout a fait d'accord, notes que je n'ai jamais pretendu que ma reponse etait la seule possible ! et puis ces methodes sont surtout, me semble t il, liées à l'optimisation combinatoire, donc plutot a des fonctions discretes. Je crois qu'il existe des tentatives pour les generaliser au cas continu (notamment les colonies de fourmi), mais c'est assez bourrin et pas encore au point, je crois.
Apres, rien ne t'empeche de generer aleatoirement un grand nombre de valeurs initiales, puis d'utiliser des methodes plus ou moins combinatoire pour trouver un maximum "un peu moins local que les autres". D'ailleurs, les algos que tu cites ne sont efficaces qu'en les complementant avec des methodes d'optimisation locale.
Salut
Il faut voir aussi combien de temps tu as pour calcule ton extremum.
Si tu dois aller vite, des methods de type "suivre la pente" peuvent etre un bo compromis
Si tu as le temps, le recuit semble effectivement une bonne idee
Si tu as une idee de ta fonction, sans la connaitre exactement, ca peut etre utile aussi.
++
