Phương pháp số sử dụng hai cách tiếp cận khác nhau của các đường cong lấp đầy không gian cho tối ưu hóa toàn cầu hộp đen

Journal of Global Optimization - Tập 88 Số 3 - Trang 707-722 - 2024
Yaroslav D. Sergeyev1, Maria Chiara Nasso1, Daniela Lera2
1Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Universitá della Calabria, Rende, Italy
2Dipartimento di Matematica ed Informatica, Universitá di Cagliari, Cagliari, Italy

Tóm tắt

Tóm tắtTrong bài báo này, các bài toán tối ưu hóa toàn cầu đa chiều được xem xét, trong đó hàm mục tiêu được giả định là liên tục Lipschitz, đa cực trị và không có biểu thức phân tích được biết đến. Hai cách tiếp cận khác nhau của đường cong Peano-Hilbert được áp dụng để giảm bài toán xuống một bài toán đơn biến thỏa mãn điều kiện Hölder được thảo luận. Cách tiếp cận đầu tiên, xấp xỉ tuyến tính từng đoạn, được sử dụng rộng rãi trong tối ưu hóa toàn cầu và không chỉ vậy, trong khi cách tiếp cận thứ hai, xấp xỉ không đơn trị, thì ít được biết đến hơn. Các thuật toán hình học đa chiều sử dụng các xấp xỉ đường cong Peano này đã được giới thiệu và điều kiện hội tụ của chúng được thiết lập. Các thí nghiệm số được thực hiện trên 800 hàm kiểm tra ngẫu nhiên được lấy từ tài liệu cho thấy hiệu suất hứa hẹn của các thuật toán sử dụng các xấp xỉ đường cong Peano so với các đối thủ cạnh tranh trực tiếp của chúng.

Từ khóa


Tài liệu tham khảo

Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer, Natural Computing Series (2017)

Pardalos, P.M., Rosen, J.B.: Constrained Global Optimization: Algorithms and Applications. Springer Lecture Notes In Computer Science, vol. 268. Springer-Verlag, New York (1987)

Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased BIRECT algorithm with local accelerators for expensive global optimization. Expert Syst. Appl. 144, 113052 (2020)

Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: A review of algorithms and comparison of software implementations. J. Global Optim. 56, 1247–1293 (2013)

Sergeyev, Y.D.: Efficient strategy for adaptive partition of $$n$$-dimensional intervals in the framework of diagonal algorithms. J. Optim. Theory Appl. 107(1), 145–168 (2000)

Sergeyev, Y.D., Mukhametzhanov, M.S., Kvasov, D.E., Lera, D.: Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization. J. Optim. Theory Appl. 171(1), 186–208 (2016)

Sergeyev, Y.D., Nasso, M.C., Mukhametzhanov, M.S., Kvasov, D.E.: Novel local tuning techniques for speeding up one-dimensional algorithms in expensive global optimization using Lipschitz derivatives. J. Comput. Appl. Math. 383, 113134 (2021)

Strongin, R.G., Barkalov, K., Bevzuk, S.: Global optimization method with dual Lipschitz constant estimates for problems with non-convex constraints. Soft. Comput. 24(16), 11853–11865 (2020)

Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008)

Zhigljavsky, A., Žilinskas, A.: Bayesian and High-Dimensional Global Optimization. Springer, New York (2021)

Archetti, F., Candelieri, A.: Bayesian Optimization and Data Science. Springer, New York (2019)

Candelieri, A., Giordani, I., Archetti, F., Barkalov, K., Meyerov, I., Polovinkin, A., Sysoyev, A., Zolotykh, N.: Tuning hyperparameters of a svm-based water demand forecasting system through parallel global optimization. Comput. Oper. Res. 106, 202–209 (2019)

Cavoretto, R., De Rossi, A., Mukhametzhanov, M.S., Sergeyev, Y.D.: On the search of the shape parameter in radial basis functions using univariate global optimization methods. J. Global Optim. 79, 305–327 (2021)

Daponte, P., Grimaldi, D., Molinaro, A., Sergeyev, Y.D.: An algorithm for finding the zero-crossing of time signals with Lipschitzean derivatives. Measurement 16(1), 37–49 (1995)

Famularo, D., Pugliese, P., Sergeyev, Y.D.: Global optimization technique for checking parametric robustness. Automatica 35(9), 1605–1611 (1999)

Floudas, C.A., Pardalos, P.M.: State of the Art in Global Optimization. Kluwer Academic Publishers, Dordrecht (1996)

Kvasov, D.E., Sergeyev, Y.D.: Lipschitz global optimization methods in control problems. Autom. Remote. Control. 74(9), 1435–1448 (2013)

Kvasov, D.E., Sergeyev, Y.D.: Deterministic approaches for solving practical black-box global optimization problems. Adv. Eng. Softw. 80, 58–66 (2015)

Lera, D., Posypkin, M., Sergeyev, Y.D.: Space-filling curves for numerical approximation and visualization of solutions to systems of nonlinear inequalities with applications in robotics. Appl. Math. Comput. 390, 125660 (2021)

Sergeyev, Y.D., Candelieri, A., Kvasov, D.E., Perego, R.: Safe global optimization of expensive noisy black-box functions in the $$\delta $$-Lipschitz framework. Soft. Comput. 24(23), 17715–17735 (2020)

Sergeyev, Y.D., Daponte, P., Grimaldi, D., Molinaro, A.: Two methods for solving optimization problems arising in electronic measurements and electrical engineering. SIAM J. Optim. 10(1), 1–21 (1999)

Sergeyev, Y.D., Kvasov, D.E., Mukhametzhanov, M. S.: A generator of multiextremal test classes with known solutions for black-box constrained global optimization. IEEE Transactions on Evolutionary Computation. https://doi.org/10.1109/TEVC.2021.3139263, in press

Gergel, V.P., Grishagin, V.A., Israfilov, R.: Multiextremal optimization in feasible regions with computable boundaries on the base of the adaptive nested scheme. In: Numerical Computations: Theory and Algorithms – NUMTA 2019, volume 11974 of LNCS, pages 112–123. Springer, 2020

Grishagin, V., Israfilov, R., Sergeyev, Y.D.: Convergence conditions and numerical comparison of global optimization methods based on dimensionality reduction schemes. Appl. Math. Comput. 318, 270–280 (2018)

Kvasov, D.E., Sergeyev, Y.D.: Multidimensional global optimization algorithm based on adaptive diagonal curves. Comput. Math. Math. Phys. 43(1), 40–56 (2003)

Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014)

Sergeyev, Y.D.: On convergence of “Divide the Best’’ global optimization algorithms. Optimization 44, 303–325 (1998)

Sergeyev, Y.D., Grishagin, V.A.: A parallel method for finding the global minimum of univariate functions. J. Optim. Theory Appl. 80, 513–536 (1994)

Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods. FizMatLit, Moscow (2008). (In Russian)

Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization: An Introduction to the Diagonal Approach. SpringerBriefs in Optimization. Springer, New York (2017)

Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013)

Strongin, R.G., Sergeyev, Y.D.: Global multidimensional optimization on parallel computer. Parallel Comput. 18(11), 1259–1273 (1992)

Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000)

Peano, G.: Sur une courbe, qui remplit toute une aire plane. Math. Ann. 36, 157–160 (1890)

Hilbert, D.: Über die stetige abbildung einer linie auf ein flächenstück. Math. Ann. 38, 459–460 (1891)

Lera, D., Sergeyev, Y.D.: Lipschitz and Hölder global optimization using space-filling curves. Appl. Numer. Math. 60(1), 115–129 (2010)

Lera, D., Sergeyev, Y.D.: Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. Commun. Nonlinear Sci. Numer. Simul. 23(1–3), 328–342 (2015)

Lera, D., Sergeyev, Y.D.: GOSH: derivative-free global optimization using multi-dimensional space-filling curves. J. Global Optim. 71(1), 193–211 (2018)

Gourdin, E., Jaumard, B., Ellaia, R.: Global optimization of Hölder functions. J. Global Optim. 8, 323–348 (1996)

Lera, D., Sergeyev, Y.D.: Global minimization algorithms for Hölder functions. BIT 42(1), 119–133 (2002)

Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)

Sergeyev, Y.D., Kvasov, D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optimization 16(3), 910–937 (2006)

Gaviano, M., Lera, D., Kvasov, D.E., Sergeyev, Y.D.: Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Software 29, 469–480 (2003)

Grishagin, V.: Operational characteristics of some global search algorithms. Problems of Stochastic Search 7, 198–206 (1978)