Optimisation stochastique. Choix des lois de perturbations. Application au reseau itineris.

Résumé L'algorithme de gradient stochastique comme le recuit simule sont des perturbations d'algorithmes de descente locale. La loi des perturbations doit-elle etre a queue exponentielle (choix classique pour le recuit simule) ou au contraire a decroissance lente ? notre analyse theorique du gradient stochastique sans contrainte avec des perturbations de gauss, puis de cauchy, montre que dans les deux cas une decroissance correcte des parametres assure une exploration efficace, avec des domaines d'application differents: la deuxieme variante est moins precise mais plus rapide, donc adaptee a des problemes de complexite moderee. La deuxieme partie de cette these illustre cette discussion par une application a l'optimisation du reseau de telephone cellulaire itineris: une implementation fondee sur le recuit simule est comparee avec une variante ou la loi de transition de metropolis, a decroissance exponentielle, est remplacee par une loi de transition a decroissance plus lente.