© 2003 by Institute of Mathematics and its Applications
Alternate minimization gradient method
1 State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, PO Box 2719, Beijing 100080, People's Republic of China
It is well known that the minimization of a smooth function f(x) is equivalent to minimizing its gradient norm ||g(x)||2 in some sense. In this paper, we propose a modified steepest descent method, whose stepsizes alternately minimize the function value and the gradient norm along the line of steepest descent. Hence the name ‘alternate minimization (AM) gradient method’. For strictly convex quadratics, the AM method is proved to be Q-superlinearly convergent in two dimensions, and Q-linearly convergent in any dimension. Numerical experiments are presented for symmetric and positive definite linear systems. They suggest that the AM method is much better than the classical steepest descent (SD) method and comparable with some existing gradient methods. They also show that the AM method is an efficient alternative if a solution with a low precision is required. Two variants of the AM method, named shortened SD step gradient methods, are also presented and analysed in this paper. By designing a new kind of line search, the two variants are extended to the field of unconstrained optimization.
Key Words: linear system; unconstrained optimization; gradient method; monotonic and nonmonotonic; convergence rate; line search
Received 5 February 2002. Revised 11 September 2002.