Abstract
In the present paper, the multidimensional multiextremal optimization problems and the numerical methods for solving these ones are considered. A general assumption only is made on the objective function that this one satisfies the Lipschitz condition with the Lipschitz constant not known a priori. The problems of this type are frequent in the applications. Two approaches to the dimensionality reduction for the multidimensional optimization problems were considered. The first one uses the Peano-type space-filling curves mapping a one-dimensional interval onto a multidimensional domain. The second one is based on the nested optimization scheme, which reduces a multi-dimensional problem to a family of the one-dimensional subproblems. A generalized scheme combining these two approaches has been proposed. In this novel scheme, solving a multidimensional problem is reduced to solving a family of problems of lower dimensionality, in which the space-filling curves are used. An adaptive algorithm, in which all arising subproblems are solved simultaneously has been implemented. The numerical experiments on several hundred test problems have been carried out confirming the efficiency of the proposed generalized scheme.
This study was supported by the Russian Science Foundation, project No. 16-11-10150.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barkalov, K., Gergel, V., Lebedev, I.: Use of Xeon Phi coprocessor for solving global optimization problems. Lecture Notes in Computer Science, vol. 9251, pp. 307–318 (2015)
Barkalov, K., Lebedev, I.: Solving multidimensional global optimization problems using graphics accelerators. Commun. Comput. Inf. Sci. 687, 224–235 (2016)
Barkalov, K., Gergel, V.: Multilevel scheme of dimensionality reduction for parallel global search algorithms. In: OPT-i 2014 Proceedings of 1st International Conference on Engineering and Applied Sciences Optimization, pp. 2111–2124 (2014)
Carr, C., Howe, C.: Quantitative Decision Procedures in Management and Economic: Deterministic Theory and Applications. McGraw-Hill, New York (1964)
Evtushenko, Y., Posypkin, M.: A deterministic approach to global box-constrained optimization. Optim. Lett. 7, 819–829 (2013)
Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the direct algorithm. J. Glob. Optim. 21(1), 27–37 (2001)
Gaviano, M., Kvasov, D.E., Lera, D., Sergeev, Ya.D.: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Transact. Math. Softw. 29(4), 469–480 (2003)
Gergel, V., Grishagin, V., Gergel, A.: Adaptive nested optimization scheme for multidimensional global search. J. Glob. Optim. 66(1), 35–51 (2016)
Gergel, V., Grishagin, V., Israfilov, R.: Local tuning in nested scheme of global optimization. Proc. Comput. Sci. 51(1), 865–874 (2015)
Grishagin, V., Israfilov, R., Sergeyev, Y.: Comparative efficiency of dimensionality reduction schemes in global optimization. AIP Conf. Proc. 1776, 060011 (2016)
Grishagin, V., Israfilov, R., Sergeyev, Y.: Convergence conditions and numerical comparison of global optimization methods based on dimensionality reduction schemes. Appl. Math. Comput. 318, 270–280 (2018)
Jones, D., Perttunen, C., Stuckman, B.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)
Jones, D.R.: The direct global optimization algorithm. In: The Encyclopedia of Optimization, pp. 725–735. Springer, Heidelberg (2009)
Kvasov, D.E., Mukhametzhanov, M.S.: Metaheuristic vs. deterministic global optimization algorithms: the univariate case. Appl. Math. Comput. 318, 245 – 259 (2018)
Paulavičius, R., Žilinskas, J.: Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints. Optim. Lett. 10(2), 237–246 (2016)
Paulavičius, R., Žilinskas, J., Grothey, A.: Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. Optim. Lett. 4(2), 173–183 (2010)
Sergeyev, Y., Grishagin, V.: Sequential and parallel algorithms for global optimization. Optim. Method. Softw. 3(1–3), 111–124 (1994)
Sergeyev, Y., Grishagin, V.: Parallel asynchronous global search and the nested optimization scheme. J. Comput. Anal. Appl. 3(2), 123–145 (2001)
Sergeyev, Y., Kvasov, D.: A deterministic global optimization using smooth diagonal auxiliary functions. Commun. Nonlinear Sci. Numer. Simul. 21(1–3), 99–111 (2015)
Sergeyev, Y., Kvasov, D., Mukhametzhanov, M.: On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget. Sci. Rep. 8(1), 435 (2018)
Sergeyev, Y., Mukhametzhanov, M., Kvasov, D., 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., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-filling Curves. Springer Briefs in Optimization. Springer, New York (2013)
Strongin R.G., Sergeyev Y.D.: Global Optimization with Non-convex Constraints. Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000)
Yang, X.S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press, Frome (2008)
Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Barkalov, K., Lebedev, I. (2020). Adaptive Global Optimization Based on Nested Dimensionality Reduction. In: Le Thi, H., Le, H., Pham Dinh, T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019. Advances in Intelligent Systems and Computing, vol 991. Springer, Cham. https://doi.org/10.1007/978-3-030-21803-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-21803-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21802-7
Online ISBN: 978-3-030-21803-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)