The ”global” convergence of Broyden-like methods with a suitable line search. (English) Zbl 0596.65034

Griewank, Andreas

J. Aust. Math. Soc., Ser. B 28, 75-92 (1986).

Summary: Iterative methods for solving a square system of nonlinear equations \(g(x)=0\) often require that the sum of squares residual \(\gamma (x)\equiv \| g(x)\|^ 2\) be reduced at each step. Since the gradient of \(\gamma\) depends on the Jacobian \(\nabla g\), this stabilization strategy is not easily implemented if only approximations \(B_ k\) to \(\nabla g\) are available. Therefore most quasi-Newton algorithms either include special updating steps or reset \(B_ k\) to a divided difference estimate of \(\nabla g\) whenever no satisfactory progress is made. Here the need for such back-up devices is avoided by a derivative-free line search in the range of g. Assuming that the \(B_ k\) are generated from an arbitrary \(B_ 0\) by fixed scale updates, we establish superlinear convergence from within any compact level set of \(\gamma\) on which g has a differentiable inverse function \(g^{-1}\).

MSC:

65H10	Numerical computation of solutions to systems of equations
65K05	Numerical mathematical programming methods

Keywords:

Broyden-like methods; Iterative methods; quasi-Newton algorithms; derivative-free line search; superlinear convergence