Optimizing radial basis functions by d.c. programming and its use in direct search for global derivative-free optimization. (English) Zbl 1267.90110
Summary: We address the global optimization of functions subject to bound and linear constraints without using derivatives of the objective function. We investigate the use of derivative-free models based on radial basis functions (RBFs) in the search step of direct-search methods of directional type. We also study the application of algorithms based on difference of convex (d.c.) functions programming to solve the resulting subproblems which consist of the minimization of the RBF models subject to simple bounds on the variables. Extensive numerical results are reported with a test set of bound and linearly constrained problems.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
global optimization; derivative-free optimization; direct-search methods; search step; radial basis functions; d.c. programming; DCAReferences:
| [1] | Ali MM, Khompatraporn C, Zabinsky ZB (2005) A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J Glob Optim 31:635–672 · Zbl 1093.90028 · doi:10.1007/s10898-004-9972-2 |
| [2] | Le Thi HA, Pham Dinh T (1997) Convex analysis approach to d.c. programming: theory, algorithms and applications. Acta Math Vietnam 22:289–355 · Zbl 0895.90152 |
| [3] | Le Thi HA, Pham Dinh T (1998) D.C. optimization algorithms for solving the trust-region subproblem. SIAM J Optim 8:476–505 · Zbl 0913.65054 · doi:10.1137/S1052623494274313 |
| [4] | Le Thi HA, Pham Dinh T (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133:23–46 · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1 |
| [5] | Björkman M, Holmström K (2000) Global optimization of costly nonconvex functions using radial basis functions. Optim Eng 1:373–397 · Zbl 1035.90061 · doi:10.1023/A:1011584207202 |
| [6] | Conn AR, Scheinberg K, Vicente LN (2009) Introduction to derivative-free optimization. MPS-SIAM series on optimization. SIAM, Philadelphia |
| [7] | Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201–213 · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [8] | Fourer R, Gay DM, Kernighan BW (1990) A modeling language for mathematical programming. Manag Sci 36:519–554 · Zbl 0701.90062 · doi:10.1287/mnsc.36.5.519 |
| [9] | Griffin JD, Kolda TG (2010) Asynchronous parallel hybrid optimization combining DIRECT and GSS. Optim Methods Softw 25:797–817 · Zbl 1198.90397 · doi:10.1080/10556780903039893 |
| [10] | Gutmann H-M (2001) A radial basis function method for global optimization. J Glob Optim 19:201–227 · Zbl 0972.90055 · doi:10.1023/A:1011255519438 |
| [11] | Hedar A-R, Fukushima M (2004) Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization. Optim Methods Softw 19:291–308 · Zbl 1059.90149 · doi:10.1080/10556780310001645189 |
| [12] | Ingber L, Rosen B (1992) Genetic algorithms and very fast simulated reannealing: a comparison. Math Comput Model 16:87–100 · Zbl 0791.68138 · doi:10.1016/0895-7177(92)90108-W |
| [13] | Ji Y, Zhang K-C, Qu S-J (2006) A deterministic global optimization algorithm. Appl Math Comput 185:382–387 · Zbl 1114.65062 · doi:10.1016/j.amc.2006.06.101 |
| [14] | Jones D, Perttunen C, Stuckman B (1993) Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79:157–181 · Zbl 0796.49032 · doi:10.1007/BF00941892 |
| [15] | Käck J-E (2004) Constrained global optimization with radial basis functions. Technical report research report MdH-IMa-2004, Department of Mathematics and Physics, Mälardalen University, Västerås, Sweden |
| [16] | Kiseleva E, Stepanchuk T (2003) On the efficiency of a global non-differentiable optimization algorithm based on the method of optimal set partitioning. J Glob Optim 25:209–235 · Zbl 1030.90088 · doi:10.1023/A:1021931422223 |
| [17] | Kolda TG, Lewis RM, Torczon V (2003) Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev 45:385–482 · Zbl 1059.90146 · doi:10.1137/S003614450242889 |
| [18] | Locatelli M (2003) A note on the Griewank test function. J Glob Optim 25:169–174 · Zbl 1030.90118 · doi:10.1023/A:1021956306041 |
| [19] | Locatelli M, Schoen F (2002) Fast global optimization of difficult Lennard–Jones clusters. Comput Optim Appl 21:55–70 · Zbl 0988.90054 · doi:10.1023/A:1013596313166 |
| [20] | Michalewicz Z (1994) Evolutionary computation techniques for nonlinear programming problems. Int Trans Oper Res 1:223–240 · Zbl 0854.90129 · doi:10.1016/0969-6016(94)90022-1 |
| [21] | Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, Berlin · Zbl 0841.68047 |
| [22] | Mongeau M, Karsenty H, Rouzé V, Hiriart-Urruty J-B (2000) Comparison of public-domain software for black box global optimization. Optim Methods Softw 13:203–226 · Zbl 0963.90062 · doi:10.1080/10556780008805783 |
| [23] | Moré JJ, Wild SM (2009) Benchmarking derivative-free optimization algorithms. SIAM J Optim 20:172–191. www.mcs.anl.gov/\(\sim\)more/dfo · Zbl 1187.90319 · doi:10.1137/080724083 |
| [24] | Oeuvray R (2005) Trust-region methods based on radial basis functions with application to biomedical imaging. PhD thesis, Institut de Mathématiques, École Polytechnique Fédérale de Lausanne, Switzerland |
| [25] | Oeuvray R, Bierlaire M (2009) BOOSTERS: a derivative-free algorithm based on radial basis functions. Int J Model Simul 29:4634–4636 |
| [26] | Parsopoulos KE, Plagianakos VP, Magoulas GD, Vrahatis MN (2001) Stretching technique for obtaining global minimizers through particle swarm optimization. In: Proc of the particle swarm optimization workshop, Indianapolis, USA, pp 22–29 |
| [27] | Pham Dinh T, Elbernoussi S (1988) Duality in d.c. (difference of convex functions) optimization. In: Subgradient methods, vol 84. Birkhäuser, Basel, pp 276–294 |
| [28] | Regis RG, Shoemaker CA (2005) Constrained global optimization of expensive black box functions using radial basis functions. J Glob Optim 31:153–171 · Zbl 1274.90511 · doi:10.1007/s10898-004-0570-0 |
| [29] | Regis RG, Shoemaker CA (2007a) Improved strategies for radial basis function methods for global optimization. J Glob Optim 37:113–135 · Zbl 1149.90120 · doi:10.1007/s10898-006-9040-1 |
| [30] | Regis RG, Shoemaker CA (2007b) Parallel radial basis function methods for the global optimization of expensive functions. Eur J Oper Res 182:514–535 · Zbl 1178.90279 · doi:10.1016/j.ejor.2006.08.040 |
| [31] | Regis RG, Shoemaker CA (2007c) A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J Comput 19:497–509 · Zbl 1241.90192 · doi:10.1287/ijoc.1060.0182 |
| [32] | Runarsson TP, Yao X (2000) Stochastic ranking for constrained evolutionary optimization. IEEE Trans Evol Comput 4:284–294 · doi:10.1109/4235.873238 |
| [33] | Vaz AIF, Vicente LN (2007) A particle swarm pattern search method for bound constrained global optimization. J Glob Optim 39:197–219 · Zbl 1180.90252 · doi:10.1007/s10898-007-9133-5 |
| [34] | Vaz AIF, Vicente LN (2009) Pswarm: a hybrid solver for linearly constrained global derivative-free optimization. Optim Methods Softw 24:669–685 · Zbl 1177.90327 · doi:10.1080/10556780902909948 |
| [35] | Wild SM, Shoemaker CA (2011) Global convergence of radial basis function trust region derivative-free algorithms. SIAM J Optim. doi: 10.1137/09074927x · Zbl 1397.65024 |
| [36] | Wild SM, Regis RG, Shoemaker CA (2008) ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J Sci Comput 30:3197–3219 · Zbl 1178.65065 · doi:10.1137/070691814 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
