Сходимость брэгмановского экстраградиентного метода
Доказана сходимость нового варианта экстраградиентного метода для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами. В методе используется дивергенция
 Брэгмана вместо евклидового расстояния и новая регулировка величины шага, не требующая знания конс...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2019 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/158103 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Сходимость брэгмановского экстраградиентного метода / Я.И. Ведель, С.В. Денисов, В.В. Семёнов // Доповіді Національної академії наук України. — 2019. — № 5. — С. 18-23. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860035608529862656 |
|---|---|
| author | Ведель, Я.И. Денисов, С.В. Семёнов, В.В. |
| author_facet | Ведель, Я.И. Денисов, С.В. Семёнов, В.В. |
| citation_txt | Сходимость брэгмановского экстраградиентного метода / Я.И. Ведель, С.В. Денисов, В.В. Семёнов // Доповіді Національної академії наук України. — 2019. — № 5. — С. 18-23. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Доказана сходимость нового варианта экстраградиентного метода для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами. В методе используется дивергенция
Брэгмана вместо евклидового расстояния и новая регулировка величины шага, не требующая знания константы Липшица оператора. В отличие от применявшихся ранее правил выбора величины шага в предлагаемом методе не производится дополнительных вычислений значений оператора и прокс-отображения.
Доведено збіжність нового варіанта екстраградієнтного методу для наближеного розв’язання варіаційних
нерівностей з псевдомонотонними та ліпшицевими операторами. У методі використовується дивергенція
Брегмана замість евклідової відстані та нове регулювання величини кроку, що не вимагає знання константи Ліпшиця оператора. На відміну від правил вибору величини кроку, що застосовувалися раніше, в пропонованому методі не проводиться додаткових обчислень значень оператора та прокс-відображення.
The convergence of a new extragradient-type method for the approximate solution of variational inequalities
with pseudomonotonіс and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is
proved. The method uses the Bregman divergence instead of the Euclidean distance and the new adjustment of
the step size, which does not require knowledge of the Lipschitz constant of an operator. In contrast to the
previously used rules for choosing the step size, the proposed method does not perform additional calculations for
the operator values and prox-map.
|
| first_indexed | 2025-12-07T16:53:57Z |
| format | Article |
| fulltext |
18 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 5
ОПОВІДІ
НАЦІОНАЛЬНОЇ
АКАДЕМІЇ НАУК
УКРАЇНИ
ІНФОРМАТИКА ТА КІБЕРНЕТИКА
doi: https://doi.org/10.15407/dopovidi2019.05.018
УДК 517.988
Я.И. Ведель, С.В. Денисов, В.В. Семёнов
Киевский национальный университет им. Тараса Шевченко
E-mail: yana.vedel@gmail.com, sireukr@gmail.com, semenov.volodya@gmail.com
Сходимость брэгмановского экстраградиентного метода
Представлено членом-корреспондентом НАН Украины С.И. Ляшко
Доказана сходимость нового варианта экстраградиентного метода для приближенного решения вариаци-
онных неравенств с псевдомонотонными и липшицевыми операторами. В методе используется дивергенция
Брэгмана вместо евклидового расстояния и новая регулировка величины шага, не требующая знания кон-
станты Липшица оператора. В отличие от применявшихся ранее правил выбора величины шага в предла-
гаемом методе не производится дополнительных вычислений значений оператора и прокс-отображения.
Ключевые слова: вариационное неравенство, экстраградиентный метод, дивергенция Брэгмана, сходи-
мость.
Многие задачи исследования операций и математической физики могут быть записаны в
форме вариационных неравенств. Особенно популярны вариационные неравенства в ма-
тематической экономике, математическом моделировании транспортных потоков и теории
игр. Заметим, что с появлением генерирующих состязательных нейронных сетей (generative
adversarial network (GAN)) интерес к алгоритмам решения вариационных неравенств воз-
ник и в среде специалистов в области машинного обучения.
Наиболее известным обобщением метода проекции градиента для вариационных не-
равенств является экстраградиентный метод Г.М. Корпелевич [1]. Исследованию этого
алгоритма посвящено большое количество публикаций. В частности, предлагались моди-
фикации алгоритма Корпелевич с одним метрическим проектированием на допустимое
множество [2—6]. Одним из современных вариантов экстраградиентного метода является
проксимальный зеркальный метод А.С. Немировского [7]. Также интересный метод двой-
ственной экстраполяции предложил Ю.Е. Нестеров [8]. А недавно [9, 10] исследованы
двухэтапные проксимальные зеркальные методы – модификации двухэтапного прокси-
мального алгоритма [11] с использованием дивергенции Брэгмана вместо евклидового
расстояния.
В данном сообщении рассматривается брэгмановский экстраградиентный метод [7] с
новой регулировкой шага, не требующей знания константы Липшица оператора. В отличие
от применявшихся ранее правил выбора величины шага [5, 6, 12] в предлагаемом методе не
© Я.И. Ведель, С.В. Денисов, В.В. Семёнов, 2019
19ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 5
Сходимость брэгмановского экстраградиентного метода
производится дополнительных вычислений значений оператора и прокс-отображения. Для
вариационных неравенств с псевдомонотонными и липшицевыми операторами, действую-
щими в конечномерном линейном нормированном пространстве, доказана теорема сходи-
мости метода.
Постановка задачи и описание алгоритма. Пусть E — конечномерное действительное
линейное пространство. Это пространство снабдим нормой ⋅ . Двойственное простран-
ство обозначим E∗ . Для a E∗∈ и b E∈ будем обозначать через ( , )a b значение линейной
функции a в точке b . Двойственная норма ∗⋅ на E∗ определена стандартным способом:
*
max{( , ) : 1}a a b b= = .
Пусть C — непустое подмножество пространства E , A — оператор, действующий из E
в E∗. Рассмотрим вариационное неравенство:
найти x C∈ : ( , ) 0Ax y x− y C∀ ∈ , (1)
множество решений которого обозначим S .
Предположим, что выполнены следующие условия:
множество C E⊆ — выпуклое и замкнутое;
оператор :A E E∗→ — псевдомонотонный и липшицевый с константой 0L > на C ;
множество S не пусто.
Введем необходимые для формулировки алгоритма конструкции. Пусть функция
: { }Eϕ → = ∪ +∞ удовлетворяет условиям:
int dom Eϕ⊆ непустое выпуклое множество;
ϕ непрерывно дифференцируема на int dom ϕ ;
если int dom bd domnx xϕ ∋ → ∈ ϕ , то
*
( )nx∇ϕ → +∞ ;
ϕ сильно выпукла относительно нормы ⋅ с константой сильной выпуклости 0σ > :
2( ) ( ) ( ( ), )
2
a b b a b a b
σ
ϕ ϕ − ∇ϕ − + − doma∀ ∈ ϕ , int domb∈ ϕ .
Соответствующая функции ϕ дивергенция Брэгмана задается формулой [13]
( , ) ( ) ( ) ( ( ), )V a b a b b a b= ϕ −ϕ − ∇ϕ − doma∀ ∈ ϕ , int domb∈ ϕ .
Замечание 1. Примеры практически важных дивергенций Брэгмана приведены в [13].
Имеет место полезное 3-точечное тождество [13]:
( , ) ( , ) ( , ) ( ( ) ( ), )V a c V a b V b c b c a b= + + ∇ϕ −∇ϕ − . (2)
Из сильной выпуклости функции ϕ следует оценка
2( , )
2
V a b a b
σ
− doma∀ ∈ ϕ , int domb∈ ϕ . (3)
Пусть domK ⊆ ϕ — непустое замкнутое выпуклое множество, причем int domK ∩ ϕ =
= ∅. Рассмотрим сильно выпуклые задачи минимизации вида
( ) arg min { ( , ) ( , )}K
x y KP a a y x V y x∈= − − + a E∗∀ ∈ , int domx∈ ϕ . (4)
Известно [13], что задача (4) имеет единственное решение int domz K∈ ∩ ϕ , причем
( , ) ( ( ) ( ), ) 0a y z z x y z− − + ∇ϕ −∇ϕ − y K∀ ∈ . (5)
Отображение : int domK
xP E K∗ → ∩ ϕ называют прокс-отображением.
20 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 5
Я.И. Ведель, С.В. Денисов, В.В. Семёнов
Опишем предлагаемый алгоритм решения вариационного неравенства (1).
Алгоритм 1. Выбираем элемент 1 int domx ∈ ϕ , (0, )τ∈ σ и положительное число 1λ . По-
лагаем 1n = .
Шаг 1. Вычислить
( )
n
C
n x n ny P Ax= −λ .
Шаг 2. Если n ny x= , то СТОП, иначе вычислить
1 ( )
n
C
n x n nx P Ay+ = −λ ,
Шаг 3. Вычислить
1 *
( , )2
min , ,
,
n n
n
n n n
n
V y x
Ay Ax+
⎧ ⎧ ⎫⎪ ⎪⎪ λ τ⎨ ⎬⎪λ = σ −⎨ ⎪ ⎪⎩ ⎭
⎪
λ⎪⎩
если
,n nAx Ay≠
иначе.
Положить : 1n n= + и перейти на шаг 1.
Замечание 2. В отличие от правил выбора nλ из работ [5, 6, 12] в алгоритме 1 не произ-
водится дополнительных вычислений значений оператора A и прокс-отображения
n
C
xP .
Замечание 3. Последовательность ( )nλ неубывающая и ограничена снизу числом
1min ,
L
τ⎧ ⎫λ⎨ ⎬
⎩ ⎭
. Следовательно, существует lim 0n
n→∞
λ > .
Если для некоторого n∈ в алгоритме 1 имеем n ny x= , то nx S∈ . Действительно, тогда
( )
n
C
n x n ny P Ax= −λ .
Из неравенства (5) следует
( ( ) ( ), )
( , ) ( , ) 0n n n
n n n n
n
x x y x
Ax y x Ax y x
∇ϕ −∇ϕ −
− + = −
λ
y C∀ ∈ ,
то есть nx S∈ .
Предположим, что для всех n∈ условие остановки на шаге 2 не выполняется и пере-
йдем к обоснованию сходимости алгоритма 1.
Сходимость алгоритма. Докажем важную оценку, связывающую дивергенцию Брэгмана
между порожденными алгоритмом 1 точками и произвольным элементом множества реше-
ний S .
Лемма 1. Для последовательностей ( )nx , ( )ny , порожденных алгоритмом 1, имеет мес-
то неравенство
1 1( , ) ( , ) 1 ( , ) 1 ( , )n n
n n n n n nV z x V z x V y x V x y+ +
μ μ⎛ ⎞ ⎛ ⎞− − − −⎜ ⎟ ⎜ ⎟σ σ⎝ ⎠ ⎝ ⎠
,
где z S∈ , 1( )n n n+μ = τ λ λ .
Доказательство. Пусть z S∈ . Запишем 3-точечное тождество (2)
1 1 1 1( , ) ( , ) ( , ) ( ( ) ( ), )n n n n n n nV z x V z x V x x x x x z+ + + += − + ∇ϕ −∇ϕ − . (6)
21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 5
Сходимость брэгмановского экстраградиентного метода
Из определения точек 1nx + и (5) следует
1 1 1( , ) ( ( ) ( ), ) 0n n n n n nAy z x x x z x+ + +λ − + ∇ϕ −∇ϕ − . (7)
Используя неравенство (7) для оценки скалярного произведения в (6), получаем
1 1 1( , ) ( , ) ( , ) ( , )n n n n n n nV z x V z x V x x Ay z x+ + +− +λ −� . (8)
Третье слагаемое в (8) представим в виде
1 1 1( , ) ( , ) ( , ) ( ( ) ( ), )n n n n n n n n n nV x x V x y V y x y x x y+ + += + + ∇ϕ −∇ϕ −� .
Получаем
1 1
1
( , ) ( , ) ( , ) ( , )
( ( ) ( ), ) ( , )
n n n n n n
n n n n n n n n n
V z x V z x V x y V y x
x Ay y x y Ay z y
+ +
+
− − +
+ ∇ϕ −λ −∇ϕ − +λ −
�
.
Из псевдомонотонности оператора A следует ( , ) 0n nAy z y− . Таким образом,
1 1
1
( , ) ( , ) ( , ) ( , )
( ( ) ( ), ).
n n n n n n
n n n n n n
V z x V z x V x y V y x
x Ay y x y
+ +
+
− − +
+ ∇ϕ −λ −∇ϕ −
�
(9)
Поскольку 1nx C+ ∈ , то
1 1
0
( ( ) ( ), ) ( ( ) ( ), )n n n n n n n n n n n nx Ay y x y x Ax y x y+ +∇ϕ −λ −∇ϕ − = ∇ϕ −λ −∇ϕ − +
1 1( , ) ( , )n n n n n n n n n nAx Ay x y Ax Ay x y+ ++λ − − λ − −� . (10)
Учитывая (10) в (9), получаем
1 1 1( , ) ( , ) ( , ) ( , ) ( , )n n n n n n n n n n nV z x V z x V x y V y x Ax Ay x y+ + +− − +λ − −� �. (11)
Теперь оценим слагаемое 1( , )n n n n nAx Ay x y+λ − − с помощью неравенства (3). Имеем
1 1*
( , )n n n n n n n n n nAx Ay x y Ax Ay x y+ +λ − − λ − −
1 1
1
2
( , ) ( , ) ( , ) ( , )n n n
n n n n n n n n
n
V y x V x y V y x V x y+ +
+
λ μ μ
τ +
σ λ σ σ
. (12)
Применив (12) в (11), получим
1 1 1( , ) ( , ) ( , ) ( , ) ( , ) ( , )n n
n n n n n n n n n nV z x V z x V x y V y x V y x V x y+ + +
μ μ
− − + + =
σ σ
� �
1( , ) 1 ( , ) 1 ( , )n n
n n n n nV z x V x y V y x+
μ μ⎛ ⎞ ⎛ ⎞= − − − −⎜ ⎟ ⎜ ⎟σ σ⎝ ⎠ ⎝ ⎠
,
что и требовалось доказать.
Сформулируем основной результат работы.
Теорема 1. Пусть множество C E⊆ — выпуклое и замкнутое, оператор :A E E∗→ —
псевдомонотонный и липшицевый с константой 0L > и S ≠ ∅ . Тогда последовательности
( )nx и ( )ny , порожденные алгоритмом 1, сходятся к некоторой точке z S∈ .
Замечание 4. В дальнейшем мы рассмотрим рандомизированную версию алгоритма 1
и проведем анализ сходимости. Это поможет продвинуться в направлении использования
метода для решения вариационных неравенств большого размера и для обучения генериру-
ющих состязательных нейронных сетей (GAN).
22 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 5
Я.И. Ведель, С.В. Денисов, В.В. Семёнов
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
1. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач. Экономика
и мат. методы. 1976. 12, № 4. С. 747—756.
2. Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control
Optim. 2000. 38. P. 431—446. doi: https://doi.org/10.1137/S0363012998338806
3. Semenov V.V. A strongly convergent splitting method for systems of operator inclusions with monotone op-
erators. J. Autom. Inform. Sci. 2014. 46, № 5. P. 45–56. doi: https://doi.org/10.1615/JAutomatInfScien.v46.
i5.40
4. Semenov V.V. Hybrid splitting methods for the system of operator inclusions with monotone operators. Cy-
bern. Syst. Anal. 2014. 50. P. 741—749. doi: https://doi.org/10.1007/s10559-014-9664-y
5. Denisov S.V., Semenov V.V., Chabak L.M. Convergence of the modified extragradient method for variational
inequalities with non-lipschitz operators. Cybern. Syst. Anal. 2015. 51. P. 757—765. doi: https://doi.org/
10.1007/s10559-015-9768-z
6. Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for variation-
al inequalities with non-Lipschitz operators. J. Autom. Inform. Sci. 2015. 47, № 7. P. 31—46. doi: https://doi.
org/10.1615/JAutomatInfScien.v47.i7.40
7. Nemirovski A. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz con-
tinuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 2004. 15.
P. 229—251. doi: https://doi.org/10.1137/S1052623403425629
8. Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related problems.
Math. Program. 2007. 109. Iss. 2–3. P. 319—344. doi: https://doi.org/10.1007/s10107-006-0034-z
9. Semenov V.V. A Version of the mirror descent method to solve variational inequalities. Cybern. Syst. Anal.
2017. 53. P. 234—243. doi: https://doi.org/10.1007/s10559-017-9923-9
10. Semenov V.V. Modified extragradient method with Bregman divergence for variational inequalities. J. Autom.
Inform. Sci. 2018. 50, Iss. 8. P. 26—37. doi: https://doi.org/10.1615/JAutomatInfScien.v50.i8.30
11. Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of equilibrium pro-
gramming. Optimization and its applications in control and data sciences: Goldengorin, B. (ed.). Cham: Sprin-
ger, 2016. P. 315—325 (Springer Optimization and Its Applications; Vol. 115). doi: https://doi.org/10.1007/
978-3-319-42056-1_10
12. Khobotov E.N. Modification of the extra-gradient method for solving variational inequalities and certain
optimization problems. USSR Comput. Math. Math. Phys. 1987. 27, Iss. 5. P. 120—127. doi: https://doi.
org/10.1016/0041-5553(87)90058-9
13. Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics,
2017. P. 494. doi: https://doi.org/10.1137/1.9781611974997
Поступило в редакцию 04.03.2019
REFERENCES
1. Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Ekonomi-
ka i Matematicheskie Metody, 12, No. 4, pp. 747-756 (in Russian).
2. Tseng, P. (2000). A modified forward-backward splitting method for maximal monotone mappings. SIAM J.
Control Optim., 38, pp. 431-446. doi: https://doi.org/10.1137/S0363012998338806
3. Semenov, V. V. (2014). A strongly convergent splitting method for systems of operator inclusions with mono-
tone operators. J. Autom. Inform. Sci., 46, No. 5, pp. 45-56. doi: https://doi.org/10.1615/JAutomatInfScien.
v46.i5.40
4. Semenov, V. V. (2014). Hybrid splitting methods for the system of operator inclusions with monotone opera-
tors. Cybern. Syst. Anal., 50, pp. 741-749. doi: https://doi.org/10.1007/s10559-014-9664-y
5. Denisov, S. V., Semenov, V. V. & Chabak, L. M. (2015). Convergence of the modified extragradient method for
variational inequalities with non-Lipschitz operators. Cybern. Syst. Anal., 51, pp. 757-765. doi: https://doi.
org/10.1007/s10559-015-9768-z
6. Verlan, D. A., Semenov, V. V. & Chabak, L. M. (2015). A strongly convergent modified extragradient method
for variational inequalities with non-Lipschitz operators. J. Autom. Inform. Sci., 47, No. 7, pp. 31-46. doi:
https://doi.org/10.1615/JAutomatInfScien.v47.i7.40
23ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 5
Сходимость брэгмановского экстраградиентного метода
7. Nemirovski, A. (2004). Prox-method with rate of convergence O(1/t) for variational inequalities with Lip-
schitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim.,
15, pp. 229-251. doi: https://doi.org/10.1137/S1052623403425629
8. Nesterov, Yu. (2007). Dual extrapolation and its applications to solving variational inequalities and related
problems. Math. Program., 109, Iss. 2-3, pp. 319–344. doi: https://doi.org/10.1007/s10107-006-0034-z
9. Semenov, V. V. (2017). A version of the mirror descent method to solve variational inequalities. Cybern. Syst.
Anal., 53, pp. 234-243. doi: https://doi.org/10.1007/s10559-017-9923-9
10. Semenov, V. V. (2018). Modified extragradient method with bregman divergence for variational inequalities.
J. Autom. Inform. Sci., 50, Iss. 8, pp. 26-37. doi: https://doi.org/10.1615/JAutomatInfScien.v50.i8.30
11. Lyashko, S. I. & Semenov, V. V. (2016). A new two-step proximal algorithm of solving the problem of equilib-
rium programming. In Goldengorin, B. (Ed.). Optimization and its applications in control and data sciences
(pp. 315-325). Optimization and Its Applications, Vol. 115. Cham: Springer. doi: https://doi.org/10.1007/978-
3-319-42056-1_10
12. Khobotov, E. N. (1987). Modification of the extra-gradient method for solving variational inequalities and
certain optimization problems. USSR Comput. Math. Math. Phys., 27, Iss. 5, pp. 120-127. doi: https://doi.
org/10.1016/0041-5553(87)90058-9
13. Beck, A. (2017). First-order methods in optimization. Philadelphia: Society for Industrial and Applied Math-
ematics. doi: https://doi.org/10.1137/1.9781611974997
Received 04.03.2019
Я.І. Ведель, С.В. Денисов, В.В. Семенов
Київський національний університет ім. Тараса Шевченка
E-mail: yana.vedel@gmail.com, sireukr@gmail.com, semenov.volodya@gmail.com
ЗБІЖНІСТЬ БРЕГМАНІВСЬКОГО ЕКСТРАГРАДІЄНТНОГО МЕТОДУ
Доведено збіжність нового варіанта екстраградієнтного методу для наближеного розв’язання варіаційних
нерівностей з псевдомонотонними та ліпшицевими операторами. У методі використовується дивергенція
Брегмана замість евклідової відстані та нове регулювання величини кроку, що не вимагає знання констан-
ти Ліпшиця оператора. На відміну від правил вибору величини кроку, що застосовувалися раніше, в про-
понованому методі не проводиться додаткових обчислень значень оператора та прокс-відображення.
Ключові слова: варіаційна нерівність, екстраградієнтний метод, дивергенція Брегмана, збіжність.
Ya.I. Vedel, S.V. Denisov, V.V. Semenov
Taras Shevchenko National University of Kiev
E-mail: yana.vedel@gmail.com, sireukr@gmail.com, semenov.volodya@gmail.com
CONVERGENCE OF THE BREGMAN EXTRAGRADIENT METHOD
The convergence of a new extragradient-type method for the approximate solution of variational inequalities
with pseudomonotonіс and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is
proved. The method uses the Bregman divergence instead of the Euclidean distance and the new adjustment of
the step size, which does not require knowledge of the Lipschitz constant of an operator. In contrast to the
previously used rules for choosing the step size, the proposed method does not perform additional calculations for
the operator values and prox-map.
Keywords: variational inequality, extragradient method, Bregman divergence, convergence.
|
| id | nasplib_isofts_kiev_ua-123456789-158103 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T16:53:57Z |
| publishDate | 2019 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Ведель, Я.И. Денисов, С.В. Семёнов, В.В. 2019-07-15T15:53:03Z 2019-07-15T15:53:03Z 2019 Сходимость брэгмановского экстраградиентного метода / Я.И. Ведель, С.В. Денисов, В.В. Семёнов // Доповіді Національної академії наук України. — 2019. — № 5. — С. 18-23. — Бібліогр.: 13 назв. — рос. 1025-6415 DOI: doi.org/10.15407/dopovidi2019.05.018 https://nasplib.isofts.kiev.ua/handle/123456789/158103 517.988 Доказана сходимость нового варианта экстраградиентного метода для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами. В методе используется дивергенция
 Брэгмана вместо евклидового расстояния и новая регулировка величины шага, не требующая знания константы Липшица оператора. В отличие от применявшихся ранее правил выбора величины шага в предлагаемом методе не производится дополнительных вычислений значений оператора и прокс-отображения. Доведено збіжність нового варіанта екстраградієнтного методу для наближеного розв’язання варіаційних
 нерівностей з псевдомонотонними та ліпшицевими операторами. У методі використовується дивергенція
 Брегмана замість евклідової відстані та нове регулювання величини кроку, що не вимагає знання константи Ліпшиця оператора. На відміну від правил вибору величини кроку, що застосовувалися раніше, в пропонованому методі не проводиться додаткових обчислень значень оператора та прокс-відображення. The convergence of a new extragradient-type method for the approximate solution of variational inequalities
 with pseudomonotonіс and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is
 proved. The method uses the Bregman divergence instead of the Euclidean distance and the new adjustment of
 the step size, which does not require knowledge of the Lipschitz constant of an operator. In contrast to the
 previously used rules for choosing the step size, the proposed method does not perform additional calculations for
 the operator values and prox-map. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Сходимость брэгмановского экстраградиентного метода Збіжність брегманівського екстраградієнтного методу Convergence of the Bregman extragradient method Article published earlier |
| spellingShingle | Сходимость брэгмановского экстраградиентного метода Ведель, Я.И. Денисов, С.В. Семёнов, В.В. Математика |
| title | Сходимость брэгмановского экстраградиентного метода |
| title_alt | Збіжність брегманівського екстраградієнтного методу Convergence of the Bregman extragradient method |
| title_full | Сходимость брэгмановского экстраградиентного метода |
| title_fullStr | Сходимость брэгмановского экстраградиентного метода |
| title_full_unstemmed | Сходимость брэгмановского экстраградиентного метода |
| title_short | Сходимость брэгмановского экстраградиентного метода |
| title_sort | сходимость брэгмановского экстраградиентного метода |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/158103 |
| work_keys_str_mv | AT vedelʹâi shodimostʹbrégmanovskogoékstragradientnogometoda AT denisovsv shodimostʹbrégmanovskogoékstragradientnogometoda AT semenovvv shodimostʹbrégmanovskogoékstragradientnogometoda AT vedelʹâi zbížnístʹbregmanívsʹkogoekstragradíêntnogometodu AT denisovsv zbížnístʹbregmanívsʹkogoekstragradíêntnogometodu AT semenovvv zbížnístʹbregmanívsʹkogoekstragradíêntnogometodu AT vedelʹâi convergenceofthebregmanextragradientmethod AT denisovsv convergenceofthebregmanextragradientmethod AT semenovvv convergenceofthebregmanextragradientmethod |