Вариант экстраградиентного алгоритма для монотонных вариационных неравенств
Предлагается новый итерационный алгоритм решения вариационного неравенства с монотонным и липшицевым оператором, действующим в гильбертовом пространстве. Алгоритм основан на двух известных методах: алгоритме Попова и так называемом субградиентном экстраградиентном алгоритме. Привлекательной чертой а...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/115781 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Вариант экстраградиентного алгоритма для монотонных вариационных неравенств / Ю.В. Малицкий, В.В. Семенов // Кибернетика и системный анализ. — 2014. — Т. 50, № 2. — С. 125-131. — Бібліогр.: 35 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-115781 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1157812017-04-13T03:02:28Z Вариант экстраградиентного алгоритма для монотонных вариационных неравенств Малицкий, Ю.В. Семенов, В.В. Системный анализ Предлагается новый итерационный алгоритм решения вариационного неравенства с монотонным и липшицевым оператором, действующим в гильбертовом пространстве. Алгоритм основан на двух известных методах: алгоритме Попова и так называемом субградиентном экстраградиентном алгоритме. Привлекательной чертой алгоритма является вычисление только одного значения оператора неравенства и одной проекции на допустимое множество при выполнении итерационного шага. Доказана теорема о слабой сходимости для последовательностей, порожденных предложенным алгоритмом. Запропоновано новий ітераційний алгоритм розв’язання варіаційних нерівностей із монотонним та ліпшицевим оператором, що діє в гільбертовому просторі. Алгоритм ґрунтується на двох відомих методах: алгоритмі Попова і так званому субґрадієнтному екстраґрадієнтному алгоритмі. Привабливою рисою алгоритму є обчислення лише одного значення оператора нерівності і однієї проекції на допустиму множину при виконанні ітераційного кроку. Доведено теорему про слабку збіжність для послідовностей, що породжуються запропонованим алгоритмом. We propose a new iterative algorithm to solve the variational inequality problem with monotone and Lipschitz continuous mapping in Hilbert space. It is based on two well-known methods: Popov’s algorithm and so-called subgradient extragradient algorithm. An advantage of the algorithm is the computation of only one value of the inequality mapping and one projection onto the feasible set at one iteration. We prove the weak convergence of the sequences generated by the proposed algorithm. 2014 Article Вариант экстраградиентного алгоритма для монотонных вариационных неравенств / Ю.В. Малицкий, В.В. Семенов // Кибернетика и системный анализ. — 2014. — Т. 50, № 2. — С. 125-131. — Бібліогр.: 35 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/115781 517.988 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Малицкий, Ю.В. Семенов, В.В. Вариант экстраградиентного алгоритма для монотонных вариационных неравенств Кибернетика и системный анализ |
| description |
Предлагается новый итерационный алгоритм решения вариационного неравенства с монотонным и липшицевым оператором, действующим в гильбертовом пространстве. Алгоритм основан на двух известных методах: алгоритме Попова и так называемом субградиентном экстраградиентном алгоритме. Привлекательной чертой алгоритма является вычисление только одного значения оператора неравенства и одной проекции на допустимое множество при выполнении итерационного шага. Доказана теорема о слабой сходимости для последовательностей, порожденных предложенным алгоритмом. |
| format |
Article |
| author |
Малицкий, Ю.В. Семенов, В.В. |
| author_facet |
Малицкий, Ю.В. Семенов, В.В. |
| author_sort |
Малицкий, Ю.В. |
| title |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| title_short |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| title_full |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| title_fullStr |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| title_full_unstemmed |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| title_sort |
вариант экстраградиентного алгоритма для монотонных вариационных неравенств |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/115781 |
| citation_txt |
Вариант экстраградиентного алгоритма для монотонных вариационных неравенств / Ю.В. Малицкий, В.В. Семенов // Кибернетика и системный анализ. — 2014. — Т. 50, № 2. — С. 125-131. — Бібліогр.: 35 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT malickijûv variantékstragradientnogoalgoritmadlâmonotonnyhvariacionnyhneravenstv AT semenovvv variantékstragradientnogoalgoritmadlâmonotonnyhvariacionnyhneravenstv |
| first_indexed |
2025-07-08T09:21:36Z |
| last_indexed |
2025-07-08T09:21:36Z |
| _version_ |
1837070021949390848 |
| fulltext |
ÓÄÊ 517.988
Þ.Â. ÌÀËÈÖÊÈÉ, Â.Â. ÑÅÌÅÍÎÂ
ÂÀÐÈÀÍÒ ÝÊÑÒÐÀÃÐÀÄÈÅÍÒÍÎÃÎ ÀËÃÎÐÈÒÌÀ
ÄËß ÌÎÍÎÒÎÍÍÛÕ ÂÀÐÈÀÖÈÎÍÍÛÕ ÍÅÐÀÂÅÍÑÒÂ1
Àííîòàöèÿ. Ïðåäëàãàåòñÿ íîâûé èòåðàöèîííûé àëãîðèòì ðåøåíèÿ âàðèàöèîííîãî íåðà-
âåíñòâà ñ ìîíîòîííûì è ëèïøèöåâûì îïåðàòîðîì, äåéñòâóþùèì â ãèëüáåðòîâîì ïðîñò-
ðàíñòâå. Àëãîðèòì îñíîâàí íà äâóõ èçâåñòíûõ ìåòîäàõ: àëãîðèòìå Ïîïîâà è òàê íàçûâàå-
ìîì ñóáãðàäèåíòíîì ýêñòðàãðàäèåíòíîì àëãîðèòìå. Ïðèâëåêàòåëüíîé ÷åðòîé àëãîðèòìà
ÿâëÿåòñÿ âû÷èñëåíèå òîëüêî îäíîãî çíà÷åíèÿ îïåðàòîðà íåðàâåíñòâà è îäíîé ïðîåêöèè íà
äîïóñòèìîå ìíîæåñòâî ïðè âûïîëíåíèè èòåðàöèîííîãî øàãà. Äîêàçàíà òåîðåìà î ñëàáîé
ñõîäèìîñòè äëÿ ïîñëåäîâàòåëüíîñòåé, ïîðîæäåííûõ ïðåäëîæåííûì àëãîðèòìîì.
Êëþ÷åâûå ñëîâà: âàðèàöèîííîå íåðàâåíñòâî, ìîíîòîííûé îïåðàòîð, ýêñòðàãðàäèåíòíûé
ìåòîä, ñõîäèìîñòü.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü C — íåïóñòîå ïîäìíîæåñòâî äåéñòâèòåëüíîãî ãèëüáåðòîâà ïðîñòðàíñòâà
H , A — îïåðàòîð, äåéñòâóþùèé â H . Ðàññìîòðèì âàðèàöèîííîå íåðàâåíñòâî:
íàéòè x C Ax y x� � �: ( , ) 0 � �y C . (1)
Ìíîæåñòâî ðåøåíèé âàðèàöèîííîãî íåðàâåíñòâà (1) îáîçíà÷èì VI A C( , ).
Áóäåì ïðåäïîëàãàòü âûïîëíåííûìè ñëåäóþùèå óñëîâèÿ:
� ìíîæåñòâî C H� âûïóêëîå è çàìêíóòîå;
� îïåðàòîð A H H: � ìîíîòîííûé è ëèïøèöåâûé ñ êîíñòàíòîé L 0;
� VI A C( , )
�.
Ìíîãèå çàäà÷è èññëåäîâàíèÿ îïåðàöèé (ïîèñê ñåäëîâûõ òî÷åê, ïîèñê ðàâíî-
âåñèÿ Íýøà â íåêîîïåðàòèâíûõ èãðàõ, ìèíèìèçàöèÿ) è ìàòåìàòè÷åñêîé ôèçèêè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2 125
1
Íàñòîÿùàÿ ðàáîòà ôèíàíñèðîâàëàñü Âåðõîâíîé Ðàäîé Óêðàèíû (èìåííàÿ ñòèïåíäèÿ Âåðõîâíîé
Ðàäû Óêðàèíû äëÿ ìîëîäûõ ó÷åíûõ, 2013) è ÃÔÔÈ Óêðàèíû (ïðîåêò GP/F49/061).
© Þ.Â. Ìàëèöêèé, Â.Â. Ñåìåíîâ, 2014
ìîãóò áûòü çàïèñàíû â ôîðìå âàðèàöèîííûõ íåðàâåíñòâ [1–6], äëÿ ðåøåíèÿ êî-
òîðûõ ê íàñòîÿùåìó âðåìåíè ïðåäëîæåíî áîëüøîå êîëè÷åñòâî ìåòîäîâ [7–23],
â ÷àñòíîñòè ãðàäèåíòíîãî òèïà. Èçâåñòíî, ÷òî â ñëó÷àå íåîïòèìèçàöèîííûõ ïî-
ñòàíîâîê äëÿ ñõîäèìîñòè íàèáîëåå ïðîñòûõ ãðàäèåíòíûõ ìåòîäîâ íåîáõîäèìî
âûïîëíåíèå óñèëåííûõ óñëîâèé ìîíîòîííîñòè [7]. Äëÿ ïðåîäîëåíèÿ ýòîé òðóä-
íîñòè ñóùåñòâóåò íåñêîëüêî ïîäõîäîâ. Îäèí èç íèõ — ðåãóëÿðèçàöèÿ èñõîäíîé
çàäà÷è ñ öåëüþ ïðèäàòü åé òðåáóåìîå ñâîéñòâî [8, 21]. Ñõîäèìîñòü áåç ìîäèôè-
êàöèè çàäà÷è îáåñïå÷èâàåòñÿ â èòåðàöèîííûõ ìåòîäàõ ýêñòðàãðàäèåíòíîãî òèïà,
âïåðâûå ïðåäëîæåííûõ À.Ñ. Àíòèïèíûì [24] è Ã.Ì. Êîðïåëåâè÷ [25].
Äëÿ âàðèàöèîííîãî íåðàâåíñòâà (1) ýêñòðàãðàäèåíòíûé àëãîðèòì Êîðïåëå-
âè÷ èìååò âèä
x C
y P x Ax
x P x Ay
n C n n
n C n n
0
1
�
� �
� �
�
�
�
�
�
,
( ),
( ),
�
�
ãäå � �( , / )0 1 L , PC — îïåðàòîð ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ íà ìíîæåñòâî C.
Èçâåñòíî, ÷òî ïîñëåäîâàòåëüíîñòè ( )xn è ( )yn ñëàáî ñõîäÿòñÿ ê íåêîòîðîé
òî÷êå z VI A C� ( , ) . Îáîáùåíèþ è èññëåäîâàíèþ ýòîãî àëãîðèòìà ïîñâÿùåíî
áîëüøîå êîëè÷åñòâî ïóáëèêàöèé [26–30 è äð.].
Ê íåäîñòàòêàì àëãîðèòìà Êîðïåëåâè÷ ìîæíî îòíåñòè âû÷èñëåíèå çíà÷åíèé
îïåðàòîðà A â äâóõ ðàçíûõ òî÷êàõ (âûõîäèò íà ïåðâûé ïëàí â ìîäåëÿõ îïòèìàëü-
íîãî óïðàâëåíèÿ, îñîáåííî ñèñòåìàìè ñ ðàñïðåäåëåííûìè ïàðàìåòðàìè [6]) è íå-
îáõîäèìîñòü äâóõ ïðîåêòèðîâàíèé íà äîïóñòèìîå ìíîæåñòâî C (ðåñóðñîåìêèõ
â ñëó÷àå ìíîæåñòâà C ñëîæíîé ñòðóêòóðû) äëÿ ïåðåõîäà ê ñëåäóþùåé èòåðàöèè.
Îò ïåðâîãî íåäîñòàòêà ñâîáîäåí ýêñòðàãðàäèåíòíûé àëãîðèòì Ïîïîâà [31],
ïðåäëîæåííûé êàê ìîäèôèêàöèÿ àëãîðèòìà Ýððîó–Ãóðâèöà ïîèñêà ñåäëîâûõ òî-
÷åê âûïóêëî-âîãíóòûõ ôóíêöèé. Äëÿ âàðèàöèîííîãî íåðàâåíñòâà (1) àëãîðèòì
Ïîïîâà ïðèìåò âèä
x y C
x P x Ay
y P x Ay
n C n n
n C n n
0 0
1
1 1
, ,
( ),
( ),
�
� �
� �
�
�
�
�
�
� �
�
�
ãäå � �( , / )0 1 3L .  [31] äëÿ ñëó÷àÿ H d� � äîêàçàíà ñõîäèìîñòü ïîðîæäåííûõ
ýòèì ìåòîäîì ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn .
Äëÿ âàðèàöèîííûõ íåðàâåíñòâ [32] è çàäà÷ ðàâíîâåñíîãî ïðîãðàììèðîâà-
íèÿ [33] áûëè ïðåäëîæåíû ìîäèôèêàöèè àëãîðèòìà Êîðïåëåâè÷ ñ îäíèì ìåòðè-
÷åñêèì ïðîåêòèðîâàíèåì íà äîïóñòèìîå ìíîæåñòâî.  ýòèõ òàê íàçûâàåìûõ ñóá-
ãðàäèåíòíûõ ýêñòðàãðàäèåíòíûõ àëãîðèòìàõ ïåðâûé ýòàï èòåðàöèè ñîâïàäàåò
ñ ïåðâûì ýòàïîì èòåðàöèè â àëãîðèòìå Êîðïåëåâè÷, à äàëåå äëÿ ïîëó÷åíèÿ xn�1
âìåñòî ïðîåêòèðîâàíèÿ òî÷êè x Ayn n� � íà äîïóñòèìîå ìíîæåñòâî C òî÷êó
x Ayn n� � ïðîåêòèðóþò íà íåêîòîðîå îïîðíîå äëÿ C ïîëóïðîñòðàíñòâî. Äëÿ âàðè-
àöèîííîãî íåðàâåíñòâà (1) ñóáãðàäèåíòíûé ýêñòðàãðàäèåíòíûé àëãîðèòì èìååò
âèä
x H
y P x Ax
H z H x Ax y z y
x
n C n n
n n n n n
0
0
�
� �
� � � � � �
,
( ),
: ( , ) ,
�
�{ }
n H n nP x Ay
n� � �
�
�
�
�
�
� 1 ( ),�
ãäå � �( , / )0 1 L . Â ðàáîòàõ [32, 33] äîêàçàíà ñëàáàÿ ñõîäèìîñòü ïîðîæäåííûõ ýòèì
àëãîðèòìîì ïîñëåäîâàòåëüíîñòåé ( )xn è ( )yn ê íåêîòîðîé òî÷êå z VI A C� ( , ) .
 äàííîé ðàáîòå ïðåäëàãàåòñÿ íîâûé àëãîðèòì ðåøåíèÿ âàðèàöèîííûõ íåðà-
âåíñòâ (1) ñ ìîíîòîííûì è ëèïøèöåâûì îïåðàòîðîì, ñîâìåùàþùèé â ñåáå ïîëî-
æèòåëüíûå ÷åðòû ýêñòðàãðàäèåíòíîãî àëãîðèòìà Ïîïîâà è ñóáãðàäèåíòíîãî ýêñòðà-
ãðàäèåíòíîãî àëãîðèòìà. Äîêàçûâàåòñÿ òåîðåìà î ñëàáîé ñõîäèìîñòè àëãîðèòìà.
126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2
ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÓÒÂÅÐÆÄÅÍÈß
Ïóñòü H — äåéñòâèòåëüíîå ãèëüáåðòîâî ïðîñòðàíñòâî ñî ñêàëÿðíûì ïðîèçâåäå-
íèåì ( , )� � è ïîðîæäåííîé íîðìîé | | ||� , C H� — íåïóñòîå âûïóêëîå è çàìêíóòîå
ìíîæåñòâî. Ïóñòü PC — îïåðàòîð ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ íà ìíîæåñòâî C,
ò.å. P xC — åäèíñòâåííûé ýëåìåíò ìíîæåñòâà C ñî ñâîéñòâîì | | | |P x x
C
� �
� �
�
min | | | |
z C
z x . Ïîëåçíû ñëåäóþùèå õàðàêòåðèçàöèè ýëåìåíòà P xC [2, 34]:
y P x y CC� � � , ( , )y x z y� � � 0 � �z C, (2)
y P x y CC� � � , | | || || | | | | ||y z x z y x� � � � �2 2 2 � �z C. (3)
Èç íåðàâåíñòâà (2) ñëåäóåò, ÷òî x VI A C� ( , ) òîãäà è òîëüêî òîãäà, êîãäà
x P x AxC� �( )� , ãäå � 0 [2, 34].
Åñëè îïåðàòîð A H H: � ìîíîòîííûé è íåïðåðûâíûé, à ìíîæåñòâî C H� âû-
ïóêëîå è çàìêíóòîå, òî x VI A C� ( , ) òîãäà è òîëüêî òîãäà, êîãäà x C� è ( , )Ay y x� � 0
äëÿ âñåõ y C� [1, 2, 34].  ÷àñòíîñòè, ìíîæåñòâîVI A C( , ) âûïóêëîå è çàìêíóòîå.
Ïðè äîêàçàòåëüñòâå ñõîäèìîñòè ïîñëåäîâàòåëüíîñòåé ýëåìåíòîâ ãèëüáåðòî-
âà ïðîñòðàíñòâà èñïîëüçóåì èçâåñòíóþ ëåììó Îïÿëà.
Ëåììà 1 [35]. Ïóñòü ïîñëåäîâàòåëüíîñòü ( )xn ýëåìåíòîâ ãèëüáåðòîâà ïðîñò-
ðàíñòâà H ñëàáî ñõîäèòñÿ ê ýëåìåíòó x H� . Òîãäà äëÿ âñåõ y H x� \ { } èìååì
lim || | | lim | | ||
n
n
n
nx x x y
�� ��
� � � .
ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ
Äëÿ ðåøåíèÿ çàäà÷è (1) ïðåäëàãàåì ñëåäóþùèé àëãîðèòì.
Àëãîðèòì 1
1. Çàäàåì x y C0 0, � è � 0 .
2. Âû÷èñëÿåì
x P x Ay
y P x Ay
C
C
1 0 0
1 1 0
� �
� �
�
�
( ),
( ).
�
�
3. Èìåÿ xn , yn è yn�1, ñòðîèì ïîëóïðîñòðàíñòâî
H z H x Ay y z yn n n n n� � � � � ��{ }: ( , )� 1 0
è âû÷èñëÿåì x P x Ay
y P x Ay
n H n n
n C n n
n�
� �
� �
� �
�
�
1
1 1
( ),
( ).
�
�
4. Åñëè x xn n� �1 è y y yn n n� �� �1 1, òî çàêàí÷èâàåì âû÷èñëåíèå, èíà÷å ïî-
ëàãàåì n n: � �1 è ïåðåõîäèì íà øàã 3.
Ïðåæäå âñåãî îòìåòèì, ÷òî C H n� . Äåéñòâèòåëüíî, åñëè ïðåäïîëîæèòü ñó-
ùåñòâîâàíèå ýëåìåíòà z C H n� \ , òî íåðàâåíñòâî ( , )x Ay y z yn n n n� � � �� 1 0 áó-
äåò ïðîòèâîðå÷èòü ôàêòó y P x Ayn C n n� � �( )� 1 .
Ïîêàæåì, ÷òî îñòàíîâêà àëãîðèòìà 1 ïðèâîäèò ê ðåøåíèþ âàðèàöèîííîãî
íåðàâåíñòâà (1).
Ëåììà 2. Åñëè x xn n� �1 è y y yn n n� �� �1 1 â àëãîðèòìå 1, òî y VI A Cn � ( , ).
Äîêàçàòåëüñòâî. Åñëè â àëãîðèòìå 1 èìååò ìåñòî x xn n� �1 , òî èç (2) ñëåäóåò
( , )Ay x xn n� � 0 � �x H n . (4)
Ó÷èòûâàÿ x Hn n� �1 è y yn n� �1, ïîëó÷àåì ( , )x Ay y x yn n n n n� � � �� 0 , îòêóäà
äåëàåì âûâîä, ÷òî ( , )Ay x yn n n� � 0. Äàëåå ïðåäñòàâèì (4) â âèäå ( , )Ay x yn n� �
� � �( , )Ay x yn n n 0 � �x H n . Ñëåäîâàòåëüíî, ( , ) ( , )Ay x y Ay x yn n n n n� � � � 0
� �x H n . Ïîñêîëüêó y C Hn n� � , òî y VI A Cn � ( , ).
Ïåðåéäåì ê äîêàçàòåëüñòâó ñëàáîé ñõîäèìîñòè àëãîðèòìà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2 127
ÎÑÍÎÂÍÎÉ ÐÅÇÓËÜÒÀÒ
Ñíà÷àëà äîêàæåì âàæíîå íåðàâåíñòâî, ñâÿçûâàþùåå ðàññòîÿíèÿ îò ïîðîæäåí-
íûõ àëãîðèòìîì òî÷åê äî ìíîæåñòâà VI A C( , ).
Ëåììà 3. Ïóñòü ïîñëåäîâàòåëüíîñòè ( )xn è ( )yn ïîðîæäåíû àëãîðèòìîì 1,
z VI A C� ( , ). Òîãäà ñïðàâåäëèâî íåðàâåíñòâî
|| || || || ( ) || ||x z x z L x yn n n n� �� � � � � � �1
2 2
1
21 2�
� � � � � �( ) | | | | | | ||1 2
1
2
� �L x y L x yn n n n . (5)
Äîêàçàòåëüñòâî. Ïîñêîëüêó z VI A C H n� �( , ) , òî èç x P x Ayn H n nn� � �1 ( )�
è (3) ñëåäóåò
| | | | | | | | | | | |x z x Ay z x Ay xn n n n n n� �� � � � � � � �1
2 2
1
2
� �
� � � � � �� �| | | | | | | | ( , )x z x x Ay x zn n n n n
2
1
2
12� . (6)
Èç ìîíîòîííîñòè A è âêëþ÷åíèÿ z VI A C� ( , ) âûòåêàåò ( , )Ay y zn n � � 0. Äîáà-
âèâ íåîòðèöàòåëüíîå ñëàãàåìîå 2�( , )Ay y zn n � ê ïðàâîé ÷àñòè íåðàâåíñòâà (6),
ïîëó÷èì
|| || || || || || ( , )x z x z x x Ay x yn n n n n n n� � �� � � � � � �1
2 2
1
2
12� �
� � � � � � � � �� �|| || || || || || ( ,x z x y x y x y y xn n n n n n n n n
2 2
1
2
12 ) �
� � � � � � � �� �2 1
2 2
1
2
�( , ) || || || || || ||Ay x y x z x y x yn n n n n n n n �
� � � � � � �� � � �2 21 1 1 1� �( , ) ( , )Ay Ay x y x Ay y x yn n n n n n n n n . (7)
Èç âêëþ÷åíèÿ x Hn n� �1 ñëåäóåò íåðàâåíñòâî ( , )x Ay y x yn n n n n� � � �� �� 1 1 0.
Ñëàãàåìîå 2 1 1�( , )Ay Ay x yn n n n� �� � â (7) îöåíèì òàê:
2 21 1 1 1� �( , ) || || || ||Ay Ay x y L y y x yn n n n n n n n� � � �� � � � � �
� � � � � �� �2 1 1�L y x x y x yn n n n n n( || || || || ) || ||
� � � � � �� ��L y x x y x yn n n n n n(|| || || || || || )1
2
1
2 22 .
Ñ ó÷åòîì ïðåäûäóùèõ âûêëàäîê ïðèõîäèì ê íåðàâåíñòâó (5).
Côîðìóëèðóåì îñíîâíîé ðåçóëüòàò ðàáîòû.
Òåîðåìà 1. Ïóñòü ìíîæåñòâî C H� âûïóêëîå è çàìêíóòîå, îïåðàòîð
A H H: � ìîíîòîííûé è ëèïøèöåâûé ñ êîíñòàíòîé L 0 , VI A C( , )
�
è � �
�
�
�
�
�
�0
1
3
,
L
. Òîãäà ïîñëåäîâàòåëüíîñòè ( )xn è ( )yn , ïîðîæäåííûå àëãîðèò-
ìîì 1, ñëàáî ñõîäÿòñÿ ê íåêîòîðîé òî÷êå z VI A C� ( , ) .
Äîêàçàòåëüñòâî. Ñíà÷àëà ïîêàæåì îãðàíè÷åííîñòü ïîñëåäîâàòåëüíîñòè ( )xn .
Çàôèêñèðóåì íîìåð N �� è ðàññìîòðèì íåðàâåíñòâà (5) äëÿ âñåõ íîìåðîâ N ,
N �1, …, M , ãäå M N . Ñëîæèâ èõ, ïîëó÷èì
|| || || || ( ) || ||x z x z L x yM N n n
n N
M
� �
�
� � � � � � ��1
2 2
1
21 3�
� � � � �
�
��( ) || || || ||1 2
1
2
� �L x y L x yn n
n N
M
N N . (8)
Îòñþäà ñëåäóåò îãðàíè÷åííîñòü ïîñëåäîâàòåëüíîñòè ( )xn .
Èç íåðàâåíñòâà (8) ïîëó÷àåì ñõîäèìîñòü ðÿäîâ || ||x yn n
n
� �� 1
2 è
|| ||x yn n
n
�� 2 . Òàêèì îáðàçîì,
lim || || lim | | | |
n
n n
n
n nx y x y
��
�
��
� � � �1 0 . (9)
128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2
Ðàññìîòðèì ïîäïîñëåäîâàòåëüíîñòü ( )xnk
, ñëàáî ñõîäÿùóþñÿ ê íåêîòîðîé
òî÷êå z H� . Òîãäà y znk
� ñëàáî è z C� . Ïîêàæåì, ÷òî z VI A C� ( , ). Èìååì
( , )y x Ay x yn n n nk k k k� � �� � � �1 1 1 0� � �x C .
Èñïîëüçóÿ ìîíîòîííîñòü îïåðàòîðà A, âûâîäèì
0 1 1 1� � � � �� � �( , )y x Ay x yn n n nk k k k
� ( , )y x x yn n nk k k� � �� � �1 1 1
� � � � � � �� � �� �( , ) ( , ) ( ,Ay y y Ay x y y x x yn n n n n n n nk k k k k k k1 1 1 k � �1 )
� � � ��� �( , ) ( , )Ay y y Ax x yn n n nk k k k1 .
Ñîâåðøèâ ïðåäåëüíûé ïåðåõîä ñ ó÷åòîì (9), ïîëó÷èì ( , )Ax x z� � 0 � �x C .
Ñëåäîâàòåëüíî, z VI A C� ( , ).
Ïîêàæåì, ÷òî x zn � ñëàáî (òîãäà èç | | | |x yn n� � 0 áóäåò ñëåäîâàòü y zn �
ñëàáî). Ðàññóæäàåì îò ïðîòèâíîãî. Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò ïîäïîñëåäîâà-
òåëüíîñòü ( )xmk
òàêàÿ, ÷òî x zmk
� � ñëàáî è z z
�. Èç íåðàâåíñòâà (5) è 0 3 1� ��L
ñëåäóåò
|| || || || || || || ||x x L x y x x L x yn n n n n n� � �� � � � � � �1
2
1
2 2
1� �
2 � �x VI A C( , ) .
Òàêèì îáðàçîì, äëÿ âñåõ x VI A C� ( , ) ñóùåñòâóåò
lim (|| || || || )
n
n n nx x L x y
��
�� � � �2
1
2
� � .
Ïðèìåíèâ äâàæäû ëåììó Îïÿëà:
lim (|| || || || ) lim (|| ||
n
n n n
k
nx z L x y x z
k��
�
��
� � � � �2
1
2 2
� � � ���L x yn nk k
|| || )1
2
� � � � � � � �
�� �� ��
lim || || lim || || lim (||
k
n
k
n
k
nx z x z x
k k k
2 2 z L x yn nk k
| | || || )2
1
2� � ���
� � � � � �
��
�lim (|| || || || )
n
n n nx z L x y2
1
2
�
� � � � � �
��
�lim (|| || || || )
k
m m mx z L x y
k k k
2
1
2
�
� � � � � �
�� ��
lim || || lim || ||
k
m
k
mx z x z
k k
2 2
� � � � � �
��
�
��
lim (| | | | | | | | ) lim ( | |
k
m m m
n
nx z L x y x z
k k k
2
1
2
� | | | | | | )2
1
2� � ��L x yn n ,
ïîëó÷èì ïðîòèâîðå÷èâîå íåðàâåíñòâî. Òàêèì îáðàçîì, z z� �.
Çàìåòèì, ÷òî ñëàáûé ïðåäåë z VI A C� ( , ) ïîðîæäåííîé àëãîðèòìîì 1 ïîñëå-
äîâàòåëüíîñòè ( )xn îáëàäàåò ñâîéñòâîì
P x zVI A C n( , ) � ñèëüíî. (10)
Äåéñòâèòåëüíî, èìååò ìåñòî ( , )( , ) ( , )P x x z P xVI A C n n VI A C n� � � 0. Åñëè äîêà-
çàòü, ÷òî P x zVI A C n( , ) � ñèëüíî, òî ïîñëå ïðåäåëüíîãî ïåðåõîäà ïîëó÷èì
( , )z z z z� � � 0, ò.å. z z� è âåðíî (10). Äîêàæåì ñèëüíóþ ñõîäèìîñòü
( )( , )P xVI A C n . Èìååì
| | | | | | | |( , ) ( , )x P x x P xn VI A C n n VI A C n� � �� � � �1 1
2
1
2
� � � � �| | | | | | | |( , )x P x L x yn VI A C n n n
2
1
2
� .
Èç ñóììèðóåìîñòè ðÿäà | | | |x yn n
n
� �� 1
2 ñëåäóåò ñóùåñòâîâàíèå
lim || ||( , )
n
n VI A C nx P x
��
� �� . Ïðèìåíèâ íåðàâåíñòâî (3) è ëåììó 2, ïîëó÷èì
|| || || || ||( , ) ( , ) ( , )P x P x x P x PVI A C m VI A C n m VI A C n V� � � �2 2
I A C m mx x( , ) ||� �2
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2 129
� � � � � �� �|| || || || ||( , ) ( , )x P x P x x L xm VI A C n VI A C m m m1 1
2 2
� ym� �2
2|| �
� � � � � � ��|| || || || ||( , ) ( , )x P x P x x L x yn VI A C n VI A C m m k
2 2
� 1 k
k n
m
�
�
� 2
2|| , m n .
Îòñþäà ñëåäóåò ôóíäàìåíòàëüíîñòü ïîñëåäîâàòåëüíîñòè ( )( , )P xVI A C n .
Çàìå÷àíèå 1. Àíàëîãè÷íîå òåîðåìå 1 óòâåðæäåíèå î ñõîäèìîñòè áóäåò
èìåòü ìåñòî è äëÿ èòåðàöèîííîãî ïðîöåññà
x P x Ay
y P x Ay
n H n n n
n C n n n
n�
� �
� �
� �
�
�
1
1 1
( ),
( ),
�
�
ãäå H z H x Ay y z yn n n n n n� � � � � �� �{ }: ( , )� 1 1 0 , ïðè óñëîâèè, ÷òî 0� �inf � n
� �sup � n
L
1
3
.
Çàìå÷àíèå 2. Î÷åâèäíûì íåäîñòàòêîì èçó÷åííîãî àëãîðèòìà ÿâëÿåòñÿ ïðåä-
ïîëîæåíèå î òîì, ÷òî êîíñòàíòà Ëèïøèöà L èçâåñòíà. Íåîáõîäèìî ðàçðàáîòàòü
âàðèàíò àëãîðèòìà áåç èñïîëüçîâàíèÿ ýòîé èíôîðìàöèè ñ ðåãóëèðîâêèé øàãà,
ïîäîáíîé èçâåñòíîìó ïðàâèëó Àðìèõî [9, 10].
 äàííîé ðàáîòå ðàññìîòðåíà ïðîáëåìà ïðèáëèæåííîãî ðåøåíèÿ âàðèàöèîí-
íûõ íåðàâåíñòâ ñ ìîíîòîííûìè è ëèïøèöåâûìè îïåðàòîðàìè, äåéñòâóþùèìè â
ãèëüáåðòîâîì ïðîñòðàíñòâå. Ïðåäëîæåí íîâûé èòåðàöèîííûé àëãîðèòì, îñíîâàí-
íûé íà äâóõ ìåòîäàõ: àëãîðèòìå Ïîïîâà [31] è ñóáãðàäèåíòíîì ýêñòðàãðàäèåíòíîì
àëãîðèòìå [32, 33]. Äîêàçàíà òåîðåìà î ñëàáîé ñõîäèìîñòè äëÿ ïîñëåäîâàòåëüíîñòåé,
ïîðîæäåííûõ àëãîðèòìîì. Îòìåòèì, ÷òî âû÷èñëèòåëüíûå çàòðàòû, íåîáõîäèìûå
äëÿ âûïîëíåíèÿ èòåðàöèîííîãî øàãà àëãîðèòìà 1, ïî÷òè ðàâíû çàòðàòàì äëÿ ðåàëè-
çàöèè øàãà â êëàññè÷åñêîì ìåòîäå ïðîåêöèè ãðàäèåíòà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ë è î í ñ Æ . - Ë . Íåêîòîðûå ìåòîäû ðåøåíèÿ íåëèíåéíûõ êðàåâûõ çàäà÷. — Ì.: Ìèð, 1972.
— 587 c.
2. Ê è í ä å ð ë å ð å ð Ä . , Ñ ò à ì ï à ê ê ü ÿ Ã . Ââåäåíèå â âàðèàöèîííûå íåðàâåíñòâà è èõ ïðèëî-
æåíèÿ. — Ì.: Ìèð, 1983. — 256 c.
3. Á à é î ê ê è Ê . , Ê à ï å ë î À . Âàðèàöèîííûå è êâàçèâàðèàöèîííûå íåðàâåíñòâà. — Ì.: Íàó-
êà, 1988. — 448 c.
4. Ê î í í î â È . Â . Î ñèñòåìàõ âàðèàöèîííûõ íåðàâåíñòâ // Èçâ. âóçîâ. Ìàòåìàòèêà. — 1997. —
¹ 12. — C. 79–88.
5. N a g u r n e y A . Network economics: A variational inequality approach. — Dordrecht: Kluwer
Academ. Publ., 1999. — 325 p.
6. Ñ å ì å í î â  .  . , Ñ å ì å í î â à Í .  . Î çàäà÷å âåêòîðíîãî óïðàâëåíèÿ â ãèëüáåðòîâîì ïðî-
ñòðàíñòâå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 2. — Ñ. 117–130.
7. Ã î ë ü ø ò å é í Å . Ã . , Ò ð å ò ü ÿ ê î â Í . Â . Ìîäèôèöèðîâàííûå ôóíêöèè Ëàãðàíæà. Òåîðèÿ
è ìåòîäû îïòèìèçàöèè. — Ì.: Íàóêà, 1989. — 400 c.
8. Á à ê ó ø è í ñ ê è é À . Á . , à î í ÷ à ð ñ ê è é À .  . Íåêîððåêòíûå çàäà÷è. ×èñëåííûå ìåòîäû
è ïðèëîæåíèÿ. — Ì.: Èçä-âî ÌÃÓ, 1989. — 200 c.
9. K o n n o v I . V . Combined relaxation methods for variational inequalities. — Berlin; Heidelberg;
New York: Springer-Verlag, 2001. — 181 p.
10. Fa c c h i n e i F . , P a n g J . - S . Finite-dimensional variational inequalities and complementarity
problem. V. 2. — New York: Springer, 2003. — 666 p.
11. Â à ñ è í Â . Â . , Å ð å ì è í È . È . Îïåðàòîðû è èòåðàöèîííûå ïðîöåññû ôåéåðîâñêîãî òèïà. (Òå-
îðèÿ è ïðèëîæåíèÿ). — Ìîñêâà; Èæåâñê: Ðåãóëÿðíàÿ è õàîòè÷åñêàÿ äèíàìèêà, 2005. — 200 c.
12. Ï ø å í è ÷ í û é Á . Í . , Ê à ë æ à í î â Ì . Ó . Ìåòîä ðåøåíèÿ âàðèàöèîííûõ íåðàâåíñòâ // Êè-
áåðíåòèêà è ñèñòåìíûé àíàëèç. — 1992. — ¹ 6. — Ñ. 48–55.
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2
13. Ê à ë à ø í è ê î â Â . Â . , Ê à ë à ø í è ê î â à Í . È . Ðåøåíèå äâóõóðîâíåâîãî âàðèàöèîííîãî
íåðàâåíñòâà // Òàì æå. — 1994. — ¹ 4. — Ñ. 178–180.
14. Ï à í è í  . Ì . , Ñ ê î ï å ö ê è é  .  . , Ë à â ð è í à Ò .  . Ìîäåëè è ìåòîäû êîíå÷íîìåðíûõ
âàðèàöèîííûõ íåðàâåíñòâ // Òàì æå. — 2000. — ¹ 6. — Ñ. 47–64.
15. X i u N . , Z h a n g J . Some recent advances in projection-type methods for variational inequalities
// J. Comput. Appl. Math. — 2003. — 152. — Ð. 559–585.
16. N a d e z h k i n a N . , T a k a h a s h i W . Strong convergence theorem by a hybrid method for non-
expansive mappings and Lipschitz-continuous monotone mappings // SIAM J. Optim. — 2006. —
16, N 4. — P. 1230–1241.
17. N a d e z h k i n a N . , T a k a h a s h i W . Weak convergence theorem by an extragradient method
for nonexpansive mappings and monotone mappings // J. Optim. Theory and Appl. — 2006. — 128.
— P. 191–201.
18. Í ó ð ì è í ñ ê è é Å . À . Èñïîëüçîâàíèå äîïîëíèòåëüíûõ ìàëûõ âîçäåéñòâèé â ôåéåðîâñêèõ
ìîäåëÿõ èòåðàòèâíûõ àëãîðèòìîâ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2008. — 48,
¹ 12. — Ñ. 2121–2128.
19. Ñ å ì å í î â Â . Â . Î ìåòîäå ïàðàëëåëüíîé ïðîêñèìàëüíîé äåêîìïîçèöèè äëÿ ðåøåíèÿ çàäà÷
âûïóêëîé îïòèìèçàöèè // Ìåæäóíàðîäíûé íàó÷íî-òåõíè÷åñêèé æóðíàë «Ïðîáëåìû óïðàâëå-
íèÿ è èíôîðìàòèêè». — 2010. — ¹ 2. — Ñ. 42–46.
20. Ì à ë ³ ö ü ê è é Þ .  . , Ñ å ì å í î â  .  . Íîâ³ òåîðåìè ñèëüíî¿ çá³æíîñò³ ïðîêñèìàëüíîãî
ìåòîäó äëÿ çàäà÷³ ð³âíîâàæíîãî ïðîãðàìóâàííÿ // Æóðí. îá÷èñë. òà ïðèêë. ìàòåìàòèêè. —
2010. — ¹ 3 (102). — Ñ. 79–88.
21. Ñ å ì å í î â Â . Â . Î ñõîäèìîñòè ìåòîäîâ ðåøåíèÿ äâóõóðîâíåâûõ âàðèàöèîííûõ íåðàâåíñòâ
ñ ìîíîòîííûìè îïåðàòîðàìè // Òàì æå. — 2010. — ¹ 2 (101). — Ñ. 120–128.
22. Ä å í è ñ î â Ñ .  . , Ñ å ì å í î â  .  . Ïðîêñèìàëüíèé àëãîðèòì äëÿ äâîð³âíåâèõ âàð³àö³éíèõ
íåð³âíîñòåé: ñèëüíà çá³æí³ñòü // Òàì æå. — 2011. — ¹ 3 (106). — C. 27–32.
23. Ñ å ì å í î â Â . Â . Ïàðàëëåëüíàÿ äåêîìïîçèöèÿ âàðèàöèîííûõ íåðàâåíñòâ ñ ìîíîòîííûìè
îïåðàòîðàìè // Òàì æå. — 2012. — ¹ 2 (108). — Ñ. 53–58.
24. À í ò è ï è í À . Ñ . Î ìåòîäå âûïóêëîãî ïðîãðàììèðîâàíèÿ, èñïîëüçóþùåì ñèììåòðè÷åñêóþ
ìîäèôèêàöèþ ôóíêöèè Ëàãðàíæà // Ýêîíîìèêà è ìàò. ìåòîäû. — 1976. — 12, ¹ 6. —
Ñ. 1164–1173.
25. Ê î ð ï å ë å â è ÷ à . Ì . Ýêñòðàãðàäèåíòíûé ìåòîä äëÿ îòûñêàíèÿ ñåäëîâûõ òî÷åê è äðóãèõ çà-
äà÷ // Òàì æå. — 1976. — 12, ¹ 4. — Ñ. 747–756.
26. Õ î á î ò î â Å . Í . Î ìîäèôèêàöèè ýêñòðàãðàäèåíòíîãî ìåòîäà äëÿ ðåøåíèÿ âàðèàöèîííûõ íå-
ðàâåíñòâ è íåêîòîðûõ çàäà÷ îïòèìèçàöèè // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. —
1987. — 27, ¹ 10. — Ñ. 1462–1473.
27. Ç û ê è í à À . Â . , Ì å ë å í ü ÷ ó ê Í . Â . Äâóõøàãîâûé ýêñòðàãðàäèåíòíûé ìåòîä äëÿ âàðèà-
öèîííûõ íåðàâåíñòâ // Èçâ. âóçîâ. Ìàòåìàòèêà. — 2010. — ¹ 9. — Ñ. 82–85.
28. Ç à ï î ð î æ å ö Ä . Í . , Ç û ê è í à À . Â . , Ì å ë å í ü ÷ ó ê Í . Â . Ñðàâíèòåëüíûé àíàëèç ýêñ-
òðàãðàäèåíòíûõ ìåòîäîâ ðåøåíèÿ âàðèàöèîííûõ íåðàâåíñòâ äëÿ íåêîòîðûõ çàäà÷ //
Àâòîìàòàòèêà è òåëåìåõàíèêà. — 2012. — ¹ 4. — Ñ. 32–46.
29.  î é ò î â à Ò . À . , Ä å í è ñ î â Ñ .  . , Ñ å ì å í î â  .  . Ñèëüíî çá³æíèé ìîäèô³êîâàíèé
âàð³àíò ìåòîäó Êîðïåëåâè÷ äëÿ çàäà÷ ð³âíîâàæíîãî ïðîãðàìóâàííÿ // Æóðí. îá÷èñë. òà ïðèêë.
ìàòåìàòèêè. — 2011. — ¹ 1 (104). — Ñ. 10–23.
30. À ï î ñ ò î ë Ð . ß . , à ð è í å í ê î À . À . , Ñ å ì å í î â  .  . ²òåðàö³éí³ àëãîðèòìè äëÿ ìîíî-
òîííèõ äâîð³âíåâèõ âàð³àö³éíèõ íåð³âíîñòåé // Òàì æå. — 2012. — ¹ 1 (107). — C. 3–14.
31. Ï î ï î â Ë . Ä . Ìîäèôèêàöèÿ ìåòîäà Ýððîó–Ãóðâèöà ïîèñêà ñåäëîâûõ òî÷åê // Ìàò. çàìåòêè.
— 1980. — 28, ¹ 5. — Ñ. 777–784.
32. C e n s o r Y . , G i b a l i A . , R e i c h S . The subgradient extragradient method for solving varia-
tional inequalities in Hilbert space // J. Optim. Theory and Appl. — 2011. — 148. — P. 318–335.
33. Ë ÿ ø ê î Ñ . È . , Ñ å ì å í î â  .  . ,  î é ò î â à Ò . À . Ýêîíîìè÷íàÿ ìîäèôèêàöèÿ ìåòîäà
Êîðïåëåâè÷ äëÿ ìîíîòîííûõ çàäà÷ î ðàâíîâåñèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011.
— ¹ 4. — C. 146–154.
34. B a u s c h k e H . H . , C o m b e t t e s P . L . Convex analysis and monotone operator theory in Hil-
bert spaces. — Berlin; Heidelberg; New York: Springer, 2011. — 408 p.
35. O p i a l Z . Weak convergence of the sequence of successive approximations for nonexpansive
mappings // Bull. Amer. Math. Soc. — 1967. — 73. — P. 591–597.
Ïîñòóïèëà 24.04.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 2 131
|