Method for estimating objective function landscape convexity during extremum search

Objectives. The work set out to develop a method for estimating the objective function (OF) landscape convexity in the extremum neighborhood. The proposed method, which requires no additional OF calculations or complicated mathematical processing, relies on the data accumulated during extremum search.

Methods. Landscape convexity is characterized by the index of power approximation of the OF in the vicinity of the extremum. The estimation of this index is carried out for pairs of test points taking into account their distances to the found extremum and OF values in them. Based on the analysis of estimation errors, the method includes the selection of test points by their distances from the found extremum and the selection of pairs of test points by the angle between the directions to them from the found extremum. Test functions having different convexities, including concave, were used to experimentally validate the method. The particle swarm optimization algorithm was used as an extremum search method. The experimental results were presented in the form of statistical characteristics and histograms of distributions of the estimation values of the degree of the OF approximation index.

Results. The conductive experiments confirm that the proposed method provides a reliable estimation of power index range bounds upon condition of appropriate definition of trial points and trial point pair selection parameters.

Conclusions. The proposed method may be a part of OF landscape analysis. It is necessary to complement it with the algorithms for automatic adjustment of trial points and pairs of trial points selection parameters. Additional information may be provided by analyzing the dependencies of power index estimations and trial point distances from extrema.

1. Malan K.M. A Survey of Advances in Landscape Analysis for Optimisation. Algorithms. 2021;14(2):40. https://doi.org/10.3390/a14020040

2. Mersmann O., Bischl B., Trautmann H., Preuss M., Weihs C., Rudolf G. Exploratory Landscape Analysis. In: GECCO’11: Proceedings of the 13th Annual Genetic and Evolutionary Computation. 2011. P. 829–836. https://doi.org/10.1145/2001576.2001690

3. Kerschke P., Trautmann H. Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-package flacco. In: Bauer N., Ickstadt K., Lübke K., Szepannek G., Trautmann H., Vichi M. (Eds.). Applications in Statistical Computing. Book Series: Studies in Classification, Data Analysis, and Knowledge Organization. Berlin/Heidelberg, Germany: Springer; 2019. P. 93–123. https://doi.org/10.1007/978-3-030-25147-5_7

4. Trajanov R., Dimeski S., Popovski M., Korosec P., Eftimov T. Explainable Landscape-Aware Optimization Performance Predicion. Preprint. 2021. http://arxiv.org/pdf/2110.11633v1, https://doi.org/10.48550/arXiv.2110.11633

5. van Stein B., Long F.X., Frenzel M., Krause P., Gitterle M., Back T. DoE2Vec: Deep-learning Based Features for Exploratory Landscape Analysis. Preprint. 2023. https://arxiv.org/pdf/2304.01219v1

6. Polyak B.T. Vvedenie v optimizatsiyu (Introduction into Optimization). Moscow: Nauka; 1983. 384 p. (in Russ.).

7. Nocedal J., Wright S. Numerical Optimization: 2nd ed. Springer; 2006. 684 p.

8. Bertsimas D., ten Eikelder S.C.M., den Hertog D., Trichakis N. Pareto Adaptive Robust Optimality via a Fourier-Motzkin Elimination Lens. Math. Program. 2024;205(9):485–538. https://doi.org/10.1007/s10107-023-01983-z

9. Smirnov A.V. Comparison of algorithms for multi-objective optimization of radio technical device characteristics. Russian Technological Journal. 2022;10(6):42−51. https://doi.org/10.32362/2500-316X-2022-10-6-42-51

10. Doikov N., Stich S.U., Jaggi M. Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions. Preprint. 2024. https://arxiv.org/pdf/2402.04843v1

11. Yaochu J. A Comprehensive Survey of Fitness Approximation in Evolutionary Computation. Soft Computing. 2005;9(1): 3–12. https://doi.org/10.1007/s00500-003-0328-5

12. Hong L.J., Zhang X. Surrogate-Based Simulation Optimization. Preprint. 2021. https://arxiv.org/pdf/2105.03893v1

13. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi (Modern Search Optimization Algorithms. Nature-Inspired Optimization Algorithms): 3rd ed. Moscow: Baumann Press; 2021. 448 p. (in Russ.).

14. Smirnov A.V. Properties of objective functions and search algorithms in multi-objective optimization problems. Russian Technological Journal. 2022;10(4):75−85. https://doi.org/10.32362/2500-316X-2022-10-4-75-85

15. Hansen N., Finck S., Ros R., Auger A. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. [Research Report] RR-6829. INRIA; 2009. Available from URL: https://hal.inria.fr/inria-00362633v2

16. Hansen N. The CMA Evolution Strategy: A Tutorial. Preprint. 2016. https://arxiv.org/abs/1604.00772v2