Diagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme
Abstract
In this paper, we consider a global optimization problem where the objective function is assumed to be Lipschitz-continuous with an unknown Lipschitz constant. Building upon the recently introduced BIRECT (BIsection of RECTangles) algorithm, we propose a new diagonal partitioning and sampling scheme. Our framework, named BIRECT-V (V for vertices), combines bisection with the sampling of two points. In the initial hyper-rectangle, these points are located at 1/3 and 1 along the main diagonal. Unlike most DIRECT-type algorithms, where evaluating the objective function at vertices is not suitable for bisection, our strategy, when combined with bisection, provides more comprehensive information about the objective function. However, the creation of new sampling points may coincide with existing ones at shared vertices, resulting in additional evaluations of the objective function and increasing the number of function evaluations per iteration. To overcome this issue, we propose modifying the original optimization domain to obtain a good approximation of the global solution. Experimental investigations demonstrate that this modification positively impacts the performance of the BIRECT-V algorithm. Our proposal shows promise as a global optimization algorithm compared to the original BIRECT and two popular DIRECT-type algorithms on a set of test problems. It particularly excels at high-dimensional problems
References
Custodio, A. L., Rocha, H., and Vicente, L. N. Incorporating minimum frobenius norm models in direct search. Computational Optimization and Applications 46, 2 (2010), 265–278.
Danilin, Y. M., and Piyavskii, S. An algorithm for finding the absolute minimum. Theory of Optimal Decisions 2 (1967), 25–37.
di Serafino, D., Liuzzi, G., Piccialli, V., Riccio, F., and Toraldo, G. A modified dividing rectangles algorithm for a problem in astrophysics. Journal of optimization theory and applications 151 (2011), 175–190.
Finkel, D. E. Global optimization with the DIRECT algorithm. North Carolina State University, 2005.
Finkel, D. E., and Kelley, C. Additive scaling and the direct algorithm. Journal of Global Optimization 36 (2006), 597–608.
Floudas, C. A. Deterministic global optimization: theory, methods and applications, vol. 37. Springer Science & Business Media, 2013.
Gablonsky, J. M., and Kelley, C. T. A locally-biased form of the direct algorithm. Journal of Global optimization 21 (2001), 27–37.
Gablonsky, J. M. X. Modifications of the DIRECT algorithm. North Carolina state university, 2001.
Hedar, A. Test functions for unconstrained global optimization, 2005.
Horst, R., Pardalos, P. M., and Van Thoai, N. Introduction to global optimization. Springer Science & Business Media, 2000.
Horst, R., and Tuy, H. Global optimization: Deterministic approaches. Springer Science & Business Media, 2013.
Jones, D. R. Direct global optimization algorithm. Encyclopedia of optimization 1, 1 (2009), 431–440.
Jones, D. R., and Martins, J. R. The direct algorithm: 25 years later. Journal of Global Optimization 79, 3 (2021), 521–566.
Jones, D. R., Perttunen, C. D., and Stuckman, B. E. Lipschitzian optimization without the lipschitz constant. Journal of optimization Theory and Applications 79 (1993), 157–181.
Kudela, J. A critical problem in benchmarking and analysis of evolutionary computation methods. Nature Machine Intelligence 4, 12 (2022), 1238–1245.
Kudela, J. Benchmarking state-of-the-art direct-type methods on the bbob noiseless testbed. In GECCO ’23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation (2023), pp. 1620–1627.
Kudela, J., and Juricek, M. Computational and exploratory landscape analysis of the gkls generator. In GECCO ’23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation (2023), pp. 443–446.
Kvasov, D. E., and Sergeyev, Y. D. Lipschitz gradients for global optimization in a one-pointbased partitioning scheme. Journal of Computational and Applied Mathematics 236, 16 (2012), 4042–4054.
Liberti, L., and Kucherenko, S. Comparison of deterministic and stochastic approaches to global optimization. International Transactions in Operational Research 12, 3 (2005), 263–285.
Liu, H., Xu, S., Wang, X., Wu, J., and Song, Y. A global optimization algorithm for simulation-based problems via the extended direct scheme. Engineering Optimization 47, 11 (2015), 1441–1458.
Liu, Q., and Cheng, W. A modified direct al mization problems. Journal of Global Optimization 62, 2 (2015), 205–227.
Liuzzi, G., Lucidi, S., and Piccialli, V. A direct-based approach exploiting local minimizations for the solution of large-scale global optimization problems. Computational Optimization and Applications 45 (2010), 353–375.
Liuzzi, G., Lucidi, S., and Piccialli, V. A partition-based global optimization algorithm. Journal of Global Optimization 48 (2010), 113–128.
Liuzzi, G., Lucidi, S., and Piccialli, V. Exploiting derivative-free local searches in directtype algorithms for global optimization. Computational Optimization and Applications 65 (2016), 449–475.
Ma, K., Rios, L. M., Bhosekar, A., Sahinidis, N. V., and Rajagopalan, S. Branch-andmodel: a derivative-free global optimization algorithm. Computational Optimization and Applications 85, 2 (2023), 337–367.
Paulavicius, R., Chiter, L., and Zilinskas, J. Global optimization based on bisection of rectangles, function values at diagonals, and a set of lipschitz constants. Journal of Global Optimization 71 (2018), 5–20.
Paulavicius, R., Sergeyev, Y. D., Kvasov, D. E., and Zilinskas, J. Globally-biased birect algorithm with local accelerators for expensive global optimization. Expert Systems with Applications 144 (2020), 113052.
Paulavicius, R., and Zilinskas, J. Analysis of different norms and corresponding lipschitz constants for global optimization. Technological and Economic Development of Economy 12, 4 (2006), 301–306.
Paulavicius, R., and Zilinskas, J. Simplicial global optimization, vol. 1. Springer, 2014.
Paulavicius, R., Zilinskas, J., and Grothey, A. Parallel branch and bound for global optimization with combination of lipschitz bounds. Optimization methods and software 26, 3 (2011), 487–498.
Pinter, J. D. Global optimization in action: continuous and Lipschitz optimization: algorithms, implementations and applications, vol. 6. Springer Science & Business Media, 1995.
Sergeyev, Y. D. On convergence of” divide the best” global optimization algorithms. Optimization 44, 3 (1998), 303–325.
Sergeyev, Y. D. Efficient strategy for adaptive partition of n-dimensional intervals in the framework of diagonal algorithms. Journal of Optimization Theory and Applications 107 (2000), 145–168.
Sergeyev, Y. D. Efficient partition of ndimensional intervals in the framework of onepoint- based algorithms. Journal of optimization theory and applications 124, 2 (2005), 503–510.
Sergeyev, Y. D., and Kvasov, D. Diagonal global optimization methods. fiz-matlit, moscow, 2008. Russian. Zbl1282 90138 .
Sergeyev, Y. D., and Kvasov, D. E. Global search based on efficient diagonal partitions and a set of lipschitz constants. SIAM Journal on Optimization 16, 3 (2006), 910–937.
Sergeyev, Y. D., and Kvasov, D. E. Lipschitz global optimization. In Cochran, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P., Smith,
J.C. (eds.) Wiley Encyclopedia of Operations Research and Management Science (in 8 Volumes) (2011), vol. 4, Wiley, pp. 2812–2828.
Sergeyev, Y. D., and Kvasov, D. E. On deterministic diagonal methods for solving global optimization problems with lipschitz gradients. In Optimization, Control, and Applications in the Information Age: In Honor of Panos M. Pardalos’s 60th Birthday (2015), Springer, pp. 315–334.
Sergeyev, Y. D., and Kvasov, D. E. Deterministic global optimization: An introduction to the diagonal approach. Springer, 2017.
Shubert, B. O. A sequential method seeking the global maximum of a function. SIAM Journal on Numerical Analysis 9, 3 (1972), 379–388.
Stripinis, L., and Paulavicius, R. DIRECTGOLib - DIRECT Global Optimization test problems Library, v1.1. Zenodo (2022). https://doi.org/10.5281/zenodo.6491951.
Stripinis, L., and Paulavicius, R. Directgo: A new direct-type matlab toolbox for derivativefree global optimization. ACM Transactions on Mathematical Software 48, 4 (2022), 1–46.
Stripinis, L., and Paulavicius, R. An empirical study of various candidate selection and partitioning techniques in the direct framework. Journal of Global Optimization (2022), 1–31.
Stripinis, L., and Paulavicius, R. Experimental study of excessive local refinement reduction techniques for global optimization direct-type algorithms. Mathematics 10, 20 (2022), 3760.
Stripinis, L., and Paulavicius, R. An extensive numerical benchmark study of deterministic vs. stochastic derivative-free global optimization algorithms. arXiv preprint arXiv:2209.05759 (2022).
Stripinis, L., and Paulavicius, R. Gendirect: a generalized direct-type algorithmic framework for derivative-free global optimization. arXiv preprint arXiv:2309.00835 (2023).
Stripinis, L., and Paulavicius, R. Lipschitzinspired halrect algorithm for derivative-free global optimization. Journal of Global Optimization (2023), 1–31.
Stripinis, L., and Paulavicius, R. Novel algorithm for linearly constrained derivative free global optimization of lipschitz functions. Mathematics 11, 13 (2023), 2920.
Stripinis, L., Paulaviˇcius, R., and Kudela, J. DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative free global optimization. GitHub (2022). https://github.com/blockchain-group/DIRECTGO.
Stripinis, L., Paulavicius, R., and Zilinskas, J. Improved scheme for selection of potentially optimal hyper-rectangles in direct. Optimization Letters 12 (2018), 1699–1712.
Stripinis, L., Paulavicius, R., and Zilinskas, J. Penalty functions and two-step selection procedure based direct-type algorithm for constrained global optimization. Structural and Multidisciplinary Optimization 59 (2019), 2155–2175.
Surjanovic, S., and Bingham, D. Virtual library of simulation experiments: test functions and datasets. Simon Fraser University, Burnaby, BC, Canada, accessed May 13 (2013), 2015.
Tsvetkov, E., and Krymov, R. Pure random search with virtual extension of feasible region. Journal of Optimization Theory and Applications 195, 2 (2022), 575–595.
Tuy, H., Hoang, T., Hoang, T., Mathematicien, V.-n., Hoang, T., and Mathematician, V. Convex analysis and global optimization. Springer, 1998.
Zhigljavsky, A., and Zilinskas, A. Stochastic global optimization, vol. 9. Springer Science & Business Media, 2007.
Copyright (c) 2023 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
