A new analytical envelope for multivariate global optimization
DOI:
https://doi.org/10.33993/jnaat551-1657Keywords:
global optimization, analytical envelopes, interval analysis, dimension reductionAbstract
We propose a new global optimization method that combines an α–dense univariate reduction with explicitly constructed analytical envelopes: a piecewise concave underestimator (PCU) and a piecewise convex overestimator (PCO). By leveraging interval-
based curvature bounds, the method provides rigorous global optimality certificates. An adaptive branch-and-bound strategy ensures rapid convergence by refining intervals based on theoretical envelope widths. Numerical experiments on challenging nonconvex and multimodal benchmarks demonstrate strong performance and efficiency.
Downloads
References
[1] D. Aaid, A. Noui, M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017) no. 1, pp. 19–33. https://doi.org/10.5817/am2017-1-19 DOI: https://doi.org/10.5817/AM2017-1-19
[2] D. Aaid, Ö. Özer, New technique for solving multivariate global optimization, J. Numer. Anal. Approx. Theory, 52 (2023) no. 1, pp. 3–16. https://doi.org/10.33993/jnaat521-1287 DOI: https://doi.org/10.33993/jnaat521-1287
[3] C. S. Adjiman, S. Dallwig, C. A. Floudas, A. Neumaier, A global optimization method, αBB, for general twice-differentiable constrained NLPs — I. Theoretical advances, Computers & Chemical Engineering, 22 (1998) no. 9, pp. 1137–1158. https://doi.org/10.1016/s0098-1354(98)00027-1 DOI: https://doi.org/10.1016/S0098-1354(98)00027-1
[4] C. S. Adjiman, I. P. Androulakis, C. A. Floudas, A global optimization method, αBB, for general twice-differentiable constrained NLPs—II. Implementation and computational results, Computers & Chemical Engineering, 22 (1998) no. 9, pp. 1159–1179. https://doi.org/10.1016/s0098-1354(98)00218-x DOI: https://doi.org/10.1016/S0098-1354(98)00218-X
[5] M. H. Chang, Y. C. Park, T.-Y. Lee, A new global optimization method for univariate constrained twice-differentiable NLP problems, Journal of Global Optimization, 39 (2007), pp. 79–100. https://doi.org/10.1007/s10898-006-9121-1 DOI: https://doi.org/10.1007/s10898-006-9121-1
[6] C. A. Floudas, Deterministic Global Optimization: Theory, Methods and Applications, Kluwer Academic, Dordrecht, (2000), 739 pages. https://doi.org/10.1016/S0898-1221(00)90165-2 DOI: https://doi.org/10.1016/S0898-1221(00)90165-2
[7] K. Gökçesu, H. Gökçesu, 1D to nD: A meta algorithm for multivariate global optimization via univariate optimizers, http://arxiv.org/abs/2209.03246v1
[8] D. E. Kvasov, Y. D. Sergeyev, Univariate geometric Lipschitz global optimization algorithms, Numerical Algebra, Control and Optimization, 2 (2012) no. 1, pp. 69–90. https://doi.org/10.3934/naco.2012.2.69 DOI: https://doi.org/10.3934/naco.2012.2.69
[9] H. A. Le Thi, M. Ouanes, Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint, RAIRO – Operations Research, 40 (2006) no. 3, pp. 285–302. https://doi.org/10.1051/ro:2006024 DOI: https://doi.org/10.1051/ro:2006024
[10] M. Locatelli, F. Schoen, Global Optimization: Theory, Algorithms, and Applications, MOS-SIAM Series on Optimization, (2013). https://doi.org/10.1137/1.9781611972672.fm DOI: https://doi.org/10.1137/1.9781611972672
[11] C. Malherbe, N. Vayatis, Global Optimization of Lipschitz Functions, Proc. Mach. Learn. Res. (PMLR), 70 (2017), pp. 2314–2323. http://proceedings.mlr.press/v70/malherbe17a.html
[12] Y. D. Sergeyev, A one-dimensional deterministic global minimization algorithm, Comput. Math. Math. Phys., 35 (1995) no. 5, pp. 553–562.
[13] Y. D. Sergeyev, D. E. Kvasov, M. S. Mukhametzhanov, On strong homogeneity of a class of global optimization algorithms working with infinite and infinitesimal scales, Communications in Nonlinear Science and Numerical Simulation, 59 (2018), pp. 319–330. https://doi.org/10.1016/j.cnsns.2017.11.013 DOI: https://doi.org/10.1016/j.cnsns.2017.11.013
[14] A. Skjäl, On the Use of Convex Underestimators in Global Optimization, Ph.D. dissertation, Åbo Akademi University, (2014). https://www.doria.fi/bitstream/handle/10024/95727/skjal_anders.pdf
[15] W. R. Strahl, A. U. Raghunathan, N. V. Sahinidis, Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (DC) Functions, Journal of Global Optimization, 93 (2025), pp. 953–987. https://doi.org/10.1007/s10898-025-01567-5 DOI: https://doi.org/10.1007/s10898-025-01567-5
[16] A. P. Vinod, A. Israel, U. Topcu, Constrained, Global Optimization of Unknown Functions with Lipschitz Continuous Gradients, SIAM Journal on Optimization, 32 (2022) no. 2. https://doi.org/10.1137/20m1380879 DOI: https://doi.org/10.1137/20M1380879
[17] R. Horst, Recent Advances in Global Optimization: A Tutorial Survey, Recent Developments in Mathematical Programming, (2022). https://doi.org/10.1201/9780429333439-1 DOI: https://doi.org/10.1201/9780429333439-1
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Djamel Aaid
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
