Efficient global optimization of multivariate functions with unknown H\"{o}lder constants via $\alpha$-dense curves

Nor Sahnoune; Djaouida Guettal; Mohamed Rahal

doi:10.33993/jnaat542-1601

Authors

Nor Sahnoune Department of Mathematics, Setif 1 Ferhat Abbas University, Algeria https://orcid.org/0009-0005-0240-2681
Djaouida Guettal Department of Basic Education in Technology, Setif 1 Ferhat Abbas University, Algeria https://orcid.org/0000-0002-6455-9933
Mohamed Rahal Department of Mathematics, Setif 1 Ferhat Abbas University, Algeria https://orcid.org/0000-0003-4656-3426

DOI:

https://doi.org/10.33993/jnaat542-1601

Keywords:

algorithm optimization, parametric curves

Abstract views: 3

Abstract

In this paper, we consider the global optimization problem of non-smooth functions over an $n$-dimensional box, satisfying the H\"{o}lder condition.
We focus our study on the case when the H\"{o}lder constant is not a priori known. We develop and analyze two algorithms. The first one is an extended version of the Piyavskii's method that adaptively construct a linear secants of the parabolic support functions, avoiding the need for a known H\"{o}lder constant. The second algorithm employs a reducing transformation approach which consists of generating, in the feasible box, an $\alpha$-dense curves, effectively converting the multivariate initial problem to a problem of a single variable. We prove the convergence of both algorithms. Their practical efficiency is evaluated through numerical experiments on some test functions and comparison with existing techniques.

Downloads

Download data is not yet available.

References

N. K. Arutynova, A. M. Dulliev, V. I. Zabotin, Algorithms for projecting a point into a level surface of a continuous function on a compact set, Computational Mathematics and Mathematical Physics 54 (9) (2014), pp. 1395–1401. https://doi.org/10.1134/S0965542514090036. DOI: https://doi.org/10.1134/S0965542514090036

A. R. Butz, Space filling curves and mathematical programming, Information and control 12 (1968), pp. 314–330.C. Chenouf, M. Rahal, On Hölder global optimization method using piecewise affine bounding functions, Numerical Algorithms 94 (2023), pp. 905--935. https://doi.org/10.1007/s11075-023-01524-x. DOI: https://doi.org/10.1007/s11075-023-01524-x

Yu.G. Evtushenko, Algorithm for finding the global extremum of a function (case of a non-uniforme mesh), USSR Comput, 11 (1971), pp. 1390-1403.E. Gourdin, B. Jaumard, R. Ellaia, Global optimization of Hölder functions, Journal of Global Optimization, 8 (1996), pp. 323-348. https://doi.org/10.1007/BF02403997. DOI: https://doi.org/10.1007/BF02403997

D. Guettal, C. Chenouf and M. Rahal, Global Optimization Method of Multivariate non-Lipschitz Functions Using Tangent Minorants, Nonlinear Dynamics and Systems Theory, 23 (2) (2023), pp. 183-194.

D. Guettal, A. Ziadi, Reducing transformation and global optimization, Applied Mathematics and Computation, 218 (2012), pp. 5848-5860. https://doi.org/10.1016/j.amc.2011.11.053. DOI: https://doi.org/10.1016/j.amc.2011.11.053

P. Hanjoul, P. Hansen, D. Peeters, J.F. Thisse, Uncapacitated plant location under alternative spatial price policies, Management Science, 36 (1990), pp. 41-47. https://doi.org/10.1287/mnsc.36.1.41. DOI: https://doi.org/10.1287/mnsc.36.1.41

R. Horst, P. M. Pardalos, Handbook of Global Optimization, Kluwer Academic Publishers, Boston, Dordrecht, London 1995.D. Lera, Ya. D. Sergeyev, Global minimization algorithms for Hölder functions, BIT Numerical mathematics, 42 (2002), pp. 119-133. https://doi.org/10.1023/A:1021926320198. DOI: https://doi.org/10.1023/A:1021926320198

S. A. Piyavskii, An algorithm for finding the absolute minimum for a function, Theory of Optimal Solution, 2 (1967) pp. 13–24. https://doi.org/10.1016/0041-5553(72)90115-2. DOI: https://doi.org/10.1016/0041-5553(72)90115-2

M. Rahal, D. Guettal, Modified sequential covering algorithm for finding a global minimizer of non differentiable functions and applications, Gen 22 (2014), pp. 100-115.

M. Rahal, A. Ziadi, A new extension of Piyavskii's method to Hölder functions of several variables, Applied Mathematics and Computation, 197 (2008), pp. 478-488. https://doi.org/10.1016/j.amc.2007.07.067. DOI: https://doi.org/10.1016/j.amc.2007.07.067

M. Rahal, A. Ziadi, R. Ellaia, Generating $alpha $-dense curves in non-convex sets to solve a class of non-smooth constrained global optimization, Croatian Operational Research Review, (2019), pp. 289-314. 10.17535/crorr.2019.0024. DOI: https://doi.org/10.17535/crorr.2019.0024

B.O. Shubert, A sequential method seeking the global maximum of a function, SIAM Journal on Numerical Analysis 9 (1972), pp. 379-388. https://doi.org/10.1137/0709036. DOI: https://doi.org/10.1137/0709036

R. G. Strongin, Algorithms for multi-extremal programming problems employing the set of joint space-filling curves, Journal of Global Optimization, 2 (1992), pp. 357–378. https://doi.org/10.1007/BF00122428. DOI: https://doi.org/10.1007/BF00122428

A. Törn, A. Zilinska, Global Optimization, Springer-Verlag, (1989).A. Yahyaoui, H. Ammar, Global optimization of multivariate Hölderian functions using overestimators, Open Access Library Journal, 4 (2017), pp. 1-18. 10.4236/oalib.1103511. DOI: https://doi.org/10.4236/oalib.1103511

V. I. Zabotin, P. A. Chernyshevsky, Extension of Strongin's global optimization algorithm to a function continuous on a compact interval, Computer Research and Modeling, 11 (2019), pp. 1111-1119. https://doi.org/10.20537/2076-7633-2019-11-6-1111-1119. DOI: https://doi.org/10.20537/2076-7633-2019-11-6-1111-1119

A. Ziadi, Y. Cherruault, Generation of $alpha$-dense curves and application to global optimization, Kybernetes 29 (2000), pp. 71-82. https://doi.org/10.1108/03684920010308871. DOI: https://doi.org/10.1108/03684920010308871

A. Ziadi, Y. Cherruault, Generation of $alpha$-dense curves in a cube of $mathbb{R}^{n}$, Kybernetes, 27 (1998), pp. 416-425. https://doi.org/10.1108/EUM0000000004524. DOI: https://doi.org/10.1108/EUM0000000004524

A. Ziadi, D. Guettal, Y. Cherruault, Global Optimization: Alienor mixed method with Piyavskii-Shubert technique, Kybernetes, 34 (2005), pp. 1049-1058. https://doi.org/10.1108/03684920510605867. DOI: https://doi.org/10.1108/03684920510605867