1er Symposium canadien en analyse numérique et calcul scientifique
Extending Preconditioned GMRES to Nonlinear Optimization
De Sterck, Hans
Department of Applied Mathematics, University of Waterloo

Preconditioned GMRES is a powerful iterative method for linear systems. In this talk, I will show how the concept of preconditioned GMRES can be extended to the general class of nonlinear optimization problems, using genuinely nonlinear preconditioners. I will present a nonlinear GMRES (N-GMRES) optimization method, which combines preliminary iterates generated by a stand-alone simple optimization method (the nonlinear preconditioner) to produce accelerated iterates in a generalized Krylov space. The nonlinear acceleration process, which is closely related to existing acceleration methods for nonlinear systems that include so-called Anderson acceleration, is combined with a line search in every step to obtain a general nonlinear optimization method for which global convergence can be proved when steepest-descent preconditioning is used. Numerical tests show that N-GMRES is competitive with established nonlinear optimization methods, and outperforms them for a difficult canonical tensor approximation problem when an advanced nonlinear preconditioner is used. This suggests that the real power of N-GMRES may lie in its ability to use powerful problem-dependent nonlinear preconditioners. Extension of these ideas to nonlinear preconditioning for the nonlinear CG optimization method is also discussed, and results are presented showing the effectiveness of the approach.

Lundi, 17 juin, 16h00
Salle Des Plaines C