Groupe d’études et de recherche en analyse des décisions

G-2019-64

Étude du comportement des méthodes BFGS et L-BFGS pour résoudre un sous-problème de région de confiance

, et

Dans ce papier, nous comparons la méthode BFGS à la méthode du gradient conjugué (CG) pour résoudre un problème d'optimisation sans contrainte avec un algorithme de régions de confiance. Le résultat clé est une nouvelle relation entre CG et la classe de Broyden, la classe de méthodes quasi-Newton qui généralise la méthode BFGS. Ce nouveau résultat permet de retrouver ceux établis par Broyden en 1970. Nous étudions ensuite l'utilisation de la méthode BFGS à mémoire limitée (L-BFGS) dans un algorithme de régions de confiance en donnant les mêmes relations qu'entre BFGS et CG. Nous présentons des résultats numériques pour mettre en lumière une différence de performance entre chacune de ces méthodes sur des problèmes mal conditionnés et en grande dimension. Certaines stratégies sont finalement présentées afin d'améliorer la performance de L-BFGS grâce à l'utilisation d'une mémoire variable et d'un facteur de mise à l'échelle.

, 34 pages