A Restart MPRP Conjugate Gradient Method And Its N-Step Quadratic Convergence

The PRP method is one of the most famous conjugate gradient methods. Itis well-known that the PRP method with exact line search is globally and linearlyconvergent. If some restart strategy is adopted, the convergence rate of the methodcan be n-step superlinear/quadratic. Recently, a so-called modified PRP (MPRP)method is proposed. The MPRP method with some inexact line search is also globallyconvergent. The purpose of this paper is to investigate the convergence rate of theMPRP method with inexact line search.In Chapter 2, we first show that the MPRP method with Armijo line searchor Wolfe line search is linearly convergent. In order to improve the e-ciency of theMPRP method, we derive an estimate to the exact line search steplength and useit as the initial steplength in the inexact line search. We then introduce a restartstrategy in the MPRP method and propose a restart MPRP method (called RMPRPmethod). Under appropriate conditions, we show that the RMPRP method is globallyconvergent. Moreover, it retains n-step superlinear/quadratic convergence property.Finally, we do extensive numerical experiments to test the performance of theproposed RMPRP method. We first test the quadratic convergence of the RMPRPmethod on some small problems. The results show that the restart MPRP methoddoes converge quadratically. We then compare the performance of the RMPRP methodwith that of the ordinary MPRP method (without use of restart strategy). We comparethem in the CPU time used, the number of function evaluations and the number of thegradient evaluations. The results show that the proposed RMPRP method outperformsthe ordinary MRPR method.