IMA Journal of Numerical Analysis Advance Access published online on September 25, 2009
IMA Journal of Numerical Analysis, doi:10.1093/imanum/drp021
On the convergence of a wide range of trust region methods for unconstrained optimization
Department of Applied Mathematics and Theoretical Physics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WA, UK
Email: mjdp{at}cam.ac.uk
Received on 9 May 2008. Revised on 5 February 2009.
 |
Abstract |
|---|
We consider trust region methods for seeking the unconstrained minimum of an objective function F(
), 
, when the gradient 
F(), , is available. The methods are iterative with 1 being given. The new vector of variables k+1 is derived from a quadratic approximation to F that interpolates F(k) and F(k), where k is the iteration number. The second derivative matrix of the quadratic approximation, Bk say, can be indefinite, because the approximation is employed only if the vector of variables satisfies || – k|| 
k, where k is a "trust region radius" that is adjusted automatically. Thus the approximation is useful if ||F(k)|| is sufficiently large and if ||Bk|| and k are sufficiently small. It is proved under mild assumptions that the condition ||F(k+1)|| 
is achieved after a finite number of iterations, where is any given positive constant, and then it is usual to end the calculation. The assumptions include a Lipschitz condition on F and also F has to be bounded below. The termination property is established in a single theorem that applies to a wide range of trust region methods that force the sequence F(k), k = 1, 2, 3, ..., to decrease monotonically. Any choice of each symmetric matrix Bk is allowed, provided that ||Bk|| is bounded above by a constant multiple of k.
Key Words: convergence analysis; Quasi-Newton algorithms; trust region methods; unconstrained optimization
Dedicated to Ron Mitchell with special thanks for many kindnesses.