TY - JOUR
T1 - Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization
AU - Scheinberg, K.
AU - Toint, Philippe
N1 - Publication code : FP SB010/2009/06 ; QA 0002.2/001/09/06
PY - 2010/1/1
Y1 - 2010/1/1
N2 - Several efficient methods for derivative-free optimization 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 we also provide an algorithm where such steps occur only 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 [Optim. Methods Softw., 24 (2009), pp. 145-154] for a method where no care is ever taken to guarantee poisedness of the interpolation set. © 2010 Society for Industrial and Applied Mathematics.
AB - Several efficient methods for derivative-free optimization 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 we also provide an algorithm where such steps occur only 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 [Optim. Methods Softw., 24 (2009), pp. 145-154] for a method where no care is ever taken to guarantee poisedness of the interpolation set. © 2010 Society for Industrial and Applied Mathematics.
KW - derivative-free optimization
KW - geometry of the interpolation set
KW - unconstrained minimization
UR - http://www.scopus.com/inward/record.url?scp=79251516126&partnerID=8YFLogxK
U2 - 10.1137/090748536
DO - 10.1137/090748536
M3 - Article
SN - 1095-7189
VL - 20
SP - 3512
EP - 3532
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 6
ER -