Convergence d'un algorithme de gradient stochastique projeté multi-agents pour l'optimisation non convexe.

Résumé Nous introduisons un nouveau cadre pour l'analyse de la convergence d'une classe d'algorithmes d'optimisation non convexe avec contraintes distribuées dans les systèmes multi-agents. Le but est de rechercher des minimiseurs locaux d'une fonction objectif non-convexe qui est supposée être une somme de fonctions d'utilité locales des agents. L'algorithme étudié se compose de deux étapes : une descente de gradient stochastique locale à chaque agent et une étape de commérage qui conduit le réseau d'agents à un consensus. Sous l'hypothèse d'une taille de pas décroissante, il est prouvé que le consensus est asymptotiquement atteint dans le réseau et que l'algorithme converge vers l'ensemble des points de Karush-Kuhn-Tucker. Une caractéristique importante de l'algorithme est qu'il ne nécessite pas la double stochasticité des matrices de commérage. Il convient en particulier à un scénario de diffusion naturelle pour lequel aucun message de retour entre agents n'est requis. Il est prouvé que nos résultats sont également valables si le nombre de communications dans le réseau par unité de temps disparaît à une vitesse modérée lorsque le temps augmente, ce qui permet d'économiser l'énergie du réseau. Les applications à l'allocation de puissance dans les réseaux ad-hoc sans fil sont discutées. Enfin, nous fournissons des résultats numériques qui confirment nos affirmations.