A curvilinear search using tridiagonal secant updates for unconstrained optimization

Abstract

The idea of doing a curvilinear search along the Levenberg- Marquardt path s(μ) = - (H + μI)⁻¹g always has been appealing, but the cost of solving a linear system for each trial value of the parameter y has discouraged its implementation. In this paper, an algorithm for searching along a path which includes s(μ) is studied. The algorithm uses a special inexpensive QTcQT to QT₊QT Hessian update which trivializes the linear algebra required to compute s(μ). This update is based on earlier work of Dennis-Marwil and Martinez on least-change secant updates of matrix factors. The new algorithm is shown to be local and q-superlinearily convergent to stationary points, and to be globally q-superlinearily convergent for quasi-convex functions. Computational tests are given that show the new algorithm to be robust and efficient.