Программирование, 2023, № 6, стр. 14-26
Адаптивный вариант алгоритма Франк–Вульфа для задач выпуклой оптимизации
Г. В. Айвазян a, *, Ф. С. Стонякин a, b, **, Д. А. Пасечнюк a, c, ***, М. С. Алкуса a, d, ****, А. М. Райгородский a, e, f, *****, И. В. Баран b, ******
a Московский физико-технический институт
141701 г. Долгопрудный, Институтский пер., 9, Россия
b Крымский федеральный университет им. В.И. Вернадского
295007 г. Симферополь, проспект академика Вернадского, 4, Россия
c Исследовательский центр доверенного искусственного интеллекта ИСП РАН
109004 г. Москва, ул. Александра Солженицына, 25, Россия
d Национальный исследовательский университет “Высшая школа экономики”
101000 г. Москва, ул. Мясницкая, д. 20, Россия
e Московский государственный университет им. М.В. Ломоносова, механико-математический факультет
119991 г. Москва, Ленинские горы, д. 1, Россия
f Кавказский математический центр Адыгейского государственного университета
385000 г. Майкоп, ул. Первомайская, 208, Россия
* E-mail: aivazian.grigory25@yandex.ru
** E-mail: fedyor@mail.ru
*** E-mail: dmivilensky1@gmail.com
**** E-mail: mohammad.alkousa@phystech.edu
***** E-mail: raigorodsky@yandex-team.ru
****** E-mail: matemain@mail.ru
Поступила в редакцию 13.06.2023
После доработки 14.07.2023
Принята к публикации 20.07.2023
- EDN: GGFHZJ
- DOI: 10.31857/S0132347423060031
Полные тексты статей выпуска доступны в ознакомительном режиме только авторизованным пользователям.
Аннотация
В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров Lk. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров Lk. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.
Полные тексты статей выпуска доступны в ознакомительном режиме только авторизованным пользователям.
Список литературы
Canon M.D., Cullum C.D. A tight upper bound on the rate of convergence of Frank–Wolfe algorithm // SIAM Journal on Control. 1968. V. 6 (2.4). P. 509–516.
Bomze I.M., Rinaldi F., Zeffiro D. Frank–Wolfe and friends: a journey into projection-free first-order optimization methods // 4OR-Q J Oper Res. 2021. V. 19. P. 313–345.
Braun G., Carderera A., Combettes C.W., Hassani H., Karbasi A., Mokhtari A., Pokutta S. Conditional Gradient Methods. https://arxiv.org/pdf/2211.14103.pdf
Nesterov Y. Complexity bounds for primal-dual methods minimizing the model of objective function // Math. Program. 2018. V. 171 (1-2). P. 311–330.
Nesterov Y. Universal gradient methods for convex optimization problems // Math. Program. A 2015. V. 152. P. 381–404.
Pedregosa F., Negiar G., Askari A., Jaggi M. Linearly convergent Frank–Wolfe with backtracking line-search. In: International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 2020. P. 1–10.
Polyak B.T. Gradient methods for minimizing functionals (in Russian) // Zh. Vychisl. Mat. Mat. Fiz. 1963. P. 643–653.
Łojasiewicz S. A topological property of real analytic subsets (in French) // Coll. du CNRS, Les équations aux dérivos partielles. 1963. P. 87–89.
Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition // Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19–23, 2016, Proceedings, Part I 16. Springer International Publishing, 2016. P. 795–811.
Freund R.M., Grigas P., Mazumder R. An extended Frank–Wolfe method within face directions, and its application to low-rank matrix completion // SIAM Journal on Optimization. 2017. V. 27 (2.1). P. 319–346.
100,000 ratings and 3,600 tag applications applied to 9,000 movies by 600 users. Last updated 9/2018. https://grouplens.org/datasets/movielens/
Vapnik V. The Nature of Statistical Learning Theory. Springer. 2013.
Clarkson K.L. Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm // ACM Transactions on Algorithms. 2010. V. 6 (2.4). P. 1–30.
Pima Indians Diabetes Database. https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database
Ivanov V.K., Vasin V.V., Tanana V.P. Theory of linear ill-posed problems and its applications. Walter de Gruyter. 2013.
LIBSVM Data: Classification (Binary Class). https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/binary.html
Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Журнал вычислит. матем. и матем. физ. 1966. Т. 6. № 5. С. 787–823.
Candes E.J., Recht B. Exact matrix completion via convex optimization // Foundations of Computational Mathematics. 2009. V. 9 (2.6). P. 717–772.
Combettes C.W., Pokutta S. Complexity of Linear Minimization and Projection on Some Sets // Operations Research Letters. 2021. V. 49 (2.4). P. 565–571.
Frank M., Wolfe P. An algorithm for quadratic programming // Naval Research Logistics Quarterly. 1956. V. 3 (1–2). P. 95–110.
Дополнительные материалы отсутствуют.
Инструменты
Программирование
Пн.-пт.: 10.00-19.00