Accelerated residual descent methods for solving systems of equations

15 April 2016
12:00 pm
Accelerated residual descent methods for solving systems of equations
Cuong Nguyen
Principal Research Scientist
Aerospace Computational Design Laboratory
Dept. of Aeronautics and Astronautics
MIT

We develop an accelerated residual descent method for solving linear and nonlinear systems of equations. The method is devised by leveraging the past and recent development of accelerated gradient methods in convex optimization. First, we propose a modification of the well-known Nesterov's method to obtain an accelerated residual descent scheme. Next, we equip the scheme with adaptive restarting to improve convergence and robustness. We show that the scheme can be seen as a finite difference approximation of a second-order ODE system, which turns out to coincide with the ODE system derived from Nesterov's method. However, our scheme has a larger step size and thus converges faster than Nesterov's method. We then propose an adaptive selection of the extrapolation parameter to further improve the convergence rate of our scheme. Finally, we generalize the scheme to encompass a family of accelerated residual descent methods, thereby providing an opportunity to devise superior methods. We demonstrate the method on systems of equations resulting from the finite element approximation of linear and nonlinear partial different equations. Numerical results show that the proposed method outperforms both Nesterov's method and Newton-GMRES method on the test cases considered.