Experimental investigation of convergence characteristics of quasi-Newton algorithm on nonsmooth and nonconvex functions

Objectives. The aim of the paper is to develop a methodology for studying the convergence of the quasi-Newton minimization algorithm (QNA) on nonsmooth and nonconvex objective functions (OF), as well as to conduct related numerical experiments.

Methods. The experiments were performed on a flexible OF capable of mimicking various patterns of value changes in different directions away from the minimum. A total of 18 OF instances with different landscape parameters were studied. For each example, 200 QNA searches were performed from random staring points, and all corresponding OF values were recorded. Then, the Expected Run Time (ERT) to reach a given threshold level of the OF was computed based on the data. The dependence of the achieved OF threshold on ERT was approximated separately for the segment in which all thresholds were achieved in all searches, and for a segment in which the thresholds were achieved, but not in all searches.

Results. The experiments show that, for the majority of cases in which all thresholds are achieved in all takes, a decrease in the OF follows the geometric progression law (linear convergence). However, in the second segment, convergence follows the power law. It was also found that the presence of anisotropy of the OF landscape and a loss of smoothness lead to convergence slowdown, and premature termination of search process before reaching the minimum with the required accuracy.

Conclusions. The study identifies patterns in the QNA convergence on the objective functions with different landscape parameters. Further advancement of the methodology would involve automating data collection and processing, as well as extending it to other types of optimization algorithms.

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

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

3. Dem’yanov V.F., Vasil’ev L.V. Nedifferentsiruemaya optimizatsiya (Non-differentiable Optimization). Moscow: Nauka; 1981, 384 p. (In Russ.).

4. Vorontsova E.A., Hilderbrand R.F., Gasnikov A.V., Stonyakin F.S. Vypuklaya optimizatsiya (Convex Optimization). Moscow: MPTI; 2021, 364 p. (In Russ.). ISBN 978-5-7417-0776-0

5. Puchinin S.M., Korolkov E.R., Stonyakin F.S., Alkousa M.S., Vyguzov A.A. Subgradient methods with B.T. Polyaktype step for quasiconvex minimization problems with inequality constraints and analogs of the sharp minimum. Komp’yuternye issledovaniya i modelirovanie = Computer Research and Modeling. 2024;16(1):105–122 (in Russ.). https://doi.org/10.20537/2076-7633-2024-16-1-105-122

6. Bento G.C., Mordukhovich B.S., Mota T.S., Nesterov Yu. Convergence of Descent Methods under Kurdyka-Lojasiewicz Properties. arXiv. Preprint. 2024. http://arxiv.org/pdf/2407.00812v1

7. Grimmer B., Jia Zh. Goldstein Stationarity in Lipschitz Constrained Optimization. Optim. Lett. 2025419:225–235. https://doi.org/10.1007/s11590-024-02158-1

8. Lewis A.S., Overton M.L. Nonsmooth optimization via quasi-Newton methods. Math. Program. 2013;141:135–163. https://doi.org/10.1007/s10107-012-0514-2

9. Tor A.H. Comparative numerical results on HANSO (Hybrid Algorithm for Nonsmooth Optimization). arXiv. Preprint. 2020. http://arxiv.org/pdf/2009.01037v1

10. Varelas K., Dahito M.-A. Benchmarking Multivariate Solvers of SciPy on the Noiseless Testbed. In: GECCO 2019 Companion – The Genetic and Evolutionary Computation Conference, Jul. 2019, Prague, Czech Republic. 2019. P. 1946–1954. https://doi.org/10.1145/3319619.3326891

11. 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. Accessed August 26, 2025.

12. Smirnov A.V. Investigation of influence of objective function valley ratio on the determination error of its minimum coordinates. Russian Technological Journal. 2023;11(5):57−67. https://doi.org/10.32362/2500-316X-2023-11-6-57-67

13. Smirnov A.V. The method of estimation of objective functions landscapes convexity during extremum search. Russian Technological Journal. 2025;13(2):121–131. https://doi.org/10.32362/2500-316X-2025-13-2-121-131

14. Hansen N., Auger A., Ros R., Mersmann O., Tusar T., Brockhoff D. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optim. Meth. Software. 2021;36(1):114–144. https://doi.org/10.1080/10556788.2020.1808977

15. Wang H., Vermetten D., Ye. F., Doerr C., Back T. IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics. ACM Transaction on Evolutionary Learning and Optimization. 2022;2(1):1–29. https://doi.org/10.1145/3510426