Статьи автора

Адаптивный вариант алгоритма Франк–Вульфа для задач выпуклой оптимизации

Номер выпуска 6 от 17.09.2025

В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров L_k. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров L_k. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.

19 0