Журнал вычислительной математики и математической физики, 2019, T. 59, № 5, стр. 889-894

Адаптивный проксимальный метод для вариационных неравенств

А. В. Гасников^{1, 2, 3, *}, П. Е. Двуреченский^3, 4, **, Ф. С. Стонякин^5, 1, ***, А. А. Титов^1, ****

¹ МФТИ
114070 Долгопрудный, М.о., Институтский пер., 9, Россия

² Высшая школа экономики
125319 Москва, Кочновский пр., 3, Россия

³ Ин-т проблем передачи информации РАН
127051 Москва, Большой Каретный пер., 19, Россия

⁴ Weierstrass Institute for Applied Analysis and Stochastics
10117 Berlin, Mohrenstr, 39, Германия

⁵ Крымский федеральный ун-т
295007 Симферополь, пр-т акад. Вернадского, 4, Россия

^* E-mail: gasnikov@yandex.ru
^** E-mail: pavel.dvurechensky@gmail.com
^*** E-mail: fedyor@mail.ru
^**** E-mail: a.a.titov@phystech.edu

Поступила в редакцию 11.12.2017
После доработки 19.12.2018
Принята к публикации 19.12.2018

DOI: 10.1134/S0044466919050077

Полный текст (PDF)

Аннотация

Предлагается новый аналог проксимального зеркального метода А.С. Немировского с адаптивным выбором констант в минимизируемых прокс-отображениях на каждой итерации для вариационных неравенств с липшицевым полем. Получены оценки необходимого числа итераций для достижения заданного качества решения вариационного неравенства. Показано, как можно обобщить предлагаемый подход на случай гельдерова поля. Рассмотрена модификация предлагаемого алгоритма в случае неточного оракула для оператора поля. Библ. 17.

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

Вариационные неравенства (ВН) нередко возникают в самых разных проблемах оптимизации и имеют многочисленные приложения в математической экономике, математическом моделировании транспортных потоков, теории игр и других разделах математики (см., например [1]). Исследования в области методики решения ВН активно продолжаются (см., например, [2]–[12]).

Наиболее известным аналогом градиентного метода для ВН является экстраградиентный метод Г.М. Корпелевич [13]. Одним из современных вариантов экстраградиентного метода является проксимальный зеркальный метод А.С. Немировского [10]. Недавно Ю.Е. Нестеровым в [14] предложен новый алгоритм решения задач выпуклой минимизации с адаптивным выбором констант, который в случае липшицевости градиента целевой функции не требует знания этой константы Липшица (см. также [15], разд. 5). В настоящей статье мы на базе разработанного нами критерия (5) предлагаем похожий аналог проксимального зеркального метода А.С. Немировского для решения вариационных неравенств (алгоритм 1). Также мы распространяем предлагаемую методику на постановку задачи нахождения решения вариационного неравенства с неточным оракулом для оператора поля (алгоритм 2).

Для некоторого оператора $g:Q \to {{\mathbb{R}}^{n}}$, заданного на выпуклом компакте $Q \subset {{\mathbb{R}}^{n}}$, будем рассматривать сильные вариационные неравенства вида

(1)

$\left\langle {g({{x}_{ * }}),{{x}_{ * }} - x} \right\rangle \leqslant 0,$

где $g$ удовлетворяет условию Липшица. Отметим, что в (1) требуется найти ${{x}_{ * }} \in Q$ (это ${{x}_{ * }}$ и называется решением ВН), для которого

(2)

$\mathop {max}\limits_{x \in Q} \left\langle {g({{x}_{ * }}),{{x}_{ * }} - x} \right\rangle \leqslant 0.$

В случае монотонного поля $g$ наш подход позволяет рассматривать также слабые вариационные неравенства

(3)

$\left\langle {g(x),{{x}_{ * }} - x} \right\rangle \leqslant 0.$

Обычно в (3) требуется найти ${{x}_{ * }} \in Q$, для которого (3) верно при всех $x \in Q$.

Начнем с некоторых вспомогательных понятий, соглашений и обозначений. Всюду далее будем полагать, что множество $Q$ выпукло и компактно в пространстве ${{\mathbb{R}}^{n}}$ с нормой $\left\| {\, \cdot \,} \right\|$ (вообще говоря, не евклидовой), а ${{\left\| {\, \cdot \,} \right\|}_{ * }}$ – сопряженная к $\left\| {\, \cdot \,} \right\|$ норма. Пусть задана 1-сильно выпуклая функция $d$ относительно $\left\| {\, \cdot \,} \right\|$, которая дифференцируема во всех точках $x \in Q$. Можно ввести соответствующую $d$ дивергенцию Брэгмана

(4)

$V(x,y) = d(x) - d(y) - \left\langle {\nabla d(y),x - y} \right\rangle \quad \forall x,y \in Q,$

где $\left\langle { \cdot , \cdot } \right\rangle $ – скалярное произведение в ${{\mathbb{R}}^{n}}$.

Для решения задачи (1), (2) мы предлагаем следующий адаптивный проксимальный зеркальный метод (АПЗМ). Пусть заданы число $\varepsilon > 0$ (точность решения) и начальное приближение ${{x}^{0}} = {\text{arg}}\mathop {min}\limits_{x \in Q} d(x) \in Q$.

Опишем ($N + 1$)-ю итерацию предлагаемого алгоритма ($N = 0,1,2,...$), положив изначально $N: = 0$.

Алгоритм 1: АПЗМ

Шаг 1. $N: = N + 1$, ${{L}^{{N + 1}}}: = {{L}^{N}}{\text{/}}2$.

Шаг 2. Вычисляем

${{y}^{{N + 1}}}: = {\text{arg}}\mathop {min}\limits_{x \in Q} \left\{ {\left\langle {g({{x}^{N}}),x - {{x}^{N}}} \right\rangle + {{L}^{{N + 1}}}V(x,{{x}^{N}})} \right\},$

${{x}^{{N + 1}}}: = {\text{arg}}\mathop {min}\limits_{x \in Q} \left\{ {\left\langle {g({{y}^{{N + 1}}}),x - {{x}^{N}}} \right\rangle + {{L}^{{N + 1}}}V(x,{{x}^{N}})} \right\}.$

Шаг 3. Если верно

(5)

$\left\langle {g({{y}^{{N + 1}}}) - g({{x}^{N}}),{{y}^{{N + 1}}} - {{x}^{{N + 1}}}} \right\rangle \leqslant {{L}^{{N + 1}}}V({{y}^{{N + 1}}},{{x}^{N}}) + {{L}^{{N + 1}}}V({{x}^{{N + 1}}},{{y}^{{N + 1}}}),$

то переходим к следующей итерации (шаг 1).

Шаг 4. Если не выполнено (5), то увеличиваем ${{L}^{{N + 1}}}$ в 2 раза: ${{L}^{{N + 1}}}: = 2{{L}^{{N + 1}}}$ и переходим к шагу 2.

Шаг 5. Критерий остановки метода:

$\sum\limits_{k = 0}^{N - 1} \tfrac{1}{{{{L}^{{k + 1}}}}} \geqslant \tfrac{{{{R}^{2}}}}{\varepsilon },\quad {\text{г д е }}\quad {{R}^{2}} = \mathop {max}\limits_{x \in Q} V(x,{{x}^{0}}).$

Теорема 1. После остановки алгоритма 1 справедлива оценка:

(6)

$\sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant V(x,{{x}^{0}}) - V(x,{{x}^{N}}).$

Доказательство. Непосредственно можно проверить равенства:

(7)

$\left\langle {{{{\left. {{{\nabla }_{x}}V(x,{{x}^{k}})} \right|}}_{{x = {{x}^{{k + 1}}}}}},x - {{x}^{{k + 1}}}} \right\rangle = V(x,{{x}^{k}}) - V(x,{{x}^{{k + 1}}}) - V({{x}^{{k + 1}}},{{x}^{k}}),$

(8)

$\left\langle {{{{\left. {{{\nabla }_{x}}V(x,{{x}^{k}})} \right|}}_{{x = {{y}^{{k + 1}}}}}},x - {{y}^{{k + 1}}}} \right\rangle = V(x,{{x}^{k}}) - V(x,{{y}^{{k + 1}}}) - V({{y}^{{k + 1}}},{{x}^{k}}).$

Далее, для всякого $x \in Q$ и $k = \overline {0,N - 1} $ верны неравенства:

$\left\langle {{{{\left. {{{\nabla }_{x}}\left( {\left\langle {g({{x}^{k}}),x - {{x}^{k}}} \right\rangle + {{L}^{{k + 1}}}V(x,{{x}^{k}})} \right)} \right|}}_{{x = {{y}^{{k + 1}}}}}},x - {{y}^{{k + 1}}}} \right\rangle \geqslant 0,$

$\left\langle {{{{\left. {{{\nabla }_{x}}\left( {\left\langle {g({{y}^{{k + 1}}}),x - {{x}^{k}}} \right\rangle + {{L}^{{k + 1}}}V(x,{{x}^{k}})} \right)} \right|}}_{{x = {{x}^{{k + 1}}}}}},x - {{x}^{{k + 1}}}} \right\rangle \geqslant 0.$

Поэтому

$\left\langle {g({{y}^{{k + 1}}}),{{x}^{{k + 1}}} - x} \right\rangle \leqslant {{L}^{{k + 1}}}V(x,{{x}^{k}}) - {{L}^{{k + 1}}}V(x,{{x}^{{k + 1}}}) - {{L}^{{k + 1}}}V({{x}^{{k + 1}}},{{x}^{k}})$

$\left\langle {g({{x}^{k}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant {{L}^{{k + 1}}}V(x,{{x}^{k}}) - {{L}^{{k + 1}}}V(x,{{y}^{{k + 1}}}) - {{L}^{{k + 1}}}V({{y}^{{k + 1}}},{{x}^{k}}),$

откуда для всякого $k = \overline {0,N - 1} $ с учетом (5) мы имеем

$\begin{gathered} \left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle = \left\langle {g({{y}^{{k + 1}}}),{{x}^{{k + 1}}} - x} \right\rangle + \left\langle {g({{x}^{k}}),{{y}^{{k + 1}}} - {{x}^{{k + 1}}}} \right\rangle + \left\langle {g({{y}^{{k + 1}}}) - g({{x}^{k}}),{{y}^{{k + 1}}} - {{x}^{{k + 1}}}} \right\rangle \leqslant \\ \leqslant \;{{L}^{{k + 1}}}V(x,{{x}^{k}}) - {{L}^{{k + 1}}}V(x,{{x}^{{k + 1}}}) - {{L}^{{k + 1}}}V({{x}^{{k + 1}}},{{x}^{k}}) + {{L}^{{k + 1}}}V({{x}^{{k + 1}}},{{x}^{k}}) - \\ - \;{{L}^{{k + 1}}}V({{x}^{{k + 1}}},{{y}^{{k + 1}}}) - {{L}^{{k + 1}}}V({{y}^{{k + 1}}},{{x}^{k}}) + {{L}^{{k + 1}}}V({{y}^{{k + 1}}},{{x}^{k}}) + {{L}^{{k + 1}}}V({{x}^{{k + 1}}},{{y}^{{k + 1}}}), \\ \end{gathered} $

т.е. верно неравенство

(9)

$\frac{1}{{{{L}^{{k + 1}}}}}\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant V(x,{{x}^{k}}) - V(x,{{x}^{{k + 1}}}).$

После суммирования неравенств (9) по $k = \overline {0,N - 1} $ получим

$\sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant V(x,{{x}^{0}}) - V(x,{{x}^{N}}),$

что и требовалось.

Допустим, что векторное поле $g$ удовлетворяет условию

(10)

$\left\| {g(x) - g(y)} \right\| \leqslant L\left\| {x - y} \right\|\quad \forall x,y \in Q.$

Всюду далее для краткости будем обозначать

${{S}_{N}} = \sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}.$

Условие (10) означает, что для произвольных $x,y,z \in Q$

$\left\langle {g(y) - g(z),y - z} \right\rangle \leqslant {{\left\| {g(y) - g(x)} \right\|}_{ * }}\left\| {y - z} \right\| \leqslant L\left\| {y - x} \right\|\left\| {y - z} \right\|,$

откуда в силу справедливого для всех $a,b \in \mathbb{R}$ неравенства $ab \leqslant \tfrac{{{{a}^{2}}}}{2} + \tfrac{{{{b}^{2}}}}{2}$ при произвольных $x,y,z \in Q$ верно

$\left\langle {g(y) - g(x),y - z} \right\rangle \leqslant \frac{L}{2}{{\left\| {y - x} \right\|}^{2}} + \frac{L}{2}{{\left\| {y - z} \right\|}^{2}} \leqslant LV(y,x) + LV(z,y).$

Тогда ввиду (6) для всякого $x \in Q$

$\mathop {min}\limits_{k = \overline {0,N - 1} } \left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \frac{1}{{{{S}_{N}}}}\sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \frac{1}{{{{S}_{N}}}}(V(x,{{x}^{0}}) - V(x,{{x}^{N}})) \leqslant \frac{{{{R}^{2}}}}{{{{S}_{N}}}},$

где

${{R}^{2}} = \mathop {max}\limits_{x \in Q} V(x,{{x}^{0}})$.

Если потребовать, чтобы

(11)

$\mathop {max}\limits_{x \in Q} \mathop {min}\limits_{k = \overline {0,N - 1} } \left\{ {\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle } \right\} \leqslant \frac{1}{{{{S}_{N}}}}\mathop {max}\limits_{x \in Q} \sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \varepsilon ,$

то в случае ${{L}^{0}} \leqslant 2L$ можно оценить количество итераций работы алгоритма 1. Действительно, ${{L}^{0}} \leqslant 2L$ означает, что ${{L}^{{k + 1}}} \leqslant 2L$ для всякого $k = \overline {0,N - 1} $ и поэтому верно

$\frac{{{{R}^{2}}}}{{{{S}_{N}}}} \leqslant \varepsilon \quad {\text{п р и }}\quad N \geqslant \frac{{2L{{R}^{2}}}}{\varepsilon }.$

Таким образом, справедлива следующая

Теорема 2. Если выполнено условие (10) для поля $g$, то алгоритм 1 работает не более

(12)

$N = \left\lceil {\frac{{2L{{R}^{2}}}}{\varepsilon }} \right\rceil $

итераций. Если выбрать ${{L}^{0}} \leqslant 2L$, то верно (11).

Замечание 1. Если $g\not { \equiv }0$, то выполнения условия ${{L}^{0}} \leqslant 2L$ можно добиться, выбрав

${{L}^{0}}: = \frac{{{{{\left\| {g(x) - g(y)} \right\|}}_{ * }}}}{{\left\| {x - y} \right\|}}\quad {\text{п р и }}\quad g(x) \ne g(y).$

Замечание 2. Заметим, что оценка числа итераций (12) с точностью до числового множителя оптимальна для вариационных неравенств [9], [16], [17].

Замечание 3. Отметим, что похожими рассуждениями можно получить аналог теоремы 2 для гельдерова поля $g$. Точнее говоря, если справедливо

(13)

${{\left\| {g(x) - g(y)} \right\|}_{ * }} \leqslant {{L}_{\nu }}{{\left\| {x - y} \right\|}^{\nu }}$

при $\nu \in [0;1],x,y \in Q$, причем ${{L}_{0}} < + \infty $ (другие константы ${{L}_{\nu }}$ могут быть бесконечными), то утверждение теоремы 2 выполняется, если

(14)

${{L}^{0}} \leqslant 2L = 2\mathop {inf}\limits_{\nu \in [0;1]} {{L}_{\nu }}\mathop {\left( {\frac{{2{{L}_{\nu }}}}{\varepsilon }} \right)}\nolimits^{\tfrac{{1 - \nu }}{{1 + \nu }}} $

(15)

$N = \left\lceil {\mathop {inf}\limits_{\nu \in [0;1]} \mathop {\left( {\frac{{2{{L}_{\nu }}{{R}^{{1 + \nu }}}}}{\varepsilon }} \right)}\nolimits^{\tfrac{2}{{1 + \nu }}} } \right\rceil .$

Замечание 4. Для слабых ВН (4) имеем

$\left\langle {g(x),{{y}^{{k + 1}}} - x} \right\rangle = \left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle + \left\langle {g(x) - g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \left\langle {g({{y}^{{k + 1}}}),{{y}^{{k + 1}}} - x} \right\rangle ,$

поэтому критерий (11) можно заменить на

(16)

$\mathop {max}\limits_{x \in Q} \left\langle {g(x),\tilde {y} - x} \right\rangle \leqslant \varepsilon ,\quad {\text{г д е }}\quad \tilde {y} = \frac{{\sum\limits_{k = 0}^{N - 1} \tfrac{1}{{{{L}^{{k + 1}}}}}{{y}^{{k + 1}}}}}{{{{S}_{N}}}}.$

Отметим, что именно оценку вида (16) обычно используют как критерий качества решения слабого ВН (см., например [10]).

В завершение отметим, что рассматриваемую в работе методику можно распространить на случай неточного оракула $\tilde {g}(x,{{\delta }_{c}},{{\delta }_{u}})$ для поля $g$. Поясним смысл, который мы вкладываем в это понятие.

Будем полагать, что существует фиксированное ${{\delta }_{u}} > 0$ такое, что для всякого ${{\delta }_{c}} > 0$ существует константа $L({{\delta }_{c}}) \in (0, + \infty )$, для которой $\forall x,y,z \in Q$ верно

(17)

$\left\langle {\tilde {g}(y,{{\delta }_{c}},{{\delta }_{u}}) - \tilde {g}(x,{{\delta }_{c}},{{\delta }_{u}}),y - z} \right\rangle \leqslant L({{\delta }_{c}})\left( {V(y,x) + V(z,y)} \right) + {{\delta }_{c}} + {{\delta }_{u}}.$

Замечание 5. Заметим, что мы здесь считаем, что ${{\delta }_{c}}$ – контролируемая погрешность оракула (ее возможно бесконечно уменьшать и для заданной точности решения $\varepsilon > 0$ мы всюду будем полагать, что ${{\delta }_{c}} = \tfrac{\varepsilon }{2}$). С другой стороны, погрешность ${{\delta }_{u}}$ мы полагаем неконтролируемой.

Пример 1. Пусть поле $g$ удовлетворяет условию Липшица и заданы его неточные значения на $Q$, т.е. существует ${{\bar {\delta }}_{u}} > 0$ и в произвольной точке $x \in Q$ можно вычислить величину $\bar {g}(x)$, удовлетворяющую условию

${{\left\| {\bar {g}(x) - g(x)} \right\|}_{ * }} \leqslant {{\bar {\delta }}_{u}}$.

В таком случае $\bar {g}(x) = \tilde {g}(x,{{\delta }_{c}},{{\delta }_{u}})$ удовлетворяет (17), если положить ${{\delta }_{u}} = {{\bar {\delta }}_{u}}$, а также

${{\delta }_{c}} = 0\quad {\text{и }}\quad L({{\delta }_{c}}) \equiv L.$

При условиях (17) мы предлагаем следующую модификацию алгоритма 1. Пусть заданы $\varepsilon > 0$ (точность решения) и начальное приближение

${{x}^{0}} = {\text{arg}}\mathop {min}\limits_{x \in Q} d(x) \in Q$.

Опишем ($N + 1$)-ю итерацию предлагаемого алгоритма ($N = 0,1,2,\;...$), положив изначально $N: = 0$.

Алгоритм 2: “Неточный” АПЗМ

Шаг 1. $N: = N + 1$, ${{L}^{{N + 1}}}: = {{L}^{N}}{\text{/}}2$.

Шаг 2. Вычисляем:

${{y}^{{N + 1}}}: = {\text{arg}}\mathop {min}\limits_{x \in Q} \left\{ {\left\langle {\tilde {g}\left( {{{x}^{N}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),x - {{x}^{N}}} \right\rangle + {{L}^{{N + 1}}}V(x,{{x}^{N}})} \right\},$

${{x}^{{N + 1}}}: = {\text{arg}}\mathop {min}\limits_{x \in Q} \left\{ {\left\langle {\tilde {g}\left( {{{y}^{{N + 1}}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),x - {{x}^{N}}} \right\rangle + {{L}^{{N + 1}}}V(x,{{x}^{N}})} \right\}.$

Шаг 3. Если верно

$\left\langle {\tilde {g}({{y}^{{N + 1}}},\tfrac{\varepsilon }{2},{{\delta }_{u}}) - \tilde {g}({{x}^{N}},\tfrac{\varepsilon }{2},{{\delta }_{u}}),{{y}^{{N + 1}}} - {{x}^{{N + 1}}}} \right\rangle \leqslant {{L}^{{N + 1}}}V({{y}^{{N + 1}}},{{x}^{N}}) + {{L}^{{N + 1}}}V({{x}^{{N + 1}}},{{y}^{{N + 1}}}) + \frac{\varepsilon }{2} + {{\delta }_{u}},$

то переходим к следующей итерации (шаг 1).

Шаг 4. Иначе увеличиваем в 2 раза константу ${{L}^{{N + 1}}}: = 2{{L}^{{N + 1}}}$ и переходим к шагу 2.

Шаг 5. Критерий остановки метода

$\sum\limits_{k = 0}^{N - 1} \tfrac{1}{{{{L}^{{k + 1}}}}} \geqslant \tfrac{{2{{R}^{2}}}}{\varepsilon },\quad {\text{г д е }}\quad {{R}^{2}} = \mathop {max}\limits_{x \in Q} V(x,{{x}^{0}}).$

Аналогично доказательству теоремы 2 проверяется

Теорема 3. Пусть $\tilde {g}$ удовлетворяет (17). Тогда после остановки алгоритма 2 справедлива оценка:

(18)

$\frac{1}{{{{S}_{N}}}}\sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {\tilde {g}\left( {{{y}^{{k + 1}}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \frac{{V(x,{{x}^{0}}) - V(x,{{x}^{N}})}}{{{{S}_{N}}}} + \frac{\varepsilon }{2} + {{\delta }_{u}}.$

Неравенство (18) означает, что после работы алгоритма 2 будет верно:

(19)

$\frac{1}{{{{S}_{N}}}}\sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {\tilde {g}\left( {{{y}^{{k + 1}}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \frac{{2L{{R}^{2}}}}{N} + \frac{\varepsilon }{2} + {{\delta }_{u}},$

где

${{R}^{2}} = \mathop {max}\limits_{x,y \in Q} V(x,y)$.

При условии ${{L}^{0}} \leqslant 2L$ можно показать, что алгоритм 2 будет работать не более $N = \left\lceil {\tfrac{{4L{{R}^{2}}}}{\varepsilon }} \right\rceil $ итераций. После его остановки заведомо верно неравенство

$\mathop {max}\limits_{x \in Q} \mathop {min}\limits_{k = \overline {0,N - 1} } \left\langle {\tilde {g}\left( {{{y}^{{k + 1}}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \frac{1}{{{{S}_{N}}}}\mathop {max}\limits_{x \in Q} \sum\limits_{k = 0}^{N - 1} \frac{1}{{{{L}^{{k + 1}}}}}\left\langle {\tilde {g}\left( {{{y}^{{k + 1}}},\frac{\varepsilon }{2},{{\delta }_{u}}} \right),{{y}^{{k + 1}}} - x} \right\rangle \leqslant \varepsilon + {{\delta }_{u}},$

которое может рассматриваться как критерий качества найденного решения с погрешностью ${{\delta }_{u}}$.

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

Facchinei F., Pang J.S. Finite-Dimensional Variational Inequality and Complementarity Problems. New York: Springer, 2003. V. 1, 2. 693 p.
Антипин А.С. Методы решения вариационных неравенств со связанными ограничениями // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 9. С. 1291–1307.
Antipin A. Gradient approach of computing fixed points of equilibrium problems // J. of Global Optimizat. 2002. V. 24. № 3. P. 285–309.
Антипин А.С., Ячимович В., Ячимович М. Динамика и вариационные неравенства // Ж. вычисл. матем. и матем. физ. 2017. Т. 57. № 5. С. 783–800.
Коннов И.В. Модель миграционного равновесия с обратными функциями полезности // Уч. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2013. Т. 155. № 2. С. 91–99.
Коннов И.В., Салахутдин Р.А. Двухуровневый итеративный метод для нестационарных смешанных вариационных неравенств // Изв. вузов. Матем. 2017. № 10. С. 50–61.
Меленьчук Н.В. Методы и алгоритмы для решения задач математического моделирования на основе вариационных неравенств // Дисс. … канд. физ.-матем. наук. Омск: Омский гос. техн. ун-т, 2011.
Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация // Дисс. … докт. физ.-матем. наук. М.: Моск. физ.-техн. ин-т (гос. ун-т), 2013.
Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization // J. Complexity. 2015. V. 31. № 1. P. 1–14.
Nemirovski A. Prox-method with rate of convergence O(1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems // SIAM Journal on Optimization. 2004. V. 15. P. 229–251.
Nesterov Yu. Dual extrapolation and its application for solving variational inequalities and related problems // Math. Program. 2007. Ser. B. P. 319–344.
Nesterov Yu., Scrimali L. Solving strongly monotone variational and quasi-variational inequalities // Discrete and Continuous Dynamical Systems – A. 2011. V. 31. № 4. P. 1383–1396.
Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач // Экономика и матем. методы. Т. 12. № 4. С. 747–756.
Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. 2015. V. 152. № 1–2. P. 381–404.
Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: Изд-во МФТИ: 2018. 160 с. https://arxiv.org/abs/1711.00394.
Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. 384 с.
Nemirovski A. Information-based complexity of convex programming. Technion–Israel Institute of Technology. Fall Semester 1994/95. 268 p. Available at http://www2.isye.gatech.edu/ nemirovs/Lec_EMCO.pdf.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал