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

K. Scheinberg, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

61 Downloads (Pure)

Résumé

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.
langue originaleAnglais
Pages (de - à)3512-3532
Nombre de pages21
journalSIAM Journal on Optimization
Volume20
Numéro de publication6
Les DOIs
étatPublié - 1 janv. 2010

Empreinte digitale

Derivative-free Optimization
Unconstrained Optimization
Interpolation
Interpolate
Model-based
Derivatives
Geometry
Global Convergence
Trust Region
Function evaluation
Stationary point
Evaluation Function
Criticality
Applied mathematics
Maintenance
Objective function
Iteration
Numerical Results
Model

Citer ceci

@article{0af88b3e38214b1f909d183e0cce563e,
title = "Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization",
abstract = "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. {\circledC} 2010 Society for Industrial and Applied Mathematics.",
keywords = "derivative-free optimization, geometry of the interpolation set, unconstrained minimization",
author = "K. Scheinberg and Philippe Toint",
note = "Publication code : FP SB010/2009/06 ; QA 0002.2/001/09/06",
year = "2010",
month = "1",
day = "1",
doi = "10.1137/090748536",
language = "English",
volume = "20",
pages = "3512--3532",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "6",

}

Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization. / Scheinberg, K.; Toint, Philippe.

Dans: SIAM Journal on Optimization, Vol 20, Numéro 6, 01.01.2010, p. 3512-3532.

Résultats de recherche: Contribution à un journal/une revueArticle

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

VL - 20

SP - 3512

EP - 3532

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 6

ER -