Unconstrained derivative-free optimization by successive approximation

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:223

Article

Burmen, Arpad¹  Tuma, Tadej¹ 

[1] Univ Ljubljana, Fac Elect Engn, Trzaska 25, SI-1000 Ljubljana, Slovenia

关键词: Unconstrained minimization;    Direct search;    Successive approximation;    Grid;    Simplex;   

DOI  :  10.1016/j.cam.2007.12.017

来源: Elsevier

【 摘 要 】

We present an algorithmic framework for unconstrained derivative-free optimization based on dividing the search space in regions (partitions). Every partition is assigned a representative point. The representative points form a grid. A piecewiseconstant approximation to the function subject to optimization is constructed using a partitioning and its corresponding grid. The covergence of the framework to a stationary point of a continuously differentiable function is guaranteed under mild assumptions. The proposed framework is appropriate for upgrading heuristics that lack mathematical analysis into algorithms that guarantee convergence to a local minimizer. A convergent variant of the Nelder-Mead algorithm that conforms to the given framework is constructed. The algorithm is compared to two previously published convergent variants of the NM algorithm. The comparison is conducted on the More-Garbow-Hllstrom set of test problems and on four variably-dimensional functions with dimension up to 100. The results of the comparison show that the proposed algorithm outperforms both previously published algorithms. (C) 2007 Elsevier B.V. All rights reserved.

【 授权许可】

Free