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

M. Powell ()

Computational Optimization and Applications, 2012, vol. 53, issue 2, 527-555

Abstract: We consider iterative trust region algorithms for the unconstrained minimization of an objective function $F ( \underline{x})$ , $\underline{x}\in \mathcal{R}^{n}$ , when F is differentiable but no derivatives are available, and when each model of F is a linear or a 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, if ∇ 2 F is also bounded, and if the number of iterations is infinite, then the sequence of gradients $\underline{\nabla}F ( \underline{x}_{\,k} )$ , k=1,2,3,…, converges to zero, where $\underline{x}_{\,k}$ is the centre of the trust region of the k-th iteration. Copyright Springer Science+Business Media, LLC 2012

Keywords: Convergence theory; Derivative free optimization; Symmetric Broyden; Trust region methods; Unconstrained minimization (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-012-9483-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:53:y:2012:i:2:p:527-555

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-012-9483-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().