Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах
The paper presents new algorithms for solving variational inequalities in uniformly convex Banach spaces. The first algorithm is a modification of the forward-reflected-backward algorithm, which uses the Alber generalized projection instead of the metric one. The second alg...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/317 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479688231780352 |
|---|---|
| author | Semenov, Volodymyr Kharkov, Oleh |
| author_facet | Semenov, Volodymyr Kharkov, Oleh |
| author_institution_txt_mv | [
{
"author": "Volodymyr Semenov",
"institution": "д. ф.-м. н., професор, Київський національний університет імені Тараса Шевченка, вул. Володимирська, 64\/13, 01601, Київ"
},
{
"author": "Oleh Kharkov",
"institution": "аспірант, Київський національний університет імені Тараса Шевченка, вул. Володимирська, 64\/13, 01601, Київ"
}
] |
| author_sort | Semenov, Volodymyr |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The paper presents new algorithms for solving variational inequalities in uniformly convex Banach spaces. The first algorithm is a modification of the forward-reflected-backward algorithm, which uses the Alber generalized projection instead of the metric one. The second algorithm is an adaptive version of the first one, where the monotone step size update rule is used, which does not require knowledge of Lipschitz constants and linear search procedure. Theorems on the weak convergence of methods are proved. Also, for the first algorithm, an efficiency estimate is proved. |
| first_indexed | 2026-06-09T01:10:15Z |
| format | Article |
| fulltext |
118
doi.org/10.15407/fmmit2023.37.118
Метод операторної екстраполяції для варіаційних
нерівностей в банахових просторах
Володимир Семенов1, Олег Харьков2
1 д. ф.-м. н., професор, Київський національний університет імені Тараса Шевченка, вул. Володимирська, 64/13,
01601, Київ, e-mail: semenov.volodya@gmail.com
2 аспірант, Київський національний університет імені Тараса Шевченка, вул. Володимирська, 64/13, 01601,
Київ, e-mail: olehharek@gmail.com
У роботі наведено нові алгоритми для розв’язання варіаційних нерівностей в рівномірно
опуклих банахових просторах. Перший алгоритм – модифікація методу «forward-reflected-
backward algorithm», що використовує узагальнену проєкцію Альбера замість метричної.
Другий алгоритм є адаптивним варіантом першого, де використовується монотонне
правило поновлення величини кроку, що не вимагає знання ліпшицевих констант та
лінійного пошуку. Доведено теореми про слабку збіжність методів та для першого
алгоритму доведено оцінку ефективності.
Ключові слова: варіаційна нерівність; узагальнена проєкція Альбера;
метод операторної екстраполяції, слабка збіжність
Вступ. В даній роботі, що продовжує цикл статей [1–3], досліджено нові
ітераційні алгоритми для розв’язання варіаційних нерівностей в рівномірно
опуклих банахових просторах. Перший алгоритм – модифікація методу «forward-
reflected-backward algorithm» [4], що використовує проєкцію Альбера. Другий
алгоритм є адаптивним варіантом першого, де використовується правило
поновлення величини кроку, що не вимагає знання ліпшицевих констант та
лінійного пошуку. Для варіаційних нерівностей з монотонними, ліпшицевими
операторами, що діють в 2-рівномірно опуклому та рівномірно гладкому
банаховому просторі, доведено теореми про слабку збіжність методів. Також для
першого алгоритму доведено оцінку ефективності в термінах функції зазору.
1. Метод операторної екстраполяції
Усі необхідні поняття та факти нелінійного аналізу наведено в [3, 5, 6].
Нехай E – дійсний банаховий простір з нормою , E
– спряжений до E
простір. Багатозначний оператор : 2EJ E
, що діє за правилом
22
: ,Jx x E x x x x
,
називають нормалізованим дуальным відображенням [5]. Відомо, що [5]: якщо
простір E гладкий, то J однозначне; якщо простір E строго опуклий, то J
УДК 517.988
mailto:semenov.volodya@gmail.com
mailto:olehharek@gmail.com
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 118-122
119
ін’єктивне та строго монотонне; якщо простір E рефлексивний, то J
сюр’єктивне; якщо простір E рівномірно гладкий, то J рівномірно неперервне
на обмежених множинах з E .
Нехай E – гладкий банаховий простір. Розглянемо введений Я. Альбером
[6] функціонал
2 2
, 2 ,x y x Jy x y ,x y E .
Лема 1 ([7]). Нехай E – 2-рівномірно опуклий та гладкий банаховий
простір. Тоді для деякого 1 виконується нерівність
21,x y x y ,x y E . (1)
Для банахових просторів p , pL та
m
pW (1 2p ) маємо 1
1p
[7].
Нехай K – непорожня замкнена та опукла підмножина рефлексивного,
строго опуклого та гладкого простору E . Відомо [6], що для кожного x E
існує єдиний елемент z K такий, що , inf ,
y K
z x y x
. Цей елемент z
позначають K x , а відповідний оператор :K E K називають узагальненою
проєкцією E на K (проєкцією Альбера) [6]. Зауважимо, що якщо E
гільбертовий простір, то K співпадає з метричною проєкцією на множину K .
Розглянемо варіаційну нерівність:
знайти x C : , 0Ax y x y C , (2)
де C – непорожня підмножина 2 -рівномірно опуклого та рівномірно гладкого
банахового простору E , A – оператор, що діє з E в
*E . Множину розв’язків (2)
позначимо S .
Припустимо, що виконані такі умови: множина C E – опукла та
замкнена; оператор
*:A E E – монотонний та ліпшицевий на C (з
константою 0L ); множина S не порожня.
Однією з основних теоретичних задач є оцінка числа ітерацій алгоритму,
що необхідне для отримання наближеного розв’язку заданої якості. Якість
наближеного розв’язку x C варіаційної нерівності (2) будемо оцінювати за
допомогою невід’ємної функції зазору
gap sup ,
y C
x Ay x y
. (3)
Очевидно, що для коректності означення функції зазору (3) необхідна
обмеженість допустимої множини C .
Лема 2. Нехай оператор A – монотонний. Якщо x C – розв’язок (2), то
gap 0x . Навпаки, якщо для x C маємо gap 0x , то x – розв’язок (2).
Для розв’язання варіаційної нерівності (2) в [3] запропоновано такий
алгоритм операторної екстраполяції.
Володимир Семенов, Олег Харьков
Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах
120
Алгоритм 1. Обираємо 0 1x x E , 0n . Покладаємо 1n .
1. Обчислити
1
1n C n n n nx J Jx Ax m
, 1 1n n n nm Ax Ax .
2. Якщо 1 1n n nx x x , то СТОП, інакше : 1n n та перейти до 1.
Зауваження 1. Алгоритм 1 є модификацією «forward-reflected-backward
algorithm» [4] для задач в банахових просторах, що використовує проєкцію
Альбера замість метричної. Збіжність «forward-reflected-backward algorithm» в
гільбертовому просторі доведена в [4].
У випадку обмеженості множини C алгоритму 1 необхідно зробити
LDO
ітерацій для отримання x C з gap x , 0 , де
,sup ,a b CD a b .
Теорема 1. Нехай nx – послідовність, що породжена алгоритмом 1 з
1
2
0,n L
. Тоді для послідовності
11
1
1
N
n nn
N N
nn
x
z
має місце нерівність
1gap Nz 1
1
1
sup ,
2
N
y C
nn
y x
.
Теорема 2. Нехай nx – послідовність, що породжена алгоритмом 1 з
1
2
n
L
. Тоді для послідовності середніх 1
1 11
N
N nN n
z x
має місце оцінка
1gap Nz 1sup ,
y C
L
y x
N
.
Теорема 3. Нехай C – непорожня опукла та замкнена підмножина 2 -
рівномірно опуклого та рівномірно гладкого банахового простору E ,
*:A E E – монотонний та ліпшицевий на множині C оператор, S .
Припустимо, що відображення J секвенційно слабко неперервне та
послідовність n така, що 1
2
0 inf supn n n n L
. Тоді послідовність
nx , що породжена алгоритмом 1, слабко збігаються до деякої точки z S .
2. Адаптивний варіант
Відштовхуючись від алгоритму 1 та робіт [1, 2] у статті [3] побудовано алгоритм
з адаптивним вибором величини
n , що не вимагає знання ліпшицевих констант
та процедур типу лінійного пошуку. У даній роботі наведемо результат про
збіжність даного алгоритму.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 118-122
121
Припустимо, що відома лише константа 1 з леми 1.
Алгоритм 2. Обираємо 0 1x x E , 1
2
0,
та число
1 0 0 .
Покладаємо 1n .
1. Обчислити
1
1n C n n n nx J Jx Ax m
, 1 1n n n nm Ax Ax .
2. Якщо 1 1n n nx x x , то СТОП, інакше перейти до 3.
3. Обчислити
1
1
1 1 *
min , , якщо ,
, інакше.
n n
n n n
n n n
n
x x
Ax Ax
Ax Ax
Покласти : 1n n та перейти до 1.
В якості функції Ляпунова оберемо
1
1, 2 , ,n
n n n n n n
n
W z x m x z L x x
, z S .
Лема 3. Для nx , що породжена алгоритмом 2, виконується нерівність
1n nW W 1
1
1
1 ,n n
n n
n n
x x
.
Теорема 4. Нехай C – непорожня опукла та замкнена підмножина 2 -
рівномірно опуклого та рівномірно гладкого банахового простору E ,
*:A E E – монотонний та ліпшицевий оператор, S . Припустимо, що
відображення J секвенційно слабко неперервне. Тоді nx , що породжена
алгоритмом 2, слабко збігається до деякої точки z S .
Для операторного рівняння 0Ax алгоритм 2 дає такий процес
1 1 1
1
1
1 1 *
,
min , , якщо ,
, інакше.
n n n n n n n
n n
n n n
n n n
n
Jx Jx Ax Ax Ax
x x
Ax Ax
Ax Ax
Висновки. В роботі досліджено модифікації методу «forward-reflected-
backward algorithm», що використовують проєкцію Альбера, для
розв’язання варіаційних нерівностей в рівномірно опуклих банахових
Володимир Семенов, Олег Харьков
Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах
122
просторах. Доведено теореми про слабку збіжність методів. Вкажемо на
актуальні питання. По-перше, всі результати отримані для класу 2-рівномірно
опуклих і рівномірно гладких банахових просторів, який не містить важливих
для застосувань просторів pL і
m
pW ( 2 p ). Бажано позбавитися цього
обмеження. По-друге, для можливості ефективного застосування алгоритмів для
нелінійних задач необхідні швидкі та стійкі алгоритми обчислення проєкції
Альбера для широкого набору множин. Цікавим питанням є дослідження
поведінки алгоритмів 1 та 2 у ситуації C E . А саме, питання про
асимптотичну поведінку
*nAx . Зауважимо, що теореми 1 та 4 можна отримати
для задач з псевдомонотонними операторами.
Література
[1] Vedel Y., Semenov V. Adaptive Extraproximal Algorithm for the Equilibrium Problem in
Hadamard Spaces. In: Olenev N., Evtushenko Y., Khachay M., Malkova V. (eds .)
Optimization and Applications. OPTIMA 2020. Lecture Notes in Computer Science, vol
12422. Springer, Cham, 2020. P. 287-300.
[2] Semenov V. V., Denisov S. V., Kravets A. V. Adaptive Two-Stage Bregman Method for Variational
Inequalities. Cybernetics and Systems Analysis. 2021. Vol. 57. Issue 6. P. 959-967.
[3] Vedel Y., Semenov V., Denisov S. A Novel Algorithm with Self-adaptive Technique
for Solving Variational Inequalities in Banach Spaces. In: Olenev N. N., Evtushenko Y. G.,
Jaćimović M., Khachay M., Malkova V. (eds.) Advances in Optimization and Applications.
OPTIMA 2021. Communications in Computer and Information Science, vol 1514. Springer,
Cham, 2021. P. 50-64.
[4] Malitsky Y., Tam M. K. A Forward-Backward Splitting Method for Monotone Inclusions Without
Cocoercivity. SIAM Journal on Optimization. 2020. Vol. 30. P. 1451-1472.
[5] Alber Y., Ryazantseva I. Nonlinear Ill Posed Problems of Monotone Type. Dordrecht: Springer,
2006. 410 p.
[6] Alber Y. I. Metric and generalized projection operators in Banach spaces: properties and
applications. In: Theory and Applications of Nonlinear Operators of Accretive and Monotone
Type, vol. 178. New York: Dekker, 1996. P. 15-50.
[7] Xu H. K. Inequalities in Banach spaces with applications. Nonlinear Anal. 1991. Vol. 16. Iss. 12.
P. 1127-1138.
Operator extrapolation method for variational inequalities in
Banach spaces
Volodymyr Semenov, Oleh Kharkov
The paper presents new algorithms for solving variational inequalities in uniformly convex
Banach spaces. The first algorithm is a modification of the forward-reflected-backward algorithm,
which uses the Alber generalized projection instead of the metric one. The second algorithm is an
adaptive version of the first one, where the monotone step size update rule is used, which does not
require knowledge of Lipschitz constants and linear search procedure. Theorems on the weak
convergence of methods are proved. Also, for the first algorithm, an efficiency estimate is proved.
Отримано 14.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-317 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:15Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/14/10898928bd4bbfe11f93f6be33c76014.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3172025-02-21T17:31:10Z Operator extrapolation method for variational inequalities in Banach spaces Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах Semenov, Volodymyr Kharkov, Oleh варіаційна нерівність; узагальнена проєкція Альбера; метод операторної екстраполяції, слабка збіжність The paper presents new algorithms for solving variational inequalities in uniformly convex Banach spaces. The first algorithm is a modification of the forward-reflected-backward algorithm, which uses the Alber generalized projection instead of the metric one. The second algorithm is an adaptive version of the first one, where the monotone step size update rule is used, which does not require knowledge of Lipschitz constants and linear search procedure. Theorems on the weak convergence of methods are proved. Also, for the first algorithm, an efficiency estimate is proved. У роботі наведено нові алгоритми для розв’язання варіаційних нерівностей в рівномірно опуклих банахових просторах. Перший алгоритм – модифікація методу «forward-reflected-backward algorithm», що використовує узагальнену проєкцію Альбера замість метричної. Другий алгоритм є адаптивним варіантом першого, де використовується монотонне правило поновлення величини кроку, що не вимагає знання ліпшицевих констант та лінійного пошуку. Доведено теореми про слабку збіжність методів та для першого алгоритму доведено оцінку ефективності. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-28 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/317 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 118-122 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 118-122 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/317/285 Авторське право (c) 2023 Володимир Семенов, Олег Харьков (Автор) |
| spellingShingle | варіаційна нерівність; узагальнена проєкція Альбера; метод операторної екстраполяції слабка збіжність Semenov, Volodymyr Kharkov, Oleh Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title | Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title_alt | Operator extrapolation method for variational inequalities in Banach spaces |
| title_full | Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title_fullStr | Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title_full_unstemmed | Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title_short | Метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| title_sort | метод операторної екстраполяції для варіаційних нерівностей в банахових просторах |
| topic | варіаційна нерівність; узагальнена проєкція Альбера; метод операторної екстраполяції слабка збіжність |
| topic_facet | варіаційна нерівність; узагальнена проєкція Альбера; метод операторної екстраполяції слабка збіжність |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/317 |
| work_keys_str_mv | AT semenovvolodymyr operatorextrapolationmethodforvariationalinequalitiesinbanachspaces AT kharkovoleh operatorextrapolationmethodforvariationalinequalitiesinbanachspaces AT semenovvolodymyr metodoperatornoíekstrapolâcíídlâvaríacíjnihnerívnostejvbanahovihprostorah AT kharkovoleh metodoperatornoíekstrapolâcíídlâvaríacíjnihnerívnostejvbanahovihprostorah |