АДАПТИВНЫЕ ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ С НЕТОЧНЫМ ОРАКУЛОМ ДЛЯ ОТНОСИТЕЛЬНО ГЛАДКИХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И ИХ ПРИЛОЖЕНИЯ К ЗАДАЧАМ ВОССТАНОВЛЕНИЯ МАЛОРАНГОВЫХ МАТРИЦ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Статья посвящена адаптивным прямо-двойственным методам первого порядка для относительно гладких задач оптимизации с ограничениями-неравенствами, а также их приложениям к задачам восстановления малоранговых матриц. Показано, что для некоторого класса относительно гладких задач восстановления малоранговых матриц можно применять треугольное шкалированное свойство с коэффициентом шкалирования γ = 2, что открыло возможность применения для таких задач ускоренных методов и методов типа Франк–Вульфа и результатов об их вычислительных гарантиях. Предложен адаптивный вариант метода подобных треугольников для гладких задач относительно дивергенции Брегмана с треугольным шкалированным свойством с коэффициентом шкалирования γ = 2. Также предложены неускоренный и ускоренный прямо-двойственные адаптивные методы с неточным оракулом для относительно гладких задач. Ускоренный прямо-двойственный метод также есть аналог метода подобных треугольников и использует треугольное шкалированное свойство дивергенции Брегмана с коэффициентом шкалирования γ = 2. Ключевая особенность исследования в статье методов — возможность использования на итерациях неточной информации и учета неточности решения вспомогательных подзадач на итерациях методов. Это естественно ввиду усложнения таких подзадач в силу использования дивергенции (расхождения) Брегмана вместо квадрата евклидовой нормы. В частности, это привело к варианту метода Франк–Вульфа для выделенного класса относительно гладких задач. Для всех предложенных методов получены теоретические результаты о качестве выдаваемого решения.

Об авторах

О. С Савчук

ННУ МФТИ; Крымский федеральный университет им. В.И. Вернадского

Email: oleg.savchuk19@mail.ru
Долгопрудный, Россия; Симферополь, Россия

Ф. С Стонякин

ННУ МФТИ; Крымский федеральный университет им. В.И. Вернадского; Университет Нинополис

Email: fedvor@mail.ru
Долгопрудный, Россия; Симферополь,Россия; Нинополис,Россия

А. А Выгузов

ННУ МФТИ; Университет Нинополис

Email: al.vyguzov@yandex.ru
Долгопрудный, Россия; Нинополис,Россия

М. С Алкуса

Университет Нинополис

Email: m.alkousa@mnopolis.ru
Нинополис, Россия

А. В Гасников

ННУ МФТИ; Университет Нинополис

Email: gasnikov@yandex.ru
Долгопрудный, Россия; Нинополис, Россия

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025