Advanced Modeling and Optimization

Abstract for Paper 6 of Volume 5, Number 3, 2003, pp. 223-245


A Newton Method with a Two-dimensional Line Search

M.C.Bartholomew-Biggs
Numerical Optimisation Centre, Mathematics Department,
University of Hertfordshire, College Lane, Hatfield AL10 9AB, England
Email: matqmb@herts.ac.uk

 



Abstract
This paper deals with a modified version of Newton's method for unconstrained minimization in which a search direction of the form s = - ag + ß p is obtained by fitting a quadratic model to the objective function in the plane of the Newton direction p and the steepest descent direction -g. This composite search direction can be used as a fall-back option when the standard Newton step proves ineffective - e.g., when the Hessian matrix is not positive definite and p represents a move towards a saddle point or maximum. The method proposed for determining a and ß resembles a two variable trust-region approach. Two prototype algorithms are discussed: one uses s in a trust-region framework and the other performs a line search. In both methods the computational overheads are comparable with those for a standard Newton method because only one linear system needs to be solved per iteration.

Keywords: Unconstrained minimization, Newton method, Two-dimensional Line Search.