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., Vicente, L.N. Incorporating minimum Frobenius norm models in direct search. Computational Optimization and Applications, 46(2), (2010), 265-278.
Di Serafino, D., Liuzzi, G., Piccialli, V., Riccio, F., Toraldo, G. A modified DIviding RECTangles algorithm for a problem in astrophysics. Journal of Optimization Theory and Applications, 151(1), (2011), 175-190.
Finkel, D.E. Global optimization with the Direct algorithm. Ph.D. thesis, North Carolina State University (2005).
Finkel, D.E., Kelley, C.T. Additive scaling and the DIRECT algorithm. Journal of Global Optimization, 36(4), (2006), 597-608.
Floudas, C.A. Deterministic Global Optimization: Theory, Methods and Applications. Nonconvex Optimization and Its Applications, vol. 37. Springer, Boston, MA, (1999). https://doi.org/10.1007/978-1-4757-4949-6.
Gablonsky, J.M. Modifications of the Direct algorithm. Ph.D. thesis, North Carolina State University (2001).
Gablonsky, J.M., Kelley, C.T. A locally-biased form of the DIRECT algorithm. Journal of Global Optimization, 21(1), (2001), 27-37.
Hedar, A. Test functions for unconstrained global optimization. :http://www-optima.amp.i. kyotou.ac.jp/member/student/hedar/Hedar_files/TestGO.htm(2005). ((accessed on 23 August 2006)).
Horst, R., Pardalos, P.M., Thoai, N.V. Introduction to Global Optimization. Nonconvex Optimization and Its Application. Kluwer Academic Publishers (1995).
Horst, R., Tuy, H. Global Optimization: Deterministic Approaches. Springer, Berlin (1996).
Jones, D.R., Perttunen, C.D., Stuckman, B.E. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Application, 79(1), (1993), 157-181.
Jones, D.R. The Direct global optimization algorithm. In: C.A. Floudas, P.M. Pardalos (eds.) The Encyclopedia of Optimization, pp. (2001), 431-440. Kluwer Academic Publishers, Dordrect (2001).
Jones, D.R., Martins, J.R.R.A. The DIRECT algorithm: 25 years later. Journal of Global Optimization 79 (2021), 521–566.
Ma, K., Rios, L. M., Bhosekar, A., Sahinidis, N., V., Rajagopalan, S.: Branch-and- Model: a derivative-free global optimization algorithm. Computational Optimization and Applications. (2023), https://doi.org/10.1007/s10589-023-00466-3
Kudela, J. A critical problem in benchmarking and analysis of evolutionary computation methods, Nature Machine Intelligence volume 4, 1238–1245, (2022).
Kudela, J. Benchmarking State-of-the-art DIRECT-type Methods on the BBOB Noiseless Testbed, GECCO ’23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, https://doi.org/10.1145/3583133.3596308.
Kudela, J. Juricek, M. Computational and Exploratory Landscape Analysis of the GKLS Generator, GECCO ’23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, https://doi.org/10.1145/3583133.3590653.
Kvasov, D.E., Sergeyev, Y.D. Lipschitz gradients for global optimization in a one-point-based partitioning scheme. Journal of Computational and Applied Mathematics, 236(16), (2012), 4042-4054.
Liberti, L., Kucherenko, S. Comparison of deterministic and stochastic approaches to global optimization. International Transactions in Operational Research 12(3), 263–285 (2005), https://doi.org/10.1111/j.1475-3995.2005.00503.x.
Liu, Q., Cheng, W. A modified DIRECT algorithm with bilevel partition. Journal of Global Optimization, 60(3), (2014), 483-499.
Liu, H., Xu, S.,Wang, X.,Wu, J., Song, Y. A global optimization algorithm for simulation-based problemsvia the extended DIRECT scheme. Eng. Optim, 47(11), (2015), 1441–1458.
Liu, Q., Zeng, J., Yang, G. MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems. Journal of Global Optimization, 62(2), (2015), 205-227.
Liuzzi, G., Lucidi, S., Piccialli, V. A direct-based approach exploiting local minimizations for the solution for large-scale global optimization problems. Computational Optimization and Applications, 45(2), (2010), 353-375.
Liuzzi, G., Lucidi, S., Piccialli, V. A DIRECTbased 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., Piccialli, V. A partitionbased global optimization algorithm. Journal of Global Optimization, 48(1), (2010), 113-128.
Liuzzi, G., Lucidi, S., Piccialli, V. Exploiting derivative-free local searches in direct-type algorithms for global optimization. Computational Optimization and Applications pp. (2014), 1-27.
Paulavicius, R., Zilinskas, J. Analysis of different norms and corresponding Lipschitz constants for global optimization. Information Technology and Control, 36(4), (2007), 383-387.
Piyavskii, S.A. An algorithm for finding the absolute minimum of a function. Theory of Optimal Solutions 2, (1967), 13–24 . in Russian. DOI:10.1080/13928619.2006.9637758
Shubert, B.O. A sequential method seeking the global maximum of a function. SIAM Journal on Numerical Analysis 9, (1972), 379–388. https://doi.org/10.1137/0709036.
Pinter, J.D. Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Nonconvex Optimization and Its Applications, vol. 6. Springer, Berlin, Germany (1996). https://doi.org/10.1007/978-1-4757-2502-5.
Paulavicius, R., Zilinskas, J., Grothey, A. Parallel branch and bound for global optimization with combination of Lipschitz bounds. Optimization Methods and Software, 26(3), (2011), 487-498. DOI:10.1080/10556788.2010.551537.
Paulavicius, R., Zilinskas, J. Simplicial Global Optimization. Springer Briefs in Optimization. Springer New York, New York, NY (2014). DOI:10.1007/978-1-4614-9093-7 .
Paulavicius, R., Chiter, L., ˇZilinskas, J. Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants. J. Glob. Optim, 71(1), (2018), 5–20. DOI:10.1007/s10898-016-0485-6.
Paulavicius, R., Sergeyev, Y.D., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Expert Systems with Applications. November 2019.
Sergeyev, Y.D. On convergence of divide the best” global optimization algorithms. Optimization, 44(3), (1998), 303-325.
Sergeyev, Y.D. An efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms. Journal of Optimization Theory and Applications, 107(1), (2000), 145-168. DOI:10.1023/A:1004613001755.
Sergeyev, Y.D. Efficient partition of n-dimensional intervals in the framework of one-point-based algorithms. Journal of optimization theory and applications, 124(2), (2005), 503-510. DOI:10.1007/s10957-004-0948-7.
Sergeyev, Y.D., Kvasov, D.E. Global search based on diagonal partitions and a set of Lipschitz constants. SIAM Journal on Optimization, 16(3), (2006), 910-937. DOI:10.1137/040621132.
Sergeyev, Y.D., Kvasov, D.E. Diagonal Global Optimization Methods. FizMatLit, Moscow (2008). In Russian.
Sergeyev, Y.D., Kvasov, D.E. On deterministic diagonal methods for solving global optimization problems with Lipschitz gradients. In: Optimization, Control, and Applications in the Information Age, 130, pp . Springer International Publishing Switzerland, (2015), 315-334. DOI:10.1007/978-3-319-18567-5-16.
Sergeyev, Y.D., 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) vol. 4, pp. 2812–2828. John Wiley and Sons, New York, NY, USA (2011).
Sergeyev, Y.D.; Kvasov, D.E. Deterministic Global Optimization: An Introduction to the Diagonal Approach. SpringerBriefs in Optimization; Springer: Berlin, Germany, (2017). https: //doi.org/10.1007/978-1-4939-7199-2.
Stripinis, L., Paulavicius, R., Zilinskas, J. Improved scheme for selection of potentially optimal hyperrectangles in DIRECT. Optim. Lett, 12(7), (2018), 1699–1712. DOI:10.1007/s11590-017-1228-4.
Stripinis, L., Paulavicius, R., Zilinskas, J. Penalty functions and two-step selection procedure based DIRECT-type algorithm for constrained global optimization. Struct. Multidiscip. Optim, 59(6), (2019), 2155–2175. DOI:10.1007/s00158-018-2181-2.
Stripinis, L., Paulavicius, R. DIRECTGOLib - DIRECT Global Optimization test problems Library, v1.1. Zenodo (2022). https://doi.org/10.5281/zenodo.6491951.
Stripinis, L., Paulavicius, R. DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative free global optimization. GitHub (2022). https://github.com/blockchain-group/DIRECTGO.
Stripinis, L., Paulavicius, R. DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative free global optimization. arXiv (2022). https: //arxiv.org/abs/2107.0220.
Stripinis, L., Paulavicius, R. Lipschitz-inspired HALRECT Algorithm for Derivative-free Global Optimization. https://doi.org/10.48550/arXiv.2205.03015.
Stripinis, L., Paulavicius, R. An extensive numerical benchmark study of deterministic vs. stochastic derivative-free global optimization algorithms. https://doi.org/10.48550/ARXIV.2209.05759.
Stripinis, L., Paulavicius, R. An empirical study of various candidate selection and partitioning techniques in the DIRECT framework. J. Glob. Optim, (2022), 1–31.
Stripinis, L., Paulavicius, R. Experimental Study of Excessive Local Refinement Reduction Techniques for Global OptimizationDIRECT-Type Algorithms. Mathematics, 10, (2022), 3760.
Stripinis, L., Paulavicius, R. Novel Algorithm for Linearly Constrained Derivative Free Global Optimization of Lipschitz Functions; Mathematics , 11(13), (2023), 2920. https://doi.org/10.3390/math11132920.
Stripinis, L., Paulavicius, R. GENDIRECT: a GENeralized DIRECT-type algorithmic framework for derivative-free global optimization. https://doi.org/10.48550/arXiv.2309.00835.
Stripinis, L., Kudela, J., Paulavicius, R.: Directgolib - direct global optimization test problems library (2023). https://github.com/blockchain-group/DIRECTGOLib.Pre-releasev2.0
Surjanovic, S., Bingham, D.: Virtual Library of Simulation Experiments: Test Functions and Datasets. http://www.sfu.ca/~ssurjano/index.html (2013). Online; accessed: 2017-03-22.
Tsvetkov, E.A., Krymov, R.A. Pure Random Search with Virtual Extension of Feasible Region. Journal Optim Theory Appl 195, (2022), 575—595.
Tuy, H. Convex Analysis and Global Optimization. Springer Science & Business Media (2013).
Zhigljavsky, A., Zilinskas, A. Stochastic Global Optimization. Springer, New York (2008).
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.
