Exploiting problem structure in pattern search methods for unconstrained optimization

Chris Price; Philippe Toint

doi:10.1080/10556780500137116

Exploiting problem structure in pattern search methods for unconstrained optimization

Chris Price, Philippe Toint

Département de Mathématique

Résultats de recherche: Contribution à un journal/une revue › Article

16 Downloads (Pure)

Résumé

A direct search method for unconstrained optimization is described. The method makes use of any partial separability structure that the objective function may have. The method uses successively finer nested grids, and minimizes the objective function over each grid in turn. All grids are aligned with the coordinate directions, which allows the partial separability structure of the objective function to be exploited. This has two advantages: it reduces the work needed to calculate function values at the points required and it provides function values at other points as a free by-product. Numerical results show that using partial separability can dramatically reduce the number of function evaluations needed to minimize a function, in some cases allowing problems with thousands of variables to be solved. Results show that the algorithm is effective on strictly C 1 problems and on a class of non-smooth problems.

langue originale	Anglais
Pages (de - à)	479-491
Nombre de pages	13
journal	Optimization Methods and Software
Volume	21
Numéro de publication	3
Les DOIs	https://doi.org/10.1080/10556780500137116
état	Publié - 1 juin 2006

Empreinte digitale

Pattern Search

Unconstrained Optimization

Separability

Search Methods

Objective function

Grid

Partial

Value Function

Direct Search Method

Minimise

Evaluation Function

Strictly

Calculate

Numerical Results

Function evaluation

Byproducts

Citer ceci

Price, C., & Toint, P. (2006). Exploiting problem structure in pattern search methods for unconstrained optimization. Optimization Methods and Software, 21(3), 479-491. https://doi.org/10.1080/10556780500137116

Price, Chris ; Toint, Philippe. / Exploiting problem structure in pattern search methods for unconstrained optimization. Dans: Optimization Methods and Software. 2006 ; Vol 21, Numéro 3. p. 479-491.

@article{43a0751b453640db85cf08237a7f4596,

title = "Exploiting problem structure in pattern search methods for unconstrained optimization",

abstract = "A direct search method for unconstrained optimization is described. The method makes use of any partial separability structure that the objective function may have. The method uses successively finer nested grids, and minimizes the objective function over each grid in turn. All grids are aligned with the coordinate directions, which allows the partial separability structure of the objective function to be exploited. This has two advantages: it reduces the work needed to calculate function values at the points required and it provides function values at other points as a free by-product. Numerical results show that using partial separability can dramatically reduce the number of function evaluations needed to minimize a function, in some cases allowing problems with thousands of variables to be solved. Results show that the algorithm is effective on strictly C 1 problems and on a class of non-smooth problems.",

keywords = "derivative-free, pattern search, numerical results, partial separability",

author = "Chris Price and Philippe Toint",

note = "Publication code : #QA 0002.2/001/04/01 ; *FP SB010/2004/01",

year = "2006",

month = "6",

day = "1",

doi = "10.1080/10556780500137116",

language = "English",

volume = "21",

pages = "479--491",

journal = "Optimization Methods and Software",

issn = "1055-6788",

publisher = "Taylor & Francis",

number = "3",

}

Price, C & Toint, P 2006, 'Exploiting problem structure in pattern search methods for unconstrained optimization', Optimization Methods and Software, VOL. 21, Numéro 3, p. 479-491. https://doi.org/10.1080/10556780500137116

Exploiting problem structure in pattern search methods for unconstrained optimization. / Price, Chris; Toint, Philippe.

Dans: Optimization Methods and Software, Vol 21, Numéro 3, 01.06.2006, p. 479-491.

Résultats de recherche: Contribution à un journal/une revue › Article

TY - JOUR

T1 - Exploiting problem structure in pattern search methods for unconstrained optimization

AU - Price, Chris

AU - Toint, Philippe

N1 - Publication code : #QA 0002.2/001/04/01 ; *FP SB010/2004/01

PY - 2006/6/1

Y1 - 2006/6/1

N2 - A direct search method for unconstrained optimization is described. The method makes use of any partial separability structure that the objective function may have. The method uses successively finer nested grids, and minimizes the objective function over each grid in turn. All grids are aligned with the coordinate directions, which allows the partial separability structure of the objective function to be exploited. This has two advantages: it reduces the work needed to calculate function values at the points required and it provides function values at other points as a free by-product. Numerical results show that using partial separability can dramatically reduce the number of function evaluations needed to minimize a function, in some cases allowing problems with thousands of variables to be solved. Results show that the algorithm is effective on strictly C 1 problems and on a class of non-smooth problems.

AB - A direct search method for unconstrained optimization is described. The method makes use of any partial separability structure that the objective function may have. The method uses successively finer nested grids, and minimizes the objective function over each grid in turn. All grids are aligned with the coordinate directions, which allows the partial separability structure of the objective function to be exploited. This has two advantages: it reduces the work needed to calculate function values at the points required and it provides function values at other points as a free by-product. Numerical results show that using partial separability can dramatically reduce the number of function evaluations needed to minimize a function, in some cases allowing problems with thousands of variables to be solved. Results show that the algorithm is effective on strictly C 1 problems and on a class of non-smooth problems.

KW - derivative-free

KW - pattern search

KW - numerical results

KW - partial separability

UR - http://www.scopus.com/inward/record.url?scp=30944446857&partnerID=8YFLogxK

U2 - 10.1080/10556780500137116

DO - 10.1080/10556780500137116

M3 - Article

VL - 21

SP - 479

EP - 491

JO - Optimization Methods and Software