On the global convergence of trust region algorithms for unconstrained minimization. (English) Zbl 0569.90069

This paper presents and proves a result on the convergence of trust region algorithms for unconstrained minimization. The result gives a condition on the norms of the approximations to the Hessian matrix which ensures convergence.
Specifically, the problem min F(x), \(x\in R^ n\), is considered. The general trust region algorithm and auxiliary assumptions are defined precisely in the paper. The algorithm involves iteration of the form \(x_{k+1}=x_ k+\delta_ k\) where \(\delta_ k\) is usually chosen to satisfy \(\phi_ k(x_ k+\delta_ k)<F(x_ k)\), where \(\phi_ k\) is the quadratic model: \(\phi_ k(x_ k+\delta)=F(x_ k)+\delta^ Tg_ k+(1/2)\delta^ TB_ k\delta\). Here, \(g_ k=\nabla F(x_ k)\), and \(B_ k\) is some approximation to the Hessian matrix of F.
Loosely, the result is: if \(| B_ k| \leq c_ 1+c_ 2k\), then \(\lim \inf_{k\to \infty}| g_ k| =0\). The result sharpens a previously published result by the author [Nonlin. Program. 2, Proc. Math. Program. Symp., Madison 1974, 1-27 (1975; Zbl 0321.90045)].
Reviewer: B.Kearfott


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


Zbl 0321.90045
Full Text: DOI


[1] R. Fletcher,Practical methds of optimization, Volume 1: Unconstrained optimization (Wiley, Chichester, 1980). · Zbl 0439.93001
[2] M.J.D. Powell, ”Convergence properties of a class of minimization algorithms”, in: O.L. Managasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 2 (Academic Press, New York, 1975). · Zbl 0321.90045
[3] D.C. Sorensen, ”An example concerning quasi-Newton estimation of a sparse Hessian”,SIGNUM Newsletter 16(2) (1981) 8–10. · doi:10.1145/1057562.1057564
[4] D.C. Sorensen, ”Trust region methods for unconstrained optimization” in: M.J.D. Powell ed.,Nonlinear Optimization 1981 (Academic Press, London, 1982). · Zbl 0571.90081
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.