УДК 519.85
MSC: 90C25, 90С06, 49J52
DOI: 10.21538/0134-4889-2020-26-3-198-210
Полный текст статьи (Full text)
Исследования Ф.С. Стонякина по разработке алгоритма 1 и доказательству теорем 1, 2 и 3, а также исследования И.В. Баран по разработке алгоритма 2 выполнены при поддержке гранта Президента Российской Федерации для государственной поддержки молодых российских ученых — кандидатов наук, код МК-15.2020.1.
В настоящей работе получены оценки скорости сходимости некоторых субградиентных методов для задачи минимизации негладкого выпуклого липшицева однородного функционала с относительной точностью по целевому функционалу при наличии функциональных ограничений. К таким задачам предлагается применять аналоги известных субградиентных схем с переключениями. Это позволяет рассматривать и некоторые классы не обязательно выпуклых функционалов ограничений. Получена оценка скорости сходимости адаптивного зеркального спуска с переключениями на классе слабо α-квазивыпуклых целевых функционалов и функционалов ограничений. Обоснована оценка скорости сходимости предложенного субградиентного метода с переключениями с относительной точностью по целевому функционалу для задач минимизации выпуклого однородного целевого функционала со слабо $\alpha$-квазивыпуклым функционалом ограничения. Рассмотрен также метод для задач минимизации выпуклого однородного липшицева функционала с унимодальным липшицевым функционалом ограничения и выведена оценка его скорости сходимости. Доказанные оценки скорости сходимости указывают на оптимальность предложенных алгоритмических процедур с точки зрения теории нижних оракульных оценок.
Ключевые слова: относительная точность, выпуклый однородный функционал, слабо $\alpha$-квазивыпуклый функционал, зеркальный спуск, липшицев функционал, унимодальный функционал
СПИСОК ЛИТЕРАТУРЫ
1. 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.
2. 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
3. Нестеров Ю. Е. Алгоритмическая выпуклая оптимизация: дис. … д-ра физ.-мат. наук / Моск. физ.-техн. ин-т. 2013. 367 с.
4. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. Москва: Наука, 1979. 384 с.
5. Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 174, № 1. С. 33–36.
6. Шор Н. З. Применение обобщенного градиентного спуска в блочном программировании // Кибернетика. 1967. № 3. C. 53–55.
7. Немировский А. С., Юдин Д. Б. Эффективные методы решения задач выпуклого программирования большой размерности // Экономика и мат. методы. 1979. № 2. С. 135–152.
8. Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A. Mirror descentand convex optimization problems with non-smooth inequality constraints // Large-Scale and Distributed Optimization / eds. Pontus GiselssonAnders Rantzer. Springer: Cham. 2018. P. 181–213. (Lect. Notes Math.; vol. 2227) doi: 10.1007/978-3-319-97478-1_8
9. Stonyakin F., Stepanov A., Gasnikov A., Titov A. Mirror descent for constrained optimization problems with large subgradient values of functional constraints // Компьютерные исследования и моделирование. 2020. Vol. 12, no. 2. P. 301–317. doi: 10.20537/2076-7633-2020-12-2-301-317
10. Стонякин Ф. С., Алкуса М. С., Степанов А. Н., Титов А. А. Адаптивные алгоритмы зеркального спуска для задач выпуклой и сильно выпуклой оптимизации с функциональными ограничениями // Дискретный анализ и исслед. операций. 2019. Т. 26, № 3. C. 88–114.
doi: 10.33048/daio.2019.26.636
11. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. Москва: Изд-во МФТИ, 2018. 286 c.
12. Гуминов С. В., Нестеров Ю. Е., Двуреченский П. Е., Гасников А. В. Прямо-двойственный ускоренный градиентный метод с одномерным поиском для выпуклых, невыпуклых и негладких задач оптимизации // Докл. РАН. 2019. Т. 485, № 1. C. 15–18. doi: 10.31857/S0869-5652485115-18
13. Hinder O., Sidford A., Sohoni N. S. Near-optimal methods for minimizing star-convex functions and beyond [e-resource]. 2019. 37 p. URL: https://arxiv.org/pdf/1906.11985.pdf
14. Ben-Tal A., Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2019. 647 p.
15. Нестеров Ю. Е. Эффективные методы нелинейного программирования. Москва: Радио и связь, 1989. 301 с.
Поступила 9.06.2020
После доработки 14.08.2020
Принята к публикации 24.08.2020
Стонякин Федор Сергеевич
канд. физ.-мат. наук
доцент
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: fedyor@mail.ru
Баран Инна Викторовна
канд. физ.-мат. наук
старший преподаватель
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: matemain@mail.ru
Ссылка на статью: Ф.С. Стонякин, И.В. Баран. О некоторых алгоритмах для условных задач оптимизации с относительной точностью по целевому функционалу // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 198-210
English
F.S. Stonyakin, I.V. Baran. On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional
Convergence rate estimates are derived for some subgradient methods for the problem of minimization of a nonsmooth convex Lipschitz homogeneous functional with relative accuracy with respect to the objective functional under functional constraints. It is proposed to apply analogs of known switching subgradient schemes to such problems, which allows us to consider some classes of nonconvex problems as well. A convergence rate estimate is obtained for the adaptive mirror descent with switchings on the class of weakly α-quasiconvex objective functionals and constraint functionals. A convergence rate estimate of a proposed subgradient method with switchings with relative accuracy with respect to the objective functional is proved for problems of minimization of a convex homogeneous objective functional with a weakly $\alpha$-quasiconvex constraint functional. We also consider a method for problems of minimization of a convex homogeneous Lipschitz functional with unimodal Lipschitz constraint functional and derive an estimate for its convergence rate. All convergence rate estimates proved in the paper show the optimality of the proposed algorithmic procedures from the viewpoint of the theory of lower oracle bounds.
Keywords: relative accuracy, convex homogeneous functional, weakly $\alpha$-quasiconvex functional, mirror descent, Lipschitz-continuous functional, unimodal functional
Received June 9, 2020
Revised August 14, 2020
Accepted August 24, 2020
Funding Agency: The research of F. Stonyakin in Algorithm 1 and Theorems 1, 2 and 3 and the research of I. Baran in Algorithm 2 was supported by the grant of the President of the Russian Federation for young Russian candidates of sciences, code MK-15.2020.1.
Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.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: Cite this article as: F.S. Stonyakin, I.V. Baran, On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 198–210.
[References -> on the "English" button bottom right]
