optimisation locale et globale

[invite9c7554e3]

Bonjour,

Je suis débutant en optimisation et il y a un truc que je ne comprends pas trop avec la methode de recherche d'un minimum avec l'algorithme de descente de gradient (DG).

J'ai vu qu'en optimisation il y avait des méthodes permettant de trouver un minimum global car la methode de DG ne le permet pas.

==> Mais se que je ne comprends pas c'est que si on tire un point initial au hasard un grand nombre de fois et qu'on applique la DG a chaques fois alors on arrivera bien à trouver un minimum global?

==> Qu'en pensez vous?
-----

[invite5c27c063]

J'ai vu qu'en optimisation il y avait des méthodes permettant de trouver un minimum global car la methode de DG ne le permet pas.

Exact

==> Mais se que je ne comprends pas c'est que si on tire un point initial au hasard un grand nombre de fois et qu'on applique la DG a chaques fois alors on arrivera bien à trouver un minimum global?

==> Qu'en pensez vous?

Heuristiquement, ca marchera probablement mais ca depend tout de meme si le hasard fait bien les choses...

A defaut de proprietes sur la fonction, rien ne prouvera jamais que la minimum global ne soit pas dans un "bassin" n'appartenant a aucun des points initiaux essayes.

[invite5c27c063]

J'ai vu qu'en optimisation il y avait des méthodes permettant de trouver un minimum global car la methode de DG ne le permet pas.

Enfin, ce qui est exact c'est que le gradient ne donne pas de minimum global mais si la fonction est tout a fait quelconque, je ne crois pas qu'il existe de methode d'optimisation globale. Pour un optimum global, on a souvent l'hypothese que la fonction a minimiser est convexe.

[inviteaeeb6d8b]

Bonsoir,

oui, les méthodes déterministes d'optimisation (minimisation) consistent à descendre dans un creux, il s'agit des méthodes de gradient. Problème : on trouve ainsi un minimum local et non un minimum global.

Il existe un algorithme stochastique d'optimisation globale (algorithme du recuit simulé). J'en donne le principe rapidement dans le cadre de la maximisation d'une application définie sur , à variations bornées, mesurable.

Pour tout strictement positif, on considère la mesure de Boltzmann-Gibbs sur (muni de la tribu borélienne). On peut démontrer (pas trop difficile) que tend vers la mesure de comptage des points qui maximisent . En clair, si on sait simuler la mesure de Boltzmann lorsque est très grand, alors on sait trouver les points qui maximisent .

A fixé, il est plutôt facile de simuler selon en utilisant une méthode MCMC. En gros, on simule pendant un temps long une chaîne de Markov qui admet pour loi invariante.

Le principe de l'algorithme du recuit est de simuler pendant un temps long une chaîne de Markov dont les transitions sont données par la méthode MCMC précédente tout en faisant grandir (suffisamment lentement - en log(n) en fait) le paramètre . On peut démontrer la convergence de l'algorithme (ça, c'est moins évident par contre).

[A voir en vidéo sur Futura]

[invite9c7554e3]

Merci beaucoup tous pour vos réponses!