Optimization Online


On the convergence of trust region algorithms for unconstrained minimization without derivatives

MJD Powell(mjdp***at***cam.ac.uk)

Abstract: We consider iterative trust region algorithms for the unconstrained minimization of an objective function F(x) of n variables, when F is differentiable but no derivatives are available, and when each model of F is a linear or quadratic polynomial. The models interpolate F at n+1 points, which defines them uniquely when they are linear polynomials. In the quadratic case, second derivatives of the models are derived from information from previous iterations, but there are so few data that typically only the magnitudes of second derivative estimates are correct. Nevertheless, numerical results show that much faster convergence is achieved when quadratic models are employed instead of linear ones. Just one new value of F is calculated on each iteration. Changes to the variables are either trust region steps or are designed to maintain suitable volumes and diameters of the convex hulls of the interpolation points. It is proved that, if F is bounded below with bounded second derivatives, and if the number of iterations is infinite, then the sequence of gradients grad F(x_k), k=1,2,3,..., converges to zero, where x_k is the centre of the trust region of the k-th iteration.

Keywords: Convergence theory, Derivative free optimization, Symmetric Broyden, Trust region methods, Unconstrained minimization.

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Report DAMTP 2011/NA01, Centre for Mathematical Sciences, University of Cambridge, UK (January, 2011).

Download: [PDF]

Entry Submitted: 01/14/2011
Entry Accepted: 01/14/2011
Entry Last Modified: 01/14/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society