Abstract
Partition-based algorithms, such as the DIRECT algorithm, are popular algorithms for solving global optimization problems. However, these algorithms often have an eventually inefficient behavior due to much more costs requirement to obtain a solution with higher accuracy. In this paper, we present an algorithm framework for bound constrained global optimization problems based on a multilevel partition strategy. This multilevel partition strategy can be regarded as a combination of the basic partition strategy and the multigrid algorithm, which is one of the best algorithms to solve partial differential equation. Our basic idea is to combine the multigrid algorithm with the partition-based algorithm to improve the eventually inefficient behavior of the partition-based algorithm. First, we provide a general framework of the partition-based algorithms which include the DIRECT algorithm as a special case. Then we present a strategy to build the subproblem at the coarse level. This strategy is easy to implement and brings no more computational costs. Under mild conditions, we show that the sequence generated by the proposed global optimization algorithm framework converges to the global optimum. Finally, we employ the original DIRECT algorithm to build a specific global optimization algorithm based on multilevel partition and compare it with the original DIRECT algorithm. Our numerical results show that obtained algorithm improves significantly the eventually inefficient behavior of the original DIRECT algorithm when the required accuracy is high.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Björkman, M., Holmström, K.: Global optimization using the DIRECT algorithm in Matlab. Adv. Model. Optim. 1, 17–37 (1999)
Brandt, A.: Multi-level adaptive solutions to boundary value problems. Math. Comput. 31, 333–390 (1977)
Briggs, W.L., Henson, V.E., McCormick, S.: A Multigrid Tutorial. SIAM, Philadelphia (2000)
Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)
Eberhart, R.S., Kennedy, J.: A new optimizer using particle swarm theory. In: proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS’95, pp. 39–43. IEEE press (1995)
Finkel, D.E.: DIRECT optimization user guide. Center for Research and Scientific Computation CRSC-TR03-11, North Carolina State University, Raleigh, NC (2003)
Finkel, D.E., Kelley, C.T.: Convergence analysis of the DIRECT algorithm. Technical Report CRSC-TR04-28, North Carolina State University, Center for Research in Scientific Computation (2004)
Finkel D.E.: Global optimization with the DIRECT algorithm. PHD thesis, North Carolina State University (2005)
Finkel, D.E., Kelley, C.T.: Additive scaling and the DIRECT algorithm. J. Glob. Optim. 36, 597–608 (2006)
Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45, 3–38 (2009)
Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the DIRECT algorithm. J. Glob. Optim. 21, 27–37 (2001)
Hoset, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Berlin (1996)
Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. J. Glob. Optim. 14(4), 331–355 (1999)
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)
Jones, D.R.: The DIRECT Global Optimization Algorithm. The Encyclopedia of Optimization. Kluwer, Berlin (1999)
Kennedy, J., Eberhart, R.S.: Particle swarm optimization. In: proceedings of IEEE International Conference on Neural Networks, 4, pp. 1942–1948. Perth, WA, Australia (1995)
Liu, Q.: Linear scaling and the DIRECT algorithm. J. Glob. Optim. 56, 1233–1245 (2013)
Liuzzi, G., Lucidi, S., Piccialli, V.: A partion-based global optimization algorithm. J. Glob. Optim. 48, 113–128 (2010)
Ljunberg, K., Holmgren, S.: Simultaneous search for multiple QTL using the global optimization algorithm DIRECT. Bioinformatics 20(12), 1887–1895 (2004)
Pardalos, P.M., Schoen, F.: Recent advances and trends in global optimization: deterministic and stochastic methods. In: Proceedings of the Sixth International Conference on Foundations of Computer-Aided Process Design, DSI 1-2004, pp. 119–131 (2004)
Pošík P.: BBOB-Benchmarking the DIRECT global optimization algorithm. In: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 2315–2320 (2009)
Sasena, M., Papalambros, P., Goovaerts, P.: Global optimization of problems with disconnected feasible Regions via Surrogate Modeling. In: 9th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization. Atlanta, GA (2002)
Weise, T.: Global Optimization Algorithms-Theory and Applications, 2nd edn. http://www.it-weise.de/ (2009)
Liu, Q., Zeng, J.: Convergence analysis of multigrid methods with residual scaling techniques. J. Comput. Appl. Math. 234, 2932-2942 (2010)
Liu, Q., Zeng, J.: Convergence analysis of multigrid methods with residual scaling techniques. J. Comput. Appl. Math. 234, 2932-2942 (2010)
Acknowledgments
We would like to thank Doctor Finkel D.E. and Professor Kelley C.T. for their DIRECT codes and the Jones test set codes. We thank Professor Li D. H. for his suggestions to improve the appearance of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by MOE (Ministry of Education in China) Project of Humanities and Social Science (Project No. 13YJC630095) and NSF of China (No. 11271069).
Rights and permissions
About this article
Cite this article
Liu, Q., Zeng, J. Global optimization by multilevel partition. J Glob Optim 61, 47–69 (2015). https://doi.org/10.1007/s10898-014-0152-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-014-0152-8