Смирнов Александр Витальевич - к.т.н., доцент, профессор кафедры телекоммуникаций, Институт радиоэлектроники и информатики.
119454, Москва, пр-т Вернадского, д. 78
Scopus Author ID 56380930700
Alexander V. Smirnov - Cand. Sci. (Eng.), Professor, Department of Telecommunications, Institute of Radio Electronics and Informatics, MIREA – Russian Technological University.
78, Vernadskogo pr., Moscow, 119454
Scopus Author ID 56380930700
Цели. Целью работы является разработка методики исследования характеристик сходимости квазиньютоновского алгоритма (КНА) на негладких и невыпуклых целевых функциях (ЦФ) и выполнение экспериментов по этой методике.
Методы. Эксперименты выполнялись на тестовой функции, обеспечивающей возможность задания различных законов изменения ее значений по разным направлениям от точки минимума. Всего исследованы 18 примеров ЦФ с разными параметрами рельефа. Для каждого примера выполнялись 200 стартов КНА из случайных точек и фиксировались все значения ЦФ, полученные в процессе поиска. Затем по этим данным вычислялись значения Expected Run Time (ERT) – ожидаемого времени достижения заданного порогового уровня ЦФ. Далее выполнялась аппроксимация зависимости достигнутого порога ЦФ от ERT отдельно для отрезка, в котором все пороги достигаются во всех стартах для этого примера, и для отрезка, в котором пороги достигаются, но не во всех стартах.
Результаты. Эксперименты показали, что в большинстве примеров для отрезка, в котором все пороги достигаются во всех стартах, имеет место убывание ЦФ по закону геометрической прогрессии (линейная сходимость), а во втором отрезке преобладает сходимость по степенному закону. Также установлено, что наличие анизотропии рельефа ЦФ и нарушений гладкости приводят к замедлению сходимости и завершению поиска до достижения минимума с требуемой точностью.
Выводы. Исследование позволило выявить закономерности в сходимости КНА на ЦФ с различными свойствами рельефа. Дальнейшее развитие методики должно включать автоматизацию сбора и обработки данных и распространение на другие виды алгоритмов поиска оптимальных решений.
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.
The authors declare that there are no conflicts of interest present.