Méthodes Newton régulières multiniveaux avec des taux de convergence rapides

Nous introduisons de nouvelles méthodes multiniveaux pour résoudre des problèmes d'optimisation non contraints à grande échelle. Plus précisément, la philosophie des méthodes multiniveaux est appliquée aux méthodes de type Newton qui régularisent le sous-problème de Newton en utilisant des informations de second ordre issues d'un sous-problème grossier (de faible dimension). Les nouvelles méthodes multiniveaux régularisées convergent prouvablement à partir de tout point d'initialisation et bénéficient de taux de convergence plus rapides que la descente de gradient. En particulier, pour des fonctions arbitraires avec des Hessiennes continues de Lipschitz, nous montrons que leur taux de convergence s'interpole entre le taux de la descente de gradient et celui de la méthode de Newton cubique. Si, de plus, on suppose que la fonction objective est convexe, alors la méthode proposée converge avec un taux rapide O (k^-2). Ainsi, puisque les mises à jour sont générées à l'aide d'un modèle grossier en faible dimension, les résultats théoriques de cet article accélèrent significativement la convergence des méthodes de type Newton ou des méthodes de gradient préconditionnées dans des applications pratiques. Des résultats numériques préliminaires suggèrent que les algorithmes multiniveaux proposés sont significativement plus rapides que les méthodes actuelles à la pointe de la technologie.