Trouver des minima globaux via des approximations de noyaux.

Résumé Nous considérons la minimisation globale de fonctions lisses basée uniquement sur des évaluations de fonctions. Les algorithmes qui atteignent le nombre optimal d'évaluations de fonctions pour un niveau de précision donné reposent généralement sur la construction explicite d'une approximation de la fonction, qui est ensuite minimisée par des algorithmes dont la complexité est exponentielle. Dans cet article, nous considérons une approche qui modélise conjointement la fonction à approximer et trouve un minimum global. Ceci est réalisé en utilisant des sommes infinies de fonctions lisses carrées et a des liens forts avec les hiérarchies de sommes de carrés polynomiales. En exploitant les propriétés de représentation récentes des espaces de Hilbert à noyau reproducteur, le problème d'optimisation en dimension infinie peut être résolu par sous-échantillonnage en temps polynomial par rapport au nombre d'évaluations de la fonction, et avec des garanties théoriques sur le minimum obtenu. Pour $n$ échantillons, le coût de calcul est de $O(n^{3.5})$ en temps, $O(n^2)$ en espace, et nous obtenons un taux de convergence vers l'optimum global de $O(n^{-m/d + 1/2 + 3/d})$ où $m$ est le degré de différentiabilité de la fonction et $d$ le nombre de dimensions. Ce taux est presque optimal dans le cas des fonctions de Sobolev et plus généralement rend la méthode proposée particulièrement adaptée aux fonctions qui ont un grand nombre de dérivées. En effet, lorsque $m$ est de l'ordre de $d$, le taux de convergence vers l'optimum global ne souffre pas de la malédiction de la dimensionnalité, qui n'affecte que les constantes du pire cas (que nous suivons explicitement tout au long de l'article).