Finding local optima of high-dimensional functions using direct search methods

被引:34
作者
Hvattum, Lars Magnus [1 ]
Glover, Fred [2 ]
机构
[1] Norwegian Univ Sci & Technol, N-7034 Trondheim, Norway
[2] Univ Colorado, Boulder, CO 80309 USA
关键词
Non-linear optimization; Local minimum; Derivative free; Direct search; Scatter Search; GLOBAL OPTIMIZATION; SCATTER SEARCH; TABU SEARCH; PATTERN SEARCH; ALGORITHMS; LINKS;
D O I
10.1016/j.ejor.2008.01.039
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper focuses on a subclass of box-constrained, non-linear optimization problems. We are particularly concerned with settings where gradient information is unreliable, or too costly to calculate, and the function evaluations themselves are very costly. This encourages the use of derivative free optimization methods, and especially a subclass of these referred to as direct search methods. The thrust of our investigation is twofold. First, we implement and evaluate a number of traditional direct search methods according to the premise that they should be suitable as local optimizers when used in a metaheuristic framework. Second, we introduce a new direct search method, based on Scatter Search, designed to remedy the lack of a good derivative free method for solving problems of high dimensions. Our new direct search method has convergence properties comparable to those of existing methods in addition to being able to solve larger problems more effectively. (c) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:31 / 45
页数:15
相关论文
共 39 条
[1]  
Abramson M.A., 2006, SIAGOPTIMIZATION VIE, V17, P2
[2]   Mesh adaptive direct search algorithms for constrained optimization [J].
Audet, C ;
Dennis, JE .
SIAM JOURNAL ON OPTIMIZATION, 2006, 17 (01) :188-217
[3]   Analysis of generalized pattern searches [J].
Audet, C ;
Dennis, JE .
SIAM JOURNAL ON OPTIMIZATION, 2003, 13 (03) :889-903
[4]   A hybrid method combining continuous tabu search and Nelder-Mead simplex algorithms for the global optimization of multiminima functions [J].
Chelouah, R ;
Siarry, P .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 161 (03) :636-654
[5]   Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions [J].
Chelouah, R ;
Siarry, P .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 148 (02) :335-348
[6]   Recent progress in unconstrained nonlinear optimization without derivatives [J].
Conn, AR ;
Scheinberg, K ;
Toint, PL .
MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) :397-414
[7]  
DOLAN ED, 1999, THESIS
[8]   FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE [J].
GLOVER, F .
COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :533-549
[9]  
Glover F, 2000, CONTROL CYBERN, V29, P653
[10]   TABU SEARCH FOR NONLINEAR AND PARAMETRIC OPTIMIZATION (WITH LINKS TO GENETIC ALGORITHMS) [J].
GLOVER, F .
DISCRETE APPLIED MATHEMATICS, 1994, 49 (1-3) :231-255