Ф.С. Стонякин. Адаптация к величинам погрешностей для некоторых методов оптимизации градиентного типа ... С. 210-225

УДК 519.85

MSC: 90C25, 90С06, 65K10

DOI: 10.21538/0134-4889-2019-25-4-210-225

Полный текст статьи (Full text)

Работа выполнена при поддержке Российского научного фонда, проект 18-71-00048.

Введено новое понятие неточной модели выпуклой целевой функции, учитывающее возможность погрешностей при как задании функции, так и ее градиента. Для этой концепции предложен градиентный метод с адаптивной настройкой некоторых параметров модели, и получена оценка скорости сходимости. Эта оценка оптимальна на классе достаточно гладких задач при наличии погрешностей. Рассмотрен специальный класс задач выпуклой негладкой оптимизации, к которым применима предложенная методика за счет искусственного введения неточности. Показано, что для таких задач возможно модифицировать метод так, чтобы гарантированно имела место сходимость по функции со скоростью, близкой к оптимальной на классе задач выпуклой негладкой оптимизации. Предложен адаптивный градиентный метод для целевых функций с некоторой релаксацией условия липшицевости градиента, удовлетворяющих условию градиентного доминирования Поляка — Лоясиевича. При этом учитывается возможность неточного задания целевой функции и градиента. Адаптивный выбор параметров при работе метода выполняется как по величине константы Липшица градиента, так и по величине, соответствующей погрешности задания градиента и целевой функции. Обоснована линейная сходимость метода с точностью до величины, связанной с погрешностями.

Ключевые слова: градиентный метод, адаптивный метод, липшицев градиент, негладкая оптимизация, условие градиентного доминирования

СПИСОК ЛИТЕРАТУРЫ

1.   Necoara I., Nesterov Y. Glineur F. Linear convergence of first order methods for non-strongly convex optimization // Math. Program. 2019. Vol. 175. P. 69–107. doi: 10.1007/s10107-018-1232-1 

2.    Тюрин А. И., Гасников А. В. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим $(\delta,L)$-модель функции в запрошенной точке. // Журн. вычисл. математики и мат. физики. 2019. Т. 59, № 7. С. 1137–1150. doi: 10.1134/S0044466919070081 

3.   Stonyakin F. S., Dvinskikh D., Dvurechensky P., Kroshnin A., Kuznetsova O., Agafonov A., Gasnikov A., Tyurin A., Uribe C. A., Pasechnyuk D., Artamonov S. Gradient methods for problems with inexact model of the objective // Intern. Conf. on Mathematical optimization theory and operations research (MOTOR 2019): extended conference abstracts / eds. M. Khachay, Y. Kochetov, P. Pardalos. Cham: Springer, 2019. P. 97–114. (Lecture Notes in Computer Science; vol. 11548). doi: 10.1007/978-3-030-22629-9_8 

4.   Lu H., Freund R. M., Nesterov Y. Relatively smooth convex optimization by Firstorder methods, and applications. // SIAM J. Optim. 2018. Vol. 28, no 1. P. 333–354. doi: 10.1137/16M1099546 

5.   Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle. // Math. Program. 2014. Vol. 146, no. 1–2. P. 37–75. doi: 10.1007/s10107-013-0677-5 

6.   Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization: PhD thesis. 2013. 320 p.

7.   Nesterov Yu. Gradient methods for minimizing composite functions // Math. Program. 2013. Vol. 140, no. 1. P. 125–161. doi: 10.1007/s10107-012-0629-5 

8.   Нестеров Ю. Е. Алгоритмическая выпуклая оптимизация: дисс… д-р физ.-мат. наук: 01.01.07. М.: МФТИ, 2013. 367 с.

9.   Karimi H., Nutini J., Schmidt M. Linear сonvergence of пradient and зroximal-gradient methods under the Polyak–Lojasiewicz condition // Machine Learning and Knowledge Discovery in Databases / eds. B. Berendt etc. Cham: Springer, 2016. P. 795–811. (Lecture Notes in Computer Science; vol. 9851). doi: 10.1007/978-3-319-46128-1_50 

10.   Mordukhovich B. Variational analysis and generalized differentiation I, theory and examples. Berlin; Heidelberg: Springer-Verlag, 2006. 579 p. (Part of the Grundlehren der mathematischen Wissenschaften book series; vol 330). doi: 10.1007/3-540-31247-1 

11.   Поляк Б. Т. Градиентные методы минимизации функционалов // Журн. вычисл. математики и мат. физики. 1963. Том 3, № 4. C. 643–653. doi: 10.1016/0041-5553(63)90382-3 

12.   Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.

13.   Стонякин Ф. С. Аналог квадратичной интерполяции для специального класса негладких функционалов и одно его приложение к адаптивному методу зеркального спуска // Динамические системы. 2019. Т. 9 (37), № 1. С. 3–16.

14.   Mordukhovich B. S., Nam N. M. Applications of variational analysis to a generalized Fermat–Torricelli problem // J. Optim. Theory Appl. 2011. Vol. 148, no. 3. P. 431–454. doi: 10.1007/s10957-010-9761-7 

15.   Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука. Гл. редакция физ.-мат. литературы, 1979. 384 с.

16.   Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. 2015. Vol. 152, iss. 1-2. P. 381–404. doi: 10.1007/s10107-014-0790-0 

17.   D’Aspremont A. Smooth optimization with approximate gradient. // SIAM J. Optimi. 2008. Vol. 19, no. 3. P. 1171–1183. doi: 10.1137/060676386 

Поступила 8.09.2019

После доработки 21.10.2019

Принята к публикации 28.10.2019

Стонякин Федор Сергеевич
канд. физ.-мат. наук, доцент
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: fedyor@mail.ru

Ссылка на статью: Ф.С. Стонякин. Адаптация к величинам погрешностей для некоторых методов оптимизации градиентного типа // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 210-225.

English

F.S. Stonyakin. Adaptation to inexactness for some gradient-type optimization methods

We introduce a notion of inexact model of a convex objective function, which allows for errors both in the function and in its gradient. For this situation, a gradient method with an adaptive adjustment of some parameters of the model is proposed and an estimate for the convergence rate is found. This estimate is optimal on a class of sufficiently smooth problems in the presence of errors. We consider a special class of convex nonsmooth optimization problems. In order to apply the proposed technique to this class, an artificial error should be introduced. We show that the method can be modified for such problems to guarantee a convergence in the function with a nearly optimal rate on the class of convex nonsmooth optimization problems. An adaptive gradient method is proposed for objective functions with some relaxation of the Lipschitz condition for the gradient that satisfy the Polyak–Lojasievicz gradient dominance condition. Here, the objective function and its gradient can be given inexactly. The adaptive choice of the parameters is performed during the operation of the method with respect to both the Lipschitz constant of the gradient and a value corresponding to the error of the gradient and the objective function. The linear convergence of the method is justified up to a value associated with the errors.

Keywords: gradient method, adaptive method, Lipschitz gradient, nonsmooth optimization, gradient dominance condition

Received September 8, 2019

Revised October 21, 2019

Accepted October 28, 2019

Funding Agency: This work was supported by the Russian Science Foundation (project no. 18-71-00048).

Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru

Cite this article as: F.S.Stonyakin, Adaptation to inexactness for some gradient-type optimization methods, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 210–225 .