- Код статьи
- 10.31857/S0132347423060031-1
- DOI
- 10.31857/S0132347423060031
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 6
- Страницы
- 14-26
- Аннотация
- В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров Lk. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров Lk. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.
- Ключевые слова
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 20
Библиография
- 1. 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.
- 2. 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.
- 3. 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
- 4. Nesterov Y. Complexity bounds for primal-dual methods minimizing the model of objective function // Math. Program. 2018. V. 171 (1-2). P. 311–330.
- 5. Nesterov Y. Universal gradient methods for convex optimization problems // Math. Program. A 2015. V. 152. P. 381–404.
- 6. 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.
- 7. Polyak B.T. Gradient methods for minimizing functionals (in Russian) // Zh. Vychisl. Mat. Mat. Fiz. 1963. P. 643–653.
- 8. Łojasiewicz S. A topological property of real analytic subsets (in French) // Coll. du CNRS, Les équations aux dérivos partielles. 1963. P. 87–89.
- 9. 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.
- 10. 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.
- 11. 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/
- 12. Vapnik V. The Nature of Statistical Learning Theory. Springer. 2013.
- 13. Clarkson K.L. Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm // ACM Transactions on Algorithms. 2010. V. 6 (2.4). P. 1–30.
- 14. Pima Indians Diabetes Database. https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database
- 15. Ivanov V.K., Vasin V.V., Tanana V.P. Theory of linear ill-posed problems and its applications. Walter de Gruyter. 2013.
- 16. LIBSVM Data: Classification (Binary Class). https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/binary.html
- 17. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Журнал вычислит. матем. и матем. физ. 1966. Т. 6. № 5. С. 787–823.
- 18. Candes E.J., Recht B. Exact matrix completion via convex optimization // Foundations of Computational Mathematics. 2009. V. 9 (2.6). P. 717–772.
- 19. 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.
- 20. Frank M., Wolfe P. An algorithm for quadratic programming // Naval Research Logistics Quarterly. 1956. V. 3 (1–2). P. 95–110.
