Экспериментальное исследование характеристик сходимости квазиньютоновского алгоритма на негладких и невыпуклых функциях

Цели. Целью работы является разработка методики исследования характеристик сходимости квазиньютоновского алгоритма (КНА) на негладких и невыпуклых целевых функциях (ЦФ) и выполнение экспериментов по этой методике.

Методы. Эксперименты выполнялись на тестовой функции, обеспечивающей возможность задания различных законов изменения ее значений по разным направлениям от точки минимума. Всего исследованы 18 примеров ЦФ с разными параметрами рельефа. Для каждого примера выполнялись 200 стартов КНА из случайных точек и фиксировались все значения ЦФ, полученные в процессе поиска. Затем по этим данным вычислялись значения Expected Run Time (ERT) – ожидаемого времени достижения заданного порогового уровня ЦФ. Далее выполнялась аппроксимация зависимости достигнутого порога ЦФ от ERT отдельно для отрезка, в котором все пороги достигаются во всех стартах для этого примера, и для отрезка, в котором пороги достигаются, но не во всех стартах.

Результаты. Эксперименты показали, что в большинстве примеров для отрезка, в котором все пороги достигаются во всех стартах, имеет место убывание ЦФ по закону геометрической прогрессии (линейная сходимость), а во втором отрезке преобладает сходимость по степенному закону. Также установлено, что наличие анизотропии рельефа ЦФ и нарушений гладкости приводят к замедлению сходимости и завершению поиска до достижения минимума с требуемой точностью.

Выводы. Исследование позволило выявить закономерности в сходимости КНА на ЦФ с различными свойствами рельефа. Дальнейшее развитие методики должно включать автоматизацию сбора и обработки данных и распространение на другие виды алгоритмов поиска оптимальных решений.

1. Поляк Б.Т. Введение в оптимизацию. М.: Наука; 1983, 384 с.

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

3. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука; 1981, 384 с.

4. Воронцова Е.А., Хильдебранд Р.Ф., Гасников А.В., Стонякин Ф.С. Выпуклая оптимизация. М.: МФТИ; 2021, 364 с. ISBN 978-5-7417-0776-0

5. Пучинин С.М., Корольков Е.Р., Стонякин Ф.С., Алкуса М.С., Выгузов А.А. Cубградиентные методы с шагом типа Б.Т. Поляка для задач минимизации квазивыпуклых функций с ограничениями-неравенствами и аналогами острого минимума. Компьютерные исследования и моделирование. 2024;16(1):105–122. 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. URL: https://hal.inria.fr/inria-00362633v2. Дата обращения 26.08.2025. / Accessed August 26, 2025.

12. Смирнов А.В. Исследование влияния степени овражности целевой функции на погрешность определения координат ее минимума. Russian Technological Journal. 2023;11(6):57−67. https://doi.org/10.32362/2500-316X-2023-11-6-57-67

13. Смирнов А.В. Метод оценки выпуклости рельефа целевых функций в процессе поиска экстремума. 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