Optimization Online


Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization

Katya Scheinberg(katyas***at***us.ibm.com)
Philippe L. Toint(philippe.toint***at***fundp.ac.be)

Abstract: Several efficient methods for derivative-free optimization (DFO) are based on the construction and maintenance of an interpolation model for the objective function. Most of these algorithms use special ``geometry-improving'' iterations, where the geometry (poisedness) of the underlying interpolation set is made better at the cost of one or more function evaluations. We show that such geometry improvements cannot be completely eliminated if one wishes to ensure global convergence, but also provide an algorithm where such steps only occur in the final stage of the algorithm where criticality of a putative stationary point is verified. Global convergence for this method is proved by making use of a self-correction mechanism inherent to the combination of trust regions and interpolation models. This mechanism also throws some light on the surprisingly good numerical results reported by Fasano, Morales and Nocedal for a method where no care is ever taken to guarantee poisedness of the interpolation set.

Keywords: derivative-free optimization, geometry of the interpolation set, unconstrained minimization

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Other Topics (Optimization of Simulated Systems )

Citation: Report TR09/06, Department of Mathematics, FUNDP- University of Namur, Namur, Belgium, 2009

Download: [PDF]

Entry Submitted: 02/02/2009
Entry Accepted: 02/02/2009
Entry Last Modified: 02/02/2009

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