УДК 519.85
MSC: 90C25, 90С06, 49J52
DOI: 10.21538/0134-4889-2021-27-4-175-188
Полный текст статьи (Full text)
Исследования разд. 2 и 3 выполнены при поддержке гранта Президента Российской Федерации для государственной поддержки молодых российских ученых — кандидатов наук, код МК-15.2020.1. Результаты разд. 4 получены Ф. С. Стонякиным при поддержке гранта Российского научного фонда, код 21-71-30005.
В статье исследован универсальный метод градиентного типа для задач выпуклой минимизации с относительной точностью, а также получены новые результаты о линейной скорости сходимости специальных вариантов субградиентного метода для задач с острым минимумом и некоторыми обобщениями выпуклости. Предложен новый подход к выбору параметров и правилу остановки адаптивного варианта метода подобных треугольников на классе задач минимизации выпуклых положительно однородных функционалов. Это позволило получить аналог универсального градиентного метода для задач с относительной точностью и доказать оптимальную оценку его скорости сходимости на выделенном классе задач. Приведен пример результатов численных экспериментов, иллюстрирующих возможность повышения качества выдаваемого методом приближенного решения по сравнению с теоретической оценкой за счет введенного адаптивного критерия остановки. Рассмотрен вариант субградиентного метода для задач минимизации слабо $\beta$-квазивыпуклых липшицевых функционалов в случае острого минимума, и доказана линейная скорость сходимости. Наконец, предложен вариант субградиентного метода, который сходится с линейной скоростью на классе задач минимизации квазивыпуклых гельдеровых функционалов с острым минимумом. Показана применимость этого результата для функционалов со слабым острым минимумом (гельдеровым ростом), и сформулировано следствие для задач с относительной точностью.
Ключевые слова: относительная точность, выпуклый положительно однородный функционал, слабо $\beta$-квазивыпуклый функционал, субградиентный метод, липшицев функционал, квазивыпуклый функционал
СПИСОК ЛИТЕРАТУРЫ
1. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МЦНМО, 2021. 272 с.
2. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. 384 с.
3. Нестеров Ю. Е. Алгоритмическая выпуклая оптимизация: дис. …докт. физ.-мат. наук. М.: Моск. физ.-техн. ин-т, 2013. 367 с.
4. Нестеров Ю. Е. Эффективные методы нелинейного программирования. М.: Радио и связь, 1989. 301 с.
5. Нестеров Ю. Е. Методы выпуклой оптимизации. М.: МЦНМО, 2010. 281 с.
6. Поляк Б. Т. Минимизация негладких функционалов // Журн. вычисл. математики и мат. физики. 1969. Т. 9, № 3. C. 509–521.
7. Тюрин А. И., Гасников А. В. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим $(\delta, L)$-модель функции в запрошенной точке // Журн. вычисл. математики и мат. физики. 2019. Т. 59, № 7. C. 1137–1150. doi: 10.1134/S0044466919070081
8. Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle // Math. Programming. 2014. Vol. 146, no. 1. P. 37–75.
9. Hardt M., Ma T., Recht B. Gradient descent learns linear dynamical systems // J. of Machine Learning Research. 2018. Vol. 19, no. 29. P. 1–44.
10. Hinder O., Sidford A., Sohoni N. S. Near-optimal methods for minimizing star-convex functions and beyond // Proceedings of Machine Learning Research. 2020. Vol. 125. P. 1894–1938.
11. Hu Y., Li J., Yu C. K. W. Convergence rates of subgradient methods for quasi-convex optimization problems. 2019. 28 p. URL: arXiv:1910.10879 [math.OC] .
12. Jiang R., Li X. Holderian error bounds and Kurdyka–Lojasiewicz inequality for the trust region subproblem. 2020. 30 p URL: arXiv:1911.11955 [math.OC] .
13. Johnstone P. R., Moulin P. Faster subgradient methods for functions with Holderian growth. 2018. 50 p. URL: arXiv:1704.00196 [math.OC] .
14. Liu M., Yang T. Adaptive accelerated gradient converging methods under Holderian error bound condition // Proc. 31st Intern. Conf. on Neural Information Processing Systems (NIPS’17). 2017. P. 3107–3117. ISBN: 9781510860964.
15. Nesterov Yu. Rounding of convex sets and efficient gradient methods for linear programming problems // Optimization Methods and Software. 2008. Vol. 23, no. 1. P. 109–128. doi: 10.1080/10556780701550059
16. Nesterov Yu. Unconstrained convex minimization in relative scale // Math. Oper. Res. 2009. Vol. 34, no. 1. P. 180–193. doi: 10.1287/moor.1080.0348
17. Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Programming. 2015. Vol. 152, no. 1-2(A). P. 381–404. doi: 10.1007/s10107-014-0790-0
Поступила 19.07.2021
После доработки 1.09.2021
Принята к публикации 6.09.2021
Стонякин Федор Сергеевич
д-р физ.-мат. наук
доцент
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: fedyor@mail.ru
Аблаев Сейдамет Серверович
аспирант
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: seydamet.ablaev@yandex.ru
Баран Инна Викторовна
канд. физ.-мат. наук
старший преподаватель
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: matemain@mail.ru
Ссылка на статью: Ф.С. Стонякин, С.С. Аблаев, И.В. Баран. Адаптивные методы градиентного типа для задач оптимизации с относительной точностью и острым минимумом // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 4. С. 175-188
English
F.S. Stonyakin, S.S. Ablaev, I.V. Baran. Adaptive gradient-type methods for optimization problems with relative error and sharp minimum
A universal method of gradient type for convex minimization problems with relative error is studied, and new results on the linear convergence rate of specific versions of the subgradient method for problems with a sharp minimum and some generalizations of convexity are obtained. A new approach to the choice of parameters and the stopping rule of an adaptive version of the method of similar triangles on a class of minimization problems for convex positively homogeneous functionals is proposed. As a consequence, an analog of the universal gradient method for problems with relative error is obtained and an optimal estimate of its convergence rate on a chosen class of problems is proved. An example of the results of numerical experiments illustrating the possibility of improving the quality of the approximate solution produced by the method as compared to a theoretical estimate due to the introduced adaptive stopping rule is given. A version of the subgradient method for minimization problems with weakly $\beta$-quasiconvex Lipschitz-continuous functionals in the case of a sharp minimum is considered, and a linear convergence rate is proved. Finally, a version of the subgradient method is proposed that converges at a linear rate on a class of problems of minimizing quasiconvex Holder-continuous functionals with a sharp minimum. The applicability of this result for functionals with a weak sharp minimum (Holderian growth) is shown and a corollary of this result is formulated for problems with relative error.
Keywords: relative error, convex positively homogeneous functional, weak $\beta$-quasiconvex functional, subgradient method, Lipschitz-continuous functional, quasiconvex functional
Received July 19, 2021
Revised September 1, 2021
Accepted September 6, 2021
Funding Agency: The research in Sects. 2 and 3 was supported by the Russian President’s Grant for Young Russian Scientists no. MK-15.2020.1. Stonyakin’s results in Sect. 4 were supported by the Russian Science Foundation grant (project no. 27-31-30005).
Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I.Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru
Seydamet Serverovich Ablaev, doctoral student, V.I.Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: seydamet.ablaev@yandex.ru
Inna Viktorovna Baran, Cand. Sci. (Phys.-Math.), V.I.Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: matemain@mail.ru
Cite this article as: F.S. Stonyakin, S.S. Ablaev, I.V. Baran. Adaptive gradient-type methods for optimization problems with relative error and sharp minimum, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 4, pp. 175–188.
[References -> on the "English" button bottom right]
