- Код статьи
- S3034533S0044466925070077-1
- DOI
- 10.7868/S303453325070077
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 65 / Номер выпуска 7
- Страницы
- 1156-1177
- Аннотация
- Статья посвящена адаптивным прямо-двойственным методам первого порядка для относительно гладких задач оптимизации с ограничениями-неравенствами, а также их приложениям к задачам восстановления малоранговых матриц. Показано, что для некоторого класса относительно гладких задач восстановления малоранговых матриц можно применять треугольное шкалированное свойство с коэффициентом шкалирования γ = 2, что открыло возможность применения для таких задач ускоренных методов и методов типа Франк–Вульфа и результатов об их вычислительных гарантиях. Предложен адаптивный вариант метода подобных треугольников для гладких задач относительно дивергенции Брегмана с треугольным шкалированным свойством с коэффициентом шкалирования γ = 2. Также предложены неускоренный и ускоренный прямо-двойственные адаптивные методы с неточным оракулом для относительно гладких задач. Ускоренный прямо-двойственный метод также есть аналог метода подобных треугольников и использует треугольное шкалированное свойство дивергенции Брегмана с коэффициентом шкалирования γ = 2. Ключевая особенность исследования в статье методов — возможность использования на итерациях неточной информации и учета неточности решения вспомогательных подзадач на итерациях методов. Это естественно ввиду усложнения таких подзадач в силу использования дивергенции (расхождения) Брегмана вместо квадрата евклидовой нормы. В частности, это привело к варианту метода Франк–Вульфа для выделенного класса относительно гладких задач. Для всех предложенных методов получены теоретические результаты о качестве выдаваемого решения.
- Ключевые слова
- прямо-двойственный метод метод подобных треугольников метод Франк–Вульфа относительная гладкость неточный оракул треугольное шкалированное свойство малоранговая матрица
- Дата публикации
- 23.04.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 12
Библиография
- 1. Nesterov Yu. Lectures on convex optimization, volume 137. Springer, 2018.
- 2. Beck A. First-order methods in optimization. SIAM, 2017.
- 3. Lu H. Relative continuity for non-lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent // INFORMS Journal on Optimization. 2019. 1(4):288–303.
- 4. Teboulle M., Bauschke H., Bolte J. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications // Math. Oper. Res. 2017. 42(2):330–348.
- 5. Lu H., Freund R., Nesterov Yu. Relatively smooth convex optimization by first-order methods, and applications // SIOPT. 2018. 28(1):333--354.
- 6. Nesterov Yu. Implementable tensor methods in unconstrained convex optimization // Math. Program. 2021. 186:157--183.
- 7. Nesterov Yu. Inexact accelerated high-order proximal-point methods // Math. Program. 2023. P. 1--26.
- 8. Bertero M., Boccacci P., Desidera G., Vicidomini G. Image deblurring with poisson data: from cells to galaxies // Inverse Probl. 2009. 25(12):123006.
- 9. Csiszar I. Why least squares and maximum entropy? an axiomatic approach to inference for linear inverse problems // Ann. Stat. 1991. 19(4):2032--2066.
- 10. Wolfowitz J., Kiefer J. Optimum designs in regression problems // Ann. Math. Stat. 1959. 30(2):271--294.
- 11. Anwood C.L. Optimal and efficient designs of experiments // Ann. Math. Stat. 1969. P. 1570--1602.
- 12. Zhou Y., Liang Y., Shen L. A simple convergence analysis of bregman proximal gradient algorithm // Comput. Optim. Appl. 2019. 73:903--912.
- 13. Dragomir R.A. Bregman gradient methods for relatively-smooth optimization PhD thesis, UT1 Capitole, 2021.
- 14. Xiao L., Hanzely F., Richtarik P. Accelerated bregman proximal gradient methods for relatively smooth convex optimization // Comput. Optim. Appl. 2021. 79:405--440.
- 15. Bolte J., Dragomir R.A., d'Aspremont A. Quartic first-order methods for low-rank minimization // J. Optim. Theory Appl. 2021. 189:341--363.
- 16. Monteiro R., Burer S. Local minima and convergence in low-rank semidefinite programming // Math. Program. 2005. 103(3):427--444.
- 17. Nocedal J., Bottou L., Curtis F. Optimization methods for large-scale machine learning // SIAM review. 2018. 60(2):223--311.
- 18. Bengio Y., Bergstra J. Random search for hyper-parameter optimization // JMLR. 2012. 13(2).
- 19. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МЦНМО, 2021.
- 20. Artamonov S., Piskunova V., Stonyakin F., Tyurin A., Gasnikov A., Dvurechensky P., Agafonov A., Divinskikh D., Alkousa M., Pasechnyyuk D. Inexact model: A framework for optimization and variational inequalities // Optim. Methods Softw. 2021. 36(6):1155--1201.
- 21. Тюрин А.И. Прямо-двойственный быстрый градиентный метод с моделью // Компьютерные исследования и моделирование. 2020. 12(2):263--274.
- 22. Nesterov Yu. Primal-dual subgradient methods for convex problems // Math. Program. 2009. 120(1):221--259.
- 23. Гасников А.В., Тюрин А.И. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим (δ, l)-модель функции в запрошенной точке // Ж. вычисл. матем. и матем. физ. 2019. 59(7):1137--1150.
- 24. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization. 2012. 01.
- 25. Dragomir R.A., Taylor A., d'Aspremont A., Bolte J. Optimal complexity and certification of bregman first-order methods // Math. Program. 2021. 194, 04.
- 26. Bogolubsky L., Dvurechenskii P., Gasnikov A., Gusev G., Nesterov Yu., Raigorodskii A., Tikhonov A., Zhukovskii M. Learning supervised pagerank with gradient-based and gradient-free optimization methods // NeurIPS. 2016. 29.
- 27. Nesterov Yu., Devolder O., Gilneur F. First-order methods of smooth convex optimization with inexact oracle // Math. Program. 2014. 146:37--75.
- 28. Gasnikov A., Kamzolov D., Dvurechensky P. Universal intermediate gradient method for convex problems with inexact oracle // Optim. Methods Softw. 36(6):1289--1316, 2021.
- 29. Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. 2015. 152(1):381--404.
- 30. Нестеров Ю.Е., Гасников А.В., Двуреченский П.Е. Стожетические градиентные методы с неточным оракулом // Труды Московского физико-технического института. 2016. 8(1 (29)):41--91.
- 31. Hendrikx H., Xiao L., Bubeck S., Bach F., Massoulie L. Statistically preconditioned accelerated gradient method for distributed optimization, 2020.
- 32. Boyd S. Convex optimization. Cambridge UP, 2004.
- 33. Savchuk O.S., Alkousa M.S., Shushko A.S., Vyguzov A.A., Stonyakin F.S., Pasechnyuk D.A., Gasnikov A.V. Accelerated bregman gradient methods for relatively smooth and relatively lipschitz continuous minimization problems // arXiv preprint. 2024. arXiv:2411.16743.
- 34. Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function // Math. Program. 2018. 171(1):311--330.
- 35. Jaggi M. Revisiting frank-wolfe: Projection-free sparse convex optimization. 2013. V. 28. 01.
- 36. Nemirovski A., Harchaoui Z., Juditsky A. Conditional gradient algorithms for norm-regularized smooth convex optimization // Math. Program. 2013. 152. 02.
- 37. Harter A., Samaria F. Parameterisation of a stochastic model for human face identification // Proceedings of 1994 IEEE workshop on applications of computer vision. 1994. P. 138--142.
- 38. Bayandina A., Dwarechensky P., Gasnikov A., Stonyakin F., Titov A. Mirror descent and convex optimization problems with non-smooth inequality constraints. Large-scale and distributed optimization. 2018. P. 181--213.
- 39. Aivazian G.V., Stonyakin F.S., Pasechnyk D.A., Alkousa M.S., Raigorodsky A.M., Baran I.V. Adaptive variant of the frank–wolfe algorithm for convex optimization problems // Programming and Computer Software. 2023. 49(6):493--504.
