Abstract
Some powerful algorithms for multi-extremal non-convex-constrained optimization problems are based on reducing these multi-dimensional problems to those of one dimension by applying Peano-type space-filling curves mapping a unit interval on the real axis onto a multi-dimensional hypercube. Here is presented and substantiated a new scheme simultaneously employing several joint Peano-type scannings which conducts the property of nearness of points in many dimensions to a property of nearness of pre-images of these points in one dimension significantly better than in the case of a scheme with a single space-filling curve. Sufficient conditions of global convergence for the new scheme are investigated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Betro, B. (1991), Bayesian Methods in Global Optimization, Journal of Global Optimization 1(1), 1–14.
Butz, A. R. (1968), Space Filling Curves and Mathematical Programming, Inform. Control 12(4), 314–330.
Butz, A. R. (1971), Alternative Algorithm for Hibert's Space Filling Curve, IEEE Trans. Computers C-20(4), 424–426.
Evtushenko, Y. G. (1985), Numerical Optimization Techniques, Translation Series in Mathematics and Engineering, Optimization Software Inc., Publication Division, New York.
Gergel, V. P., Strongin, L. G., and Strongin, R. G. (1987), The Vicinity Method in Pattern Recognition, Engineering Cybernetics (Transl. from Izv. Acad. Nauk USSR, Techn. Kibernetika 4, 14–22).
Hansen, P., Jaumard, B., and Lu, S. H. (1991), On Timonov's Algorithm for Global Optimization of Univariate Lipschitz Functions, Journal of Global Optimization 1(1), 37–46.
Horst, R. (1990), Deterministic Methods in Constrained Global Optimization: Some Recent Advances and New Fields of Application, Naval Research Logistics Quarterly 37, 433–471.
Korotkich, V. V. (1989), Multilevel Dichotomy Algorithm in Global Optimization, in System Modelling and Optimization, 161–169. Proceedings of the 14th IFIP Conference, Leipzig. Springer-Verlag.
Kuhn, H. W. and Tucker, A. W. (1951), Nonlinear Programming, in Neyman, J., ed., Proceedings of the Second Berkeley Symposium on Math. Stat. and Probab. Univ. of Calif. Press, Berkeley and Los Angeles, Calif., 481–492.
Markin, D. L. and Strongin, R. G. (1987), A Method for Solving Multi-Extremal Problems with Non-Convex Constraints, That Uses a Priori Information about Estimates of the Optimum, U.S.S.R. Comput. Maths. Math. Phys. 27(1), 33–39. Pergamon Press 1988 (Zh. vychisl. Mat. mat. Fiz. 27(1), 52–62, 1987).
Pinter, J. (1988), Branch and Bound Algorithms for Solving Global Optimization Problems with Lipschitzian Structure, Optimization 19, 101–110.
Piyavskii, S. A. (1972), An Algorithm for Finding the Absolute Extremum of a Function, U.S.S.R. Comput. Maths. Math. Phys. 12, 57–67 (Zh. vychisl. Mat. mat. Fiz. 12 (1972) 888–896).
Rinnooy Kan, A. H. G. and Timmer, G. T. (1989), Global Optimization, in Nemhauser G. L. et al., eds., Handbooks in OR&MS 1, 631–662, North-Holland, Elsevier Science Publishers.
Sergeev, Ya. D. and Strongin, R. G. (1987), Effective Algorithm for Global Optimization with Parallel Computations, in Kurzhanski, A., Neumann, K., and Pallaschke, D., eds., Lecture Notes in Economics and Mathematical Systems 304, 158–162. Proceedings 1987. Springer-Verlag. Berlin, Heidelberg 1988.
Sergeev, Ya. D. and Strongin, R. G. (1989), A Global Minimization Algorithm with Parallel Iterations, U.S.S.R. Comput. Maths. Math. Phys. 29(2), 7–15. Pergamon Press 1990 (Zh. vychisl. Mat. mat. Fiz. 29(3), 332–345, 1989).
Strongin, R. G. (1973), On the Convergence of an Algorithm for Finding a Global Extremum, Engineering Cybernetics, 11, 549–555.
Strongin, R. G. (1978), Numerical Methods for Multiextremal Problems, Nauka, Moscow (in Russian).
Strongin, R. G. (1984), Numerical Methods for Multiextremal Nonlinear Programming Problems with Nonconvex Constraints, in Demyanov, V. F. and Pallaschke, D., eds., Lecture Notes in Economics and Mathematical Systems 255, 278–282. Proceedings 1984. Springer-Verlag. IIASA, Laxenburg/Austria 1985.
Strongin, R. G. (1989), The Information Approach to Multiextremal Optimization Problems, Stochastics and Stochastics Reports 27, 65–82. Gordon and Breach Science Publishers, Inc.
Strongin, R. G. (1990), Search for Global Optimum, Series of Mathematics and Cybernetics 2, Znanie, Moscow (in Russian).
Strongin, R. G., Gergel, V. P., and Markin, D. L. (1988), Multicriterion Multiextreme Optimization with Nonlinear Constraints, in Lewandovski, A. and Volkovich, V., eds., Lecture Notes in Economics and Mathematical Systems 351, 120–127. Proceedings 1988. Springer-Verlag. IIASA, Laxenburg/Austria 1991.
Strongin, R. G. and Markin, D. L. (1986), Minimization of Multiextremal Functions with Nonconvex Constraints, Cybernetics 22(4), 486–493. Translated from Russian. Consultant Bureau. New York.
Sukharev, A. G. (1971), Best Sequential Search Strategies for Finding an Extremum, U.S.S.R. Comput. Math. Math. Phys. 12(1), 39–59. Pergamon Press 1972 (Zh. vychisl. Mat. mat. Fiz. 12(1), 35–50, 1971).
Uosaki, K., Imamura, H., Tasaka, M., and Sugiyama, H. (1970), A Heuristic Method for Maxima Searching in Case of Multimodal Surfaces, Technol. Repts., Osaka Univ. 20, 337–344.
Zilinskas, A. (1981), On Multimodal Minimization Algorithm Constructed Axiomatically, Methods of Operations Research 40, 197–200.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Strongin, R.G. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. J Glob Optim 2, 357–378 (1992). https://doi.org/10.1007/BF00122428
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00122428