Group for Research in Decision Analysis

G-2018-50

The conjugate residual method in linesearch and trust-region methods

and

The minimum residual method (MINRES) of Paige and Saunders (1975), which is often the method of choice for symmetric linear systems, is a generalization of the method of conjugate residuals (CR), proposed by Hestenes and Stiefel (1952). Like the conjugate gradient method (CG), CR possesses properties that are desirable for unconstrained optimization, but is only defined for symmetric positive-definite operators. CR's main property, that it minimizes the residual, is particularly appealing in inexact Newton methods, typically used in a linesearch context. CR is also relevant in a trust-region context as it causes monotonic decrease of convex quadratic models (Fong and Saunders, 2012). We investigate modifications that make CR suitable, even in the presence of negative curvature, and perform comparisons on convex and nonconvex problems with the conjugate gradient method. We complete our investigation with an extension suitable for nonlinear least-squares problems. Our experiments reveal that CR performs as well as or better than CG, and mainly yields savings in operator-vector products.

, 35 pages

This cahier was revised in March 2019