Séminaire

Le récent algorithme ARC possède une propriété remarquable, une complexité en pire cas optimale. Après une mise en contexte sur les notions de vitesse de convergence et de complexité en pire cas, nous présentons un point de vue unifié des méthodes de région de confiance et de régularisation cubique adaptative (ARC). Bien que les liens entre ces deux familles aient été mentionnés dans l’article qui introduit ARC, nous poussons plus loin l’analogie et en déduisons une démonstration de convergence globale plus simple et unifiée. Nous soulignons également les faits importants de la complexité en pire cas qui s’avère optimale pour notre nouvelle variante ARCq, mais pas pour les algorithmes de région de confiance. ARCq, se prête bien à des implémentations efficaces et nous en présentons deux, une matricielle de type Cholesky et une itérative basée sur des algorithmes de type Krylov , cette dernière variante peut résoudre des problèmes de très grande taille. Quelques illustrations numériques seront également présentées.