Адаптивный двухэтапный проксимальный алгоритм для задачи о равновесии в пространствах Адамара
Рассмотрены задачи о равновесии в метрических пространствах Адамара. Для приближенного решения задач предложен и изучен новый адаптивный двухэтапный проксимальный алгоритм. В отличие от применяемых ранее правил выбора величины шага в предлагаемом алгоритме не проводятся вычисления значений бифункции...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/190522 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Адаптивный двухэтапный проксимальный алгоритм для задачи о равновесии в пространствах Адамара / Я.И. Ведель, Г.В. Сандраков, В.В. Семенов // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 136–148. — Бібліогр.: 33 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-190522 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1905222025-02-09T10:02:45Z Адаптивный двухэтапный проксимальный алгоритм для задачи о равновесии в пространствах Адамара Адаптивний двоетапний проксимальний алгоритм для задачі про рівновагу в просторах Адамара An adaptive two-stage proximal algorithm for equilibrium problems in Hadamard spaces Ведель, Я.И. Сандраков, Г.В. Семенов, В.В. Системний аналіз Рассмотрены задачи о равновесии в метрических пространствах Адамара. Для приближенного решения задач предложен и изучен новый адаптивный двухэтапный проксимальный алгоритм. В отличие от применяемых ранее правил выбора величины шага в предлагаемом алгоритме не проводятся вычисления значений бифункции в дополнительных точках и не требуется знания информации о величине липшицевых констант бифункции. Для псевдомонотонных бифункций липшицевого типа доказана теорема о слабой сходимости порожденных алгоритмом последовательностей. Предложенный алгоритм применим к псевдомонотонным вариационным неравенствам в гильбертовых пространствах. Розглянуто задачі про рівновагу в метричних просторах Адамара. Для наближеного розв'язання задач запропоновано та досліджено новий ітераційний адаптивний двоетапний проксимальний алгоритм. На відміну від правил вибору величини кроку, що застосовувалися раніше, в запропонованому алгоритмі не виконуються обчислення значень біфункції в додаткових точках, а також знання інформації про величину ліпшицевих констант біфункції не потрібно. Для псевдомонотонних біфункцій ліпшицевого типу доведено теорему про слабку збіжність породжених алгоритмом послідовностей. Запропонований алгоритм можна застосувати до псевдомонотонних варіаційних нерівностей у гільбертових просторах. Equilibrium problems in Hadamard metric spaces are considered in the paper. For an approximate solution of problems, a new iterative adaptive two-stage proximal algorithm is proposed and analyzed. In contrast to the previously used rules for choosing the step size, the proposed algorithm does not calculate bifunction values at additional points and does not require knowledge of the value of bifunction’s Lipschitz constants. For pseudo-monotone bifunctions of Lipschitz type, the theorem on weak convergence of the sequences generated by the algorithm is proved. It is shown that the proposed algorithm is applicable to pseudo-monotone variational inequalities in Hilbert spaces. Работа выполнена при финансовой поддержке МОН Украины (проект «Математичне моделювання та оптимiзацiя динамiчних систем для оборони, медицини та екології», номер госрегистрации 0219U008403) и НАН Украины (проект «Нові методи дослідження коректності та розв язання задач дискретної оптимізації, варіаційних нерівностей та їх застосування», номер госрегистрации 0119U101608). 2020 Article Адаптивный двухэтапный проксимальный алгоритм для задачи о равновесии в пространствах Адамара / Я.И. Ведель, Г.В. Сандраков, В.В. Семенов // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 136–148. — Бібліогр.: 33 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190522 517.988 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2020 |
| topic_facet |
Системний аналіз |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/190522 |
| citation_txt |
Адаптивный двухэтапный проксимальный алгоритм для задачи о равновесии в пространствах Адамара / Я.И. Ведель, Г.В. Сандраков, В.В. Семенов // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 136–148. — Бібліогр.: 33 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT vedelʹâi adaptivnyjdvuhétapnyjproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT sandrakovgv adaptivnyjdvuhétapnyjproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT semenovvv adaptivnyjdvuhétapnyjproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT vedelʹâi adaptivnijdvoetapnijproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT sandrakovgv adaptivnijdvoetapnijproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT semenovvv adaptivnijdvoetapnijproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT vedelʹâi anadaptivetwostageproximalalgorithmforequilibriumproblemsinhadamardspaces AT sandrakovgv anadaptivetwostageproximalalgorithmforequilibriumproblemsinhadamardspaces AT semenovvv anadaptivetwostageproximalalgorithmforequilibriumproblemsinhadamardspaces |
| first_indexed |
2025-11-25T16:32:58Z |
| last_indexed |
2025-11-25T16:32:58Z |
| _version_ |
1849780737495007232 |
| fulltext |
ÓÄÊ 517.988
ß.È. ÂÅÄÅËÜ, Ã.Â. ÑÀÍÄÐÀÊÎÂ, Â.Â. ÑÅÌÅÍÎÂ
ÀÄÀÏÒÈÂÍÛÉ ÄÂÓÕÝÒÀÏÍÛÉ ÏÐÎÊÑÈÌÀËÜÍÛÉ ÀËÃÎÐÈÒÌ
ÄËß ÇÀÄÀ×È Î ÐÀÂÍÎÂÅÑÈÈ Â ÏÐÎÑÒÐÀÍÑÒÂÀÕ ÀÄÀÌÀÐÀ 1
Àííîòàöèÿ. Ðàññìîòðåíû çàäà÷è î ðàâíîâåñèè â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ
Àäàìàðà. Äëÿ ïðèáëèæåííîãî ðåøåíèÿ çàäà÷ ïðåäëîæåí è èçó÷åí íîâûé
àäàïòèâíûé äâóõýòàïíûé ïðîêñèìàëüíûé àëãîðèòì.  îòëè÷èå îò ïðèìå-
íÿåìûõ ðàíåå ïðàâèë âûáîðà âåëè÷èíû øàãà â ïðåäëàãàåìîì àëãîðèòìå íå
ïðîâîäÿòñÿ âû÷èñëåíèÿ çíà÷åíèé áèôóíêöèè â äîïîëíèòåëüíûõ òî÷êàõ è íå
òðåáóåòñÿ çíàíèÿ èíôîðìàöèè î âåëè÷èíå ëèïøèöåâûõ êîíñòàíò áèôóíê-
öèè. Äëÿ ïñåâäîìîíîòîííûõ áèôóíêöèé ëèïøèöåâîãî òèïà äîêàçàíà òåîðå-
ìà î ñëàáîé ñõîäèìîñòè ïîðîæäåííûõ àëãîðèòìîì ïîñëåäîâàòåëüíîñòåé.
Ïðåäëîæåííûé àëãîðèòì ïðèìåíèì ê ïñåâäîìîíîòîííûì âàðèàöèîííûì íå-
ðàâåíñòâàì â ãèëüáåðòîâûõ ïðîñòðàíñòâàõ.
Êëþ÷åâûå ñëîâà: ïðîñòðàíñòâî Àäàìàðà, çàäà÷à î ðàâíîâåñèè, ïñåâäîìîíî-
òîííîñòü, äâóõýòàïíûé ïðîêñèìàëüíûé àëãîðèòì, àäàïòèâíîñòü, ñõîäèìîñòü.
ÂÂÅÄÅÍÈÅ
Èçâåñòíûì íàïðàâëåíèåì ñîâðåìåííîãî ïðèêëàäíîãî íåëèíåéíîãî àíàëèçà ÿâ-
ëÿåòñÿ èññëåäîâàíèå çàäà÷ î ðàâíîâåñèè. Â ðÿäå ïóáëèêàöèé äëÿ ðåøåíèÿ çà-
äà÷ î ðàâíîâåñèè â ãèëüáåðòîâîì ïðîñòðàíñòâå áûë ïðåäëîæåí äâóõýòàïíûé
ïðîêñèìàëüíûé àëãîðèòì.  íàñòîÿùåå âðåìÿ ïîÿâèëñÿ èíòåðåñ ê çàäà÷àì
î ðàâíîâåñèè â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ Àäàìàðà, â ÷àñòíîñòè èçó÷åí àíà-
ëîã äâóõýòàïíîãî ïðîêñèìàëüíîãî àëãîðèòìà.
 äàííîé ñòàòüå ïðåäëàãàåòñÿ íîâûé àäàïòèâíûé äâóõýòàïíûé ïðîêñèìàëü-
íûé àëãîðèòì äëÿ ïðèáëèæåííîãî ðåøåíèÿ çàäà÷ î ðàâíîâåñèè â ìåòðè÷åñêèõ
ïðîñòðàíñòâàõ Àäàìàðà.  îòëè÷èå îò ïðèìåíÿåìîãî ðàíåå àëãîðèòìà â ðàññìàò-
ðèâàåìîì àëãîðèòìå íå ïðîâîäèòñÿ âû÷èñëåíèé çíà÷åíèé áèôóíêöèè â äîïîëíè-
òåëüíûõ òî÷êàõ è íå òðåáóåòñÿ çíàíèé ëèïøèöåâûõ êîíñòàíò áèôóíêöèè. Äëÿ
ïñåâäîìîíîòîííûõ áèôóíêöèé ëèïøèöåâîãî òèïà äîêàçàíà òåîðåìà î ñëàáîé
ñõîäèìîñòè ïîðîæäåííûõ àëãîðèòìîì ïîñëåäîâàòåëüíîñòåé. Ïîêàçàíî, ÷òî ïðåä-
ëîæåííûé àëãîðèòì ïðèìåíèì ê ïñåâäîìîíîòîííûì âàðèàöèîííûì íåðàâåí-
ñòâàì â ãèëüáåðòîâûõ ïðîñòðàíñòâàõ.
ÎÁÇÎÐ ÈÇÂÅÑÒÍÛÕ ÐÅÇÓËÜÒÀÒÎÂ
Îäíèì èç íàïðàâëåíèé ñîâðåìåííîãî ïðèêëàäíîãî íåëèíåéíîãî àíàëèçà ÿâëÿ-
åòñÿ èññëåäîâàíèå çàäà÷ î ðàâíîâåñèè (íåðàâåíñòâ Êè Ôàíÿ, çàäà÷ ðàâíîâåñíî-
ãî ïðîãðàììèðîâàíèÿ) ñëåäóþùåãî âèäà [1–13]:
íàéòè x Ñ� : F x y( , ) � 0 � �y Ñ, (1)
ãäå Ñ — íåïóñòîå ïîäìíîæåñòâî ãèëüáåðòîâà ïðîñòðàíñòâà H; F C C: � �� —
ôóíêöèÿ òàêàÿ, ÷òî F x x( , ) � 0 äëÿ âñåõ x Ñ� (íàçûâàåìàÿ áèôóíêöèåé).
 âèäå (1) ìîæíî ñôîðìóëèðîâàòü çàäà÷è ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ,
âàðèàöèîííûå íåðàâåíñòâà è ðàçëè÷íûå èãðîâûå çàäà÷è. Ïðèâåäåì äâå òèïè÷-
íûå ôîðìóëèðîâêè [1, 2].
136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
1 Ðàáîòà âûïîëíåíà ïðè ôèíàíñîâîé ïîääåðæêå ÌÎÍ Óêðàèíû (ïðîåêò «Ìàòåìàòè÷íå
ìîäåëþâàííÿ òà îïòèìiçàöiÿ äèíàìi÷íèõ ñèñòåì äëÿ îáîðîíè, ìåäèöèíè òà åêîëî㳿», íîìåð
ãîñðåãèñòðàöèè 0219U008403) è ÍÀÍ Óêðàèíû (ïðîåêò «Íîâ³ ìåòîäè äîñë³äæåííÿ êîðåêòíîñò³ òà
ðîçâ’ÿçàííÿ çàäà÷ äèñêðåòíî¿ îïòèì³çàö³¿, âàð³àö³éíèõ íåð³âíîñòåé òà ¿õ çàñòîñóâàííÿ», íîìåð
ãîñðåãèñòðàöèè 0119U101608).
© ß.È. Âåäåëü, Ã.Â. Ñàíäðàêîâ, Â.Â. Ñåìåíîâ, 2020
1. Åñëè F x y Ax y x( , ) ( , )� � , ãäå A C H: � , òî çàäà÷à (1) ñâîäèòñÿ ê êëàññè-
÷åñêîìó âàðèàöèîííîìó íåðàâåíñòâó:
íàéòè x Ñ� : ( , )Ax y x� � 0 � �y Ñ.
2. Äëÿ êàæäîãî i I� , ãäå I — êîíå÷íîå ìíîæåñòâî èíäåêñîâ, çàäàíû ìíî-
æåñòâî Ci è ôóíêöèÿ � i C: �� , ãäå C Cii I
�
� . Äëÿ x x Ci i I� ��( ) îáîçíà-
÷èì x xi
j j I i� �( ) \{ }. Òî÷êó x x Ci i I� ��( ) íàçûâàþò ðàâíîâåñèåì Íýøà, åñëè äëÿ
âñåõ i I� âûïîëíÿþòñÿ íåðàâåíñòâà � �i i i ix x y( ) ( , )
� �y Ñi i . Îïðåäåëèì
ôóíêöèþ F C C: � �� ñëåäóþùèì îáðàçîì:
F x y x y xi
i
i ii I
( , ) ( ( , ) ( ))� �
�� � � .
Òî÷êà x C� ÿâëÿåòñÿ ðàâíîâåñèåì Íýøà òîãäà è òîëüêî òîãäà, êîãäà îíà ÿâëÿ-
åòñÿ ðåøåíèåì çàäà÷è (1).
Èññëåäîâàíèå àëãîðèòìîâ ðåøåíèÿ ðàâíîâåñíûõ è áëèçêèõ çàäà÷ îñâåùàåòñÿ
âî ìíîãèõ ïóáëèêàöèÿõ. ×àñòíûì ñëó÷àåì çàäà÷ î ðàâíîâåñèè ÿâëÿþòñÿ âàðèàöè-
îííûå íåðàâåíñòâà [14, 15]. Äëÿ èõ ðåøåíèÿ â ðàáîòå [16] ïðåäëîæåí ýêñòðà-
ãðàäèåíòíûé ìåòîä. Ýôôåêòèâíûì ñîâðåìåííûì âàðèàíòîì ýêñòðàãðàäèåíòíîãî
ìåòîäà ÿâëÿåòñÿ ïðîêñèìàëüíûé çåðêàëüíûé ìåòîä Íåìèðîâñêîãî [17], êîòîðûé
ìîæíî ïðîèíòåðïðåòèðîâàòü êàê âàðèàíò ýêñòðàãðàäèåíòíîãî ìåòîäà ñ ïðîåêòè-
ðîâàíèåì îòíîñèòåëüíî ðàñõîæäåíèÿ Áðýãìàíà. Â ñòàòüÿõ [18–20] ïðåäëîæåíû
àäàïòèâíûå ìîäèôèêàöèè ïðîêñèìàëüíîãî çåðêàëüíîãî ìåòîäà, íå òðåáóþùèå
çíàíèÿ êîíñòàíò Ëèïøèöà îïåðàòîðîâ äëÿ îïðåäåëåíèÿ âåëè÷èíû øàãà.
Àíàëîãàì ýêñòðàãðàäèåíòíîãî ìåòîäà äëÿ çàäà÷ î ðàâíîâåñèè è áëèçêèì
âîïðîñàì ïîñâÿùåíû ðàáîòû [3, 5, 7, 8, 21–25]. Îäíèì èç òàêèõ ìåòîäîâ ÿâëÿåòñÿ
ýêñòðàïðîêñèìàëüíûé àëãîðèòì âèäà
y x
x x
n F x n
n F y n
n n
n n
�
�
�
�
�
� �
prox
prox
�
�
( , )
( , )
,
,1
ãäå � n � ��( , )0 , prox � — ïðîêñèìàëüíûé îïåðàòîð ôóíêöèè � [3, 5].
Ë.Ä. Ïîïîâ â ðàáîòå [26] ïðåäëîæèë äëÿ ïîèñêà ñåäëîâûõ òî÷åê âûïóê-
ëî-âîãíóòûõ ôóíêöèé, îïðåäåëåííûõ â êîíå÷íîìåðíîì åâêëèäîâîì ïðîñòðàí-
ñòâå, èíòåðåñíóþ ìîäèôèêàöèþ ìåòîäà Ýððîó–Ãóðâèöà. Â ñòàòüå [9] äëÿ ðåøå-
íèÿ çàäà÷ î ðàâíîâåñèè â ãèëüáåðòîâîì ïðîñòðàíñòâå áûë ïðåäëîæåí
äâóõýòàïíûé ïðîêñèìàëüíûé àëãîðèòì âèäà
y x
x x
n F y n
n F y n
n n
n n
�
�
�
�
� �
� �
prox
prox
�
�
( , )
( , )
,
,
1
1
ãäå � n � ��( , )0 , ÿâëÿþùèéñÿ àäàïòàöèåé ìåòîäà Ë.Ä. Ïîïîâà ê îáùèì çàäà-
÷àì ðàâíîâåñíîãî ïðîãðàììèðîâàíèÿ (ñì. òàêæå [10, 27, 28]).
 íàñòîÿùåå âðåìÿ âîçíèêëà ïîòðåáíîñòü â ïîñòðîåíèè òåîðèè è àëãîðèòìîâ
ðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ â ìåòðè÷åñêèõ ïðîñòðàí-
ñòâàõ Àäàìàðà [29] (CAT ( )0 -ïðîñòðàíñòâàõ). Ýòî îáóñëîâëåíî ïðîáëåìàìè ìàòå-
ìàòè÷åñêîé áèîëîãèè è ìàøèííîãî îáó÷åíèÿ. Ñèëüíîé ìîòèâàöèåé äëÿ èçó÷åíèÿ
äàííûõ çàäà÷ ÿâëÿåòñÿ òàêæå âîçìîæíîñòü çàïèñàòü íåêîòîðûå íåâûïóêëûå çà-
äà÷è â âèäå ãåîäåçè÷åñêè âûïóêëûõ â ïðîñòðàíñòâå ñî ñïåöèàëüíî ïîäîáðàííîé
ðèìàíîâîé ìåòðèêîé [11, 29]. Òàêæå ïîÿâèëñÿ èíòåðåñ ê çàäà÷àì î ðàâíîâåñèè
â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ Àäàìàðà [11–13].  ñòàòüå [11] ïîëó÷åíû òåîðåìû
ñóùåñòâîâàíèÿ ðåøåíèÿ äëÿ çàäà÷ î ðàâíîâåñèè íà ìíîãîîáðàçèÿõ Àäàìàðà, ðàñ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 137
ñìîòðåíû ïðèëîæåíèÿ ê âàðèàöèîííûì íåðàâåíñòâàì è îáîñíîâàí ðåçîëüâåíò-
íûé ìåòîä äëÿ àïïðîêñèìàöèè ðåøåíèé çàäà÷ î ðàâíîâåñèè è âàðèàöèîííûõ íå-
ðàâåíñòâàõ. Â ðàáîòå [12] äëÿ áîëåå îáùèõ çàäà÷ î ðàâíîâåñèè ñ ïñåâäîìîíîòîí-
íûìè áèôóíêöèÿìè â ïðîñòðàíñòâàõ Àäàìàðà ïîëó÷åíû òåîðåìû ñóùåñòâîâàíèÿ
äëÿ çàäà÷ î ðàâíîâåñèè, ïðåäëîæåí ïðîêñèìàëüíûé àëãîðèòì è äîêàçàíà åãî ñõî-
äèìîñòü. Áîëåå êîíñòðóêòèâíîìó ïîäõîäó ïîñâÿùåíà ðàáîòà [13], àâòîðû êîòî-
ðîé, èñõîäÿ èç ðåçóëüòàòîâ ñòàòüè [5], ïðåäëîæèëè è îáîñíîâàëè äëÿ
ïñåâäîìîíîòîííûõ çàäà÷ î ðàâíîâåñèè â ïðîñòðàíñòâàõ Àäàìàðà àíàëîã
ýêñòðàïðîêñèìàëüíîãî ìåòîäà. À â áîëåå ïîçäíåé ðàáîòå [30] èçó÷åí àíàëîã
äâóõýòàïíîãî ïðîêñèìàëüíîãî àëãîðèòìà [9].
 íàñòîÿùåé ñòàòüå, êîòîðàÿ ÿâëÿåòñÿ ïðîäîëæåíèåì ðàáîò [18, 30], ïðåäëî-
æåí íîâûé àäàïòèâíûé äâóõýòàïíûé ïðîêñèìàëüíûé àëãîðèòì äëÿ ïðèáëèæåí-
íîãî ðåøåíèÿ çàäà÷ î ðàâíîâåñèè â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ Àäàìàðà.  îòëè-
÷èå îò ïðèìåíÿåìûõ ðàíåå ïðàâèë âûáîðà âåëè÷èíû øàãà [9, 10, 27, 28, 30]
â ïðåäëàãàåìîì àëãîðèòìå íå ïðîâîäèòñÿ âû÷èñëåíèé çíà÷åíèé áèôóíêöèè â äî-
ïîëíèòåëüíûõ òî÷êàõ è íå òðåáóåòñÿ çíàíèÿ ëèïøèöåâûõ êîíñòàíò áèôóíêöèè.
Äëÿ ïñåâäîìîíîòîííûõ áèôóíêöèé ëèïøèöåâîãî òèïà äîêàçàíà òåîðåìà î ñëà-
áîé ñõîäèìîñòè ïîðîæäåííûõ àëãîðèòìîì ïîñëåäîâàòåëüíîñòåé. Äîêàçàòåëüñòâî
îñíîâàíî íà èñïîëüçîâàíèè ìîäèôèöèðîâàííîé îöåíêè èç ðàáîòû [30]. Ïîêàçàíî,
÷òî ïðåäëîæåííûé àëãîðèòì ïðèìåíèì ê ïñåâäîìîíîòîííûì âàðèàöèîííûì
íåðàâåíñòâàì â ãèëüáåðòîâûõ ïðîñòðàíñòâàõ.
ÏÐÎÑÒÐÀÍÑÒÂÀ ÀÄÀÌÀÐÀ
Èçëîæèì íåñêîëüêî ïîíÿòèé è ôàêòîâ îòíîñèòåëüíî ïðîñòðàíñòâ Àäàìàðà (áî-
ëåå äåòàëüíî èçëîæåíî â [29, 31, 32]).
Ïóñòü ( , )X d — ìåòðè÷åñêîå ïðîñòðàíñòâî è x , y X� . Ãåîäåçè÷åñêèì ïóòåì,
ñîåäèíÿþùèì òî÷êè x è y , íàçûâàþò èçîìåòðèþ �: [ , ( , )]0 d x y X� òàêóþ, ÷òî
� ( )0 � x, � ( ( , ))d x y y� . Ìíîæåñòâî � ([ , ( , )])0 d x y X� îáîçíà÷àþò [ , ]x y è íàçû-
âàþò ãåîäåçè÷åñêèì ñåãìåíòîì (èëè ãåîäåçè÷åñêîé) ñ êîíöàìè x è y . Ìåòðè÷åñ-
êîå ïðîñòðàíñòâî ( , )X d íàçûâàþò ãåîäåçè÷åñêèì ïðîñòðàíñòâîì, åñëè ëþáûå
äâå òî÷êè X ìîæíî ñîåäèíèòü ãåîäåçè÷åñêîé, è îäíîçíà÷íî ãåîäåçè÷åñêèì ïðî-
ñòðàíñòâîì, åñëè äëÿ ëþáûõ äâóõ òî÷åê X ñóùåñòâóåò â òî÷íîñòè îäíà ãåîäåçè-
÷åñêàÿ, èõ ñîåäèíÿþùàÿ.
Ãåîäåçè÷åñêîå ïðîñòðàíñòâî ( , )X d íàçûâàþò CAT ( )0 -ïðîñòðàíñòâîì, åñëè
äëÿ ëþáîé òðîéêè òî÷åê y0 , y1, y X2 � òàêèõ, ÷òî d y y2
1 0( , ) � d y y2
2 0( , ) �
�
1
2
2
1 2d y y( , ) , âûïîëíÿåòñÿ íåðàâåíñòâî
d x y2
0( , )
1
2
1
2
1
4
2
1
2
2
2
1 2d x y d x y d y y( , ) ( , ) ( , )� � � �x X . (2)
Íåðàâåíñòâî (2) èíîãäà íàçûâàþò CN -íåðàâåíñòâîì [31] (çàìåòèì, ÷òî â åâêëè-
äîâîì ïðîñòðàíñòâå íåðàâåíñòâî (2) ïðåîáðàçóåòñÿ â òîæäåñòâî), à òî÷êó y0 —
ñåðåäèíîé ìåæäó òî÷êàìè y1 è y2 , êîòîðàÿ âñåãäà ñóùåñòâóåò â ãåîäåçè÷åñêîì
ïðîñòðàíñòâå.
Èçâåñòíî, ÷òî CAT ( )0 -ïðîñòðàíñòâî ÿâëÿåòñÿ îäíîçíà÷íî ãåîäåçè÷åñêèì [29].
Äëÿ òî÷åê x è y CAT ( )0 -ïðîñòðàíñòâà ( , )X d è t �[ , ]0 1 îáîçíà÷èì tx t y� �( )1
òàêóþ åäèíñòâåííóþ òî÷êó z ñåãìåíòà [ , ]x y , ÷òî d z x t d x y( , ) ( ) ( , )� �1 è
d z y td x y( , ) ( , )� . Ìíîæåñòâî C X� íàçûâàåòñÿ âûïóêëûì (ãåîäåçè÷åñêè âûïóê-
ëûì), åñëè äëÿ âñåõ x , y C� è t �[ , ]0 1 âûïîëíÿåòñÿ óñëîâèå tx t y C� � �( )1 .
Ïîëåçíûì èíñòðóìåíòîì äëÿ ðàáîòû â CAT ( )0 -ïðîñòðàíñòâå ( , )X d ÿâëÿåòñÿ
íåðàâåíñòâî
138 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
d tx t y z2 1( ( ) , )� �
td x z t d y z t t d x y2 2 21 1( , ) ( ) ( , ) ( ) ( , )� � � � ,
(3)
{ }x y z X, , � , t �[ , ]0 1 .
Çàìå÷àíèå 1. Âàæíûìè ïðèìåðàìè CAT ( )0 -ïðîñòðàíñòâ ÿâëÿþòñÿ åâêëèäî-
âû ïðîñòðàíñòâà, �-äåðåâüÿ, ìíîãîîáðàçèÿ Àäàìàðà (ïîëíûå ñâÿçíûå ðèìàíîâû
ìíîãîîáðàçèÿ íåïîëîæèòåëüíîé êðèâèçíû) è ãèëüáåðòîâ øàð ñ ãèïåðáîëè÷åñêîé
ìåòðèêîé [29, 31, 32].
Ïîëíîå CAT ( )0 -ïðîñòðàíñòâî íàçûâàþò ïðîñòðàíñòâîì Àäàìàðà.
Ïóñòü ( , )X d — ìåòðè÷åñêîå ïðîñòðàíñòâî è ( )xn — îãðàíè÷åííàÿ ïîñëåäî-
âàòåëüíîñòü ýëåìåíòîâ X . Ïóñòü òàêæå r x x d x xn
n
n( , ( )) lim ( , )�
��
. ×èñëî r xn(( )) �
= inf x X nr x x� ( , ( )) íàçûâàþò àñèìïòîòè÷åñêèì ðàäèóñîì ( )xn , à ìíîæåñòâî
A x x X r x x r xn n n(( )) : ( , ( )) (( ))� � �{ } — àñèìïòîòè÷åñêèì öåíòðîì ( )xn . Èçâå-
ñòíî, ÷òî â ïðîñòðàíñòâå Àäàìàðà ìíîæåñòâî A xn(( )) ñîñòîèò èç îäíîé òî÷êè [29].
Ïîñëåäîâàòåëüíîñòü ( )xn ýëåìåíòîâ ïðîñòðàíñòâà Àäàìàðà ( , )X d ñëàáî ñõî-
äèòñÿ (�-ñõîäèòñÿ [31]) ê ýëåìåíòó x X� , åñëè A x xnk
(( )) � { } äëÿ ëþáîé ïîäïîñëå-
äîâàòåëüíîñòè ( )xnk
. Èçâåñòíî, ÷òî ïðîèçâîëüíàÿ ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ
îãðàíè÷åííîãî, çàìêíóòîãî è âûïóêëîãî ïîäìíîæåñòâà K ïðîñòðàíñòâà Àäàìàðà
èìååò ïîäïîñëåäîâàòåëüíîñòü, ñëàáî ñõîäÿùóþñÿ ê ýëåìåíòó èç K [29, 31].
Ïðè äîêàçàòåëüñòâå ñëàáîé ñõîäèìîñòè ïîñëåäîâàòåëüíîñòåé ýëåìåíòîâ ìåò-
ðè÷åñêîãî ïðîñòðàíñòâà Àäàìàðà öåëåñîîáðàçíî èñïîëüçîâàòü èçâåñòíûé àíàëîã
ëåììû Îïÿëà [29, p. 60].
Ëåììà 1. Ïóñòü ïîñëåäîâàòåëüíîñòü ( )xn ýëåìåíòîâ ïðîñòðàíñòâà Àäàìàðà
( , )X d ñëàáî ñõîäèòñÿ ê ýëåìåíòó x X� . Òîãäà äëÿ âñåõ y X x� \ { } èìååì
lim ( , ) lim ( , )
n
n
n
nd x x d x y
�� ��
� .
Ïóñòü ( , )X d — ïðîñòðàíñòâî Àäàìàðà. Ôóíêöèÿ �: X � � � ��� � { } íà-
çûâàåòñÿ âûïóêëîé (ãåîäåçè÷åñêè âûïóêëîé), åñëè äëÿ âñåõ x , y X� è t �[ , ]0 1
âûïîëíÿåòñÿ óñëîâèå
�( ( ) )tx t y� �
1 t x t y� �( ) ( ) ( )� �1 .
Íàïðèìåð, â ïðîñòðàíñòâå Àäàìàðà ôóíêöèè y d y x� ( , ) âûïóêëû. Åñëè ñó-
ùåñòâóåò òàêàÿ êîíñòàíòà �� 0 , ÷òî äëÿ âñåõ x, y X� è t �[ , ]0 1 âûïîëíÿåòñÿ
óñëîâèå
�( ( ) )tx t y� �
1 t x t y t t d x y� � �( ) ( ) ( ) ( ) ( , )� � � �1 1 2 ,
òî ôóíêöèÿ � íàçûâàåòñÿ ñèëüíî âûïóêëîé. Èçâåñòíî, ÷òî äëÿ âûïóêëûõ
ôóíêöèé ïîëóíåïðåðûâíîñòü ñíèçó è ñëàáàÿ ïîëóíåïðåðûâíîñòü ñíèçó ýêâèâà-
ëåíòíû [29, p. 64], à ñèëüíî âûïóêëàÿ ïîëóíåïðåðûâíàÿ ñíèçó ôóíêöèÿ äîñòè-
ãàåò ìèíèìóìà â åäèíñòâåííîé òî÷êå.
Çàìå÷àíèå 2. Ìíîãèå âàæíûå äëÿ ïðèëîæåíèé êîíñòðóêöèè â ïðîñòðàí-
ñòâàõ Àäàìàðà ñâÿçàíû ñ òî÷êàìè ìèíèìóìà âûïóêëûõ ôóíêöèé [29, 32]. Íàïðè-
ìåð, äëÿ íàáîðà òî÷åê { }xi i m�1,
ìåòðè÷åñêîãî ïðîñòðàíñòâà ( , )X d ñ ïîëîæèòåëü-
íûìè âåñàìè { }� i i m�1,
áàðèöåíòðîì (öåíòðîì ìàññ, ñðåäíèì Ôðåøå) íàçûâàåòñÿ
òî÷êà
z d y xy X i
i
m
i� �
�
�arg min ( , )� 2
1
.
 ïðîñòðàíñòâå Àäàìàðà ôóíêöèè y d y xi�
2 ( , ) ñèëüíî âûïóêëû (ñì. íåðàâåí-
ñòâî (3)), ïîýòîìó ôóíêöèÿ y d y xi
i
m
i� � 2
1�
� ( , ) òàêæå ñèëüíî âûïóêëà. Îòñþäà
ñëåäóåò, ÷òî áàðèöåíòð ñóùåñòâóåò è åäèíñòâåíåí.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 139
Äëÿ âûïóêëîé, ñîáñòâåííîé è ïîëóíåïðåðûâíîé ñíèçó ôóíêöèè
�: X � � � ��� � { } ïðîêñèìàëüíûé îïåðàòîð îïðåäåëÿåòñÿ ñëåäóþùèì
îáðàçîì [29]:
prox arg� �x y d y xy X� ��min ( ( ) ( , ))
1
2
2 .
Ïîñêîëüêó ôóíêöèè � � �
1
2
2d x( , ) ñèëüíî âûïóêëû, òî îïðåäåëåíèå ïðîêñè-
ìàëüíîãî îïåðàòîðà êîððåêòíî, ò.å. äëÿ êàæäîãî x X� ñóùåñòâóåò åäèíñòâåí-
íûé ýëåìåíò prox � x X� .
Ïåðåéäåì ê ôîðìóëèðîâêå çàäà÷è î ðàâíîâåñèè â ïðîñòðàíñòâå Àäàìàðà.
ÇÀÄÀ×À Î ÐÀÂÍÎÂÅÑÈÈ Â ÌÅÒÐÈ×ÅÑÊÎÌ ÏÐÎÑÒÐÀÍÑÒÂÅ ÀÄÀÌÀÐÀ
Ïóñòü ( , )X d — ìåòðè÷åñêîå ïðîñòðàíñòâî Àäàìàðà. Äëÿ íåïóñòîãî âûïóêëîãî
çàìêíóòîãî ìíîæåñòâà Ñ X� è áèôóíêöèè F C C: � �� ðàññìîòðèì çàäà÷ó î
ðàâíîâåñèè (èëè çàäà÷ó ðàâíîâåñíîãî ïðîãðàììèðîâàíèÿ [2, 3, 9]):
íàéòè x Ñ� : F x y( , ) � 0 � �y Ñ. (4)
Ïðåäïîëîæèì, ÷òî âûïîëíåíû óñëîâèÿ:
1) F x x( , ) � 0 äëÿ âñåõ x Ñ� ;
2) ôóíêöèè F x C( , ):� �� âûïóêëû è ïîëóíåïðåðûâíû ñíèçó äëÿ âñåõ x C� ;
3) ôóíêöèè F y C( , ):� �� ñëàáî ïîëóíåïðåðûâíû ñâåðõó äëÿ âñåõ y C� ;
4) áèôóíêöèÿ F C C: � �� ïñåâäîìîíîòîííà, ò.å. äëÿ âñåõ x, y C� èç
F x y( , ) � 0 ñëåäóåò
F y x( , )
0 ;
5) áèôóíêöèÿ F C C: � �� ëèïøèöåâîãî òèïà, ò.å. ñóùåñòâóþò äâå êîíñòàí-
òû a � 0 , b� 0 òàêèå, ÷òî
F x y F x z F z y ad x z bd z y( , ) ( , ) ( , ) ( , ) ( , )
� � �2 2 � �x y z C, , . (5)
Çàìå÷àíèå 3. Óñëîâèå 5) ëèïøèöåâîãî òèïà â åâêëèäîâîì ïðîñòðàíñòâå ââå-
äåíî G. Mastroeni [4].
Ðàññìîòðèì äóàëüíóþ çàäà÷ó î ðàâíîâåñèè:
íàéòè x Ñ� : F y x( , )
0 � �y Ñ. (6)
Ìíîæåñòâà ðåøåíèé çàäà÷ (4) è (6) îáîçíà÷èì S è S * . Ïðè âûïîëíåíèè óñëî-
âèé 1) – 4) èìååì S S� * [12]. Êðîìå òîãî, ìíîæåñòâî S * âûïóêëî è çàìêíóòî.
Äàëåå áóäåì ïðåäïîëàãàòü, ÷òî S ��.
ÀÄÀÏÒÈÂÍÛÉ ÄÂÓÕÝÒÀÏÍÛÉ ÏÐÎÊÑÈÌÀËÜÍÛÉ ÀËÃÎÐÈÒÌ
 ñòàòüå [30] äëÿ ðåøåíèÿ çàäà÷è (4) áûë ïðåäëîæåí àëãîðèòì
y x F y y d yn F y n y C n
n
n n
� � �
� � � �prox arg�
�
( , ) min ( ( , ) ( ,
1 1
21
2
x
x x F y y d
n
n F y n y C n
n
n n
)),
min ( ( , )( , )� � �� � �1
21
2
prox arg�
�
( , )).y xn
�
��
�
�
�
(7)
Âåëè÷èíû � n � 0 çàäàâàëèñü, èñõîäÿ èç òðåáîâàíèÿ {inf sup }n n n n� �, �
�
�
�
�
��
�
�
0
1
2 2
,
( )a b
, ò.å. èñïîëüçîâàëàñü èíôîðìàöèÿ î êîíñòàíòàõ óñëîâèÿ òèïà
ëèïøèöåâîñòè áèôóíêöèè F .
140 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
Çàìå÷àíèå 4. Àëãîðèòì (7) äëÿ çàäà÷ â ãèëüáåðòîâîì ïðîñòðàíñòâå ïðåäëî-
æåí â ðàáîòå [9] (ñì. òàêæå [10, 27, 28]). ×àñòíûé ñëó÷àé àëãîðèòìà (7) äëÿ ïîèñ-
êà ñåäëîâûõ òî÷åê âûïóêëî-âîãíóòûõ ôóíêöèé, îïðåäåëåííûõ â êîíå÷íîìåðíîì
åâêëèäîâîì ïðîñòðàíñòâå, ïðåäëîæåí Ë.Ä. Ïîïîâûì [26]. Çàìåòèì, ÷òî â íàñòîÿ-
ùåå âðåìÿ âàðèàíò àëãîðèòìà (7) äëÿ âàðèàöèîííûõ íåðàâåíñòâ ñòàë óæå èçâå-
ñòåí ñïåöèàëèñòàìè ïî ìàøèííîìó îáó÷åíèþ ïîä íàçâàíèåì «Extrapolation from
the Past» [33].
Íà îñíîâàíèè èòåðàöèîííîé ñõåìû (7) è ðàáîòû [18] ïîñòðîèì äâóõýòàïíûé
ïðîêñèìàëüíûé àëãîðèòì ñ àäàïòèâíûì âûáîðîì âåëè÷èíû � n .
Àëãîðèòì 1
Èíèöèàëèçàöèÿ. Âûáèðàåì ýëåìåíò x1, y C0 � , � �
�
�
�
�
�
0
1
3
, , �1 0� ��( , ) . Ïî-
ëàãàåì n �1.
Øàã 1. Âû÷èñëèòü
y x F y y d yn F y n y C n
n
n n
� � �
� � � �prox arg�
�
( , ) min ( ( , ) ( ,
1 1
21
2
xn )) .
Øàã 2. Âû÷èñëèòü
x x F y y d y xn F y n y C n
n
nn n� � �� � �1
21
2
prox arg�
�
( , ) min ( ( , ) ( , )) .
Åñëè x x yn n n� � �1 , òî îñòàíîâèòü è x Sn � . Èíà÷å ïåðåéòè íà øàã 3.
Øàã 3. Âû÷èñëèòü
�
�
n
n n n n n n nF y x F y y F y x
�
� � � �
�
� �
1
1 1 1 1 0, ( , ) ( , ) ( , ) ,
m
åñëè
in ,
( , ) ( , )
( ( , ) (
�
�
n
n n n n
n n n
d y y d x y
F y x F y2
2
1
2
1
1 1 1
� �
� � �
�
� , ) ( , ))y F y xn n n�
�
�
��
!
"
�
#�
�
�
�
�
�1
èíà å.�
Ïîëîæèòü n n:� �1 è ïåðåéòè íà øàã 1.
Çàìå÷àíèå 5. Íà êàæäîì øàãå àëãîðèòìà 1 ñëåäóåò ðåøèòü äâå âûïóêëûå
çàäà÷è ñ ñèëüíî âûïóêëûìè ôóíêöèÿìè. Áóäåì ïðåäïîëàãàòü âîçìîæíîñòü èõ
ýôôåêòèâíîãî ðåøåíèÿ.
 ïðåäëàãàåìîì àëãîðèòìå ïàðàìåòð � n�1 çàâèñèò îò ðàñïîëîæåíèÿ òî÷åê
yn�1, yn , xn�1, çíà÷åíèé F y xn n( , )� �1 1 , F y yn n( , )�1 è F y xn n( , )�1 . Íèêàêàÿ èí-
ôîðìàöèÿ î êîíñòàíòàõ a è b èç íåðàâåíñòâà (5) íå èñïîëüçóåòñÿ â àëãîðèòìå.
Î÷åâèäíî, ÷òî ïîñëåäîâàòåëüíîñòü ( )� n ÿâëÿåòñÿ íåóáûâàþùåé è îãðàíè÷åííîé
ñíèçó ÷èñëîì min ,
max ,
�
�
1
2 { }a b
�
�
!
"
#
. Äåéñòâèòåëüíî, èìååì
F y x F y y F y xn n n n n n( , ) ( , ) ( , )� � � �� �
1 1 1 1
�
�� � �ad y y bd y x a b d y y dn n n n n n
2
1
2
1
2
1
2( , ) ( , ) max , ( ( , ){ } ( , ))y xn n�1 .
Çàìå÷àíèå 6. Îáîñíîâàíèå ïðàâèëà îñòàíîâêè â àëãîðèòìå 1 ïðèâåäåíî
íèæå (ñì. (12)).
Ïåðåéäåì ê îáîñíîâàíèþ ñõîäèìîñòè àëãîðèòìà 1.
ÑÕÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÀ
Âíà÷àëå ñôîðìóëèðóåì âàæíîå íåðàâåíñòâî.
Ëåììà 2. Äëÿ x, z Ñ� è x xF z
�
�� prox � ( , ) , ãäå � � 0 , èìååò ìåñòî íåðàâåí-
ñòâî
F z x F z y( , ) ( , )� �
1
2
2 2 2
�
( ( , ) ( , ) ( , ))d y x d x x d x y� �� � � �y Ñ. (8)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 141
Äîêàçàòåëüñòâî. Èç îïðåäåëåíèÿ x F z y d y xy C
�
�� �arg min ( ( , ) ( , ))
1
2
2
�ñëåäóåò
F z x d x x F z p d p x( , ) ( , ) ( , ) ( , )� ��
�
1
2
1
2
2 2
� �
� �p Ñ. (9)
Ïîëîæèâ â (9) p tx t y� � �� ( )1 , y Ñ� , t �( , )0 1 , ïîëó÷èì
F z x d x x F z tx t y d tx t( , ) ( , ) ( , ( ) ) ( (� � � ��
� � � � �
1
2
1
1
2
12 2
� �
) , )y x
� � ��tF z x t F z y( , ) ( ) ( , )1
1
2
1 12 2 2
�
( ( , ) ( ) ( , ) ( ) ( , ))td x x t d y x t t d x y� �� � � � .
Òàêèì îáðàçîì,
( ) ( , ) ( ) ( , )1 1� � ��t F z x t F z y
1
2
1 1 12 2 2
�
( ( ) ( , ) ( ) ( , ) ( ) ( , ))� � � � � �� �t d x x t d y x t t d x y . (10)
Ñîêðàòèâ â (10) 1� t è ñîâåðøèâ ïðåäåëüíûé ïåðåõîä ïðè t �1, ïîëó÷èì (8). �
Èç ëåììû 2 ñëåäóåò, ÷òî äëÿ ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn , ïîðîæäåííûõ
àëãîðèòìîì 1, èìåþò ìåñòî íåðàâåíñòâà
F y y F y yn n n( , ) ( , )� ��
1 1
(11)
� �
1
2
2 2 2
� n
n n n nd y x d x y d y y( ( , ) ( , ) ( , )) � �y Ñ,
F y x F y yn n n( , ) ( , )� �
1
(12)
� �� �
1
2
2 2
1
2
1
� n
n n n nd y x d x x d x y( ( , ) ( , ) ( , )) � �y Ñ.
Èç íåðàâåíñòâà (12) ñëåäóåò îáîñíîâàíèå ïðàâèëà îñòàíîâêè àëãîðèòìà 1.
Äåéñòâèòåëüíî, ïðè x x yn n n� � �1 èç (12) âûòåêàåò �
F y yn( , ) 0 � �y Ñ, ò.å.
x y Sn n� � .
Çàìå÷àíèå 7. Äëÿ îñòàíîâêè àëãîðèòìà 1 ìîæíî èñïîëüçîâàòü ïðàâèëî
x y yn n n� � �1, ãàðàíòèðóþùåå x Sn � .
Äîêàæåì îñíîâíóþ îöåíêó, ñâÿçûâàþùóþ ðàññòîÿíèÿ ìåæäó ïîðîæäåííû-
ìè àëãîðèòìîì 1 òî÷êàìè è ïðîèçâîëüíûì ýëåìåíòîì ìíîæåñòâà ðåøåíèé S .
Ëåììà 3. Äëÿ ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn , ïîðîæäåííûõ àëãîðèòìîì 1,
èìååò ìåñòî íåðàâåíñòâî
d x z d x z d x yn n
n
n
n n
2
1
2
1
2
11( , ) ( , ) ( , )�
�
�
� �
�
�
��
�
�
��
�
� (13)
� �
�
�
��
�
�
�
� �
�1 2 2
1
2
1
2
1�
�
�
�
�
�
n
n
n n
n
n
n nd y x d x y( , ) ( , ) ,
ãäå z S� .
Äîêàçàòåëüñòâî. Ïóñòü z S� . Èç ïñåâäîìîíîòîííîñòè áèôóíêöèè F ñëåäóåò
F y zn( , )
0 . (14)
Èç (14) è (12) ñëåäóåò
2 1� n n nF y x( , )�
d z x d x x d x zn n n n
2 2
1
2
1( , ) ( , ) ( , )� �� � . (15)
Ñóììèðóÿ íåðàâåíñòâî (15) è íåðàâåíñòâî
2 1 1 1� n n n n nF y y F y x( ( , ) ( , ))� � ��
d x x d x y d y xn n n n n n
2
1
2 2
1( , ) ( , ) ( , )� �� � ,
142 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
êîòîðîå âûòåêàåò èç (11), ïîëó÷àåì
2 1 1 1 1� n n n n n n nF y x F y y F y x( ( , ) ( , ) ( , ))� � � �� �
(16)
� � �� �d z x d x z d y x d x yn n n n n n
2 2
1
2 2
1( , ) ( , ) ( , ) ( , ) .
Èç ïðàâèëà âû÷èñëåíèÿ � n�1 ñëåäóåò íåðàâåíñòâî
F y x F y y F y xn n n n n n( , ) ( , ) ( , )� � � �� �
1 1 1 1
(17)
�
�
� �
�
�2 1
2
1
2
1
n
n n n nd y y d x y( ( , ) ( , )) .
Äëÿ îöåíêè âûðàæåíèÿ F y x F y y F y xn n n n n n( , ) ( , ) ( , )� � � �� �1 1 1 1 â (17) âîñ-
ïîëüçóåìñÿ (16). Ïîëó÷èì
d x z d z x d y x d x yn n n n n n
2
1
2 2 2
1( , ) ( , ) ( , ) ( , )� �
� � �
� �
�
� ��
�
�
n
n
n n n nd y y d x y
1
2
1
2
1( ( , ) ( , )) .
Ïîñêîëüêó d y y d y x d x yn n n n n n
2
1
2
1
22 2( , ) ( , ) ( , )� �
� , òî
d x z d z x d y x d x yn n n n n n
2
1
2 2 2
1( , ) ( , ) ( , ) ( , )� �
� � �
� � �
�
�
� �
2 2
1
2
1
1
2
1
2�
�
�
�
�
�
�
�
�
n
n
n n
n
n
n n
n
n
d y x d x y d x( , ) ( , ) ( n ny�1, ) ,
÷òî è òðåáîâàëîñü äîêàçàòü. �
Äëÿ äîêàçàòåëüñòâà ñõîäèìîñòè àëãîðèòìà 1 èñïîëüçóåì ýëåìåíòàðíóþ ëåì-
ìó î ÷èñëîâûõ ïîñëåäîâàòåëüíîñòÿõ.
Ëåììà 4. Ïóñòü ( )an , ( )bn — äâå ïîñëåäîâàòåëüíîñòè íåîòðèöàòåëüíûõ ÷è-
ñåë, óäîâëåòâîðÿþùèõ íåðàâåíñòâó a a bn n n�
�1 äëÿ âñåõ n�� . Òîãäà ñóùå-
ñòâóåò ïðåäåë lim
n
na
��
è ( )bn �� 1.
Ñôîðìóëèðóåì îäèí èç îñíîâíûõ ðåçóëüòàòîâ ðàáîòû.
Òåîðåìà 1. Ïóñòü ( , )X d — ïðîñòðàíñòâî Àäàìàðà, C X� — íåïóñòîå âû-
ïóêëîå çàìêíóòîå ìíîæåñòâî, äëÿ áèôóíêöèè F C C: � �� âûïîëíåíû óñëî-
âèÿ 1) – 5) è S �� . Òîãäà ïîðîæäåííûå àëãîðèòìîì 1 ïîñëåäîâàòåëüíîñòè ( )xn ,
( )yn ñëàáî ñõîäÿòñÿ ê ðåøåíèþ z S� çàäà÷è î ðàâíîâåñèè (4), ïðè÷åì
lim ( , ) lim ( , )
n
n n
n
n nd y x d y x
�� ��
�� �1 0.
Äîêàçàòåëüñòâî. Ïóñòü z S$� . Ïîëîæèì
a d x z d x yn n
n
n
n n� $ �
�
�
2
1
2
12( , ) ( , )�
�
�
,
b d y xn
n
n
n n
n
n
n
n
� �
�
�
��
�
�
� � �
�
�
� �
1 2 1 2
1
2 1
2
�
�
�
�
�
�
�
�
�
( , )
1
2
1
�
�
��
�
�
�d x yn n( , ) .
Íåðàâåíñòâî (13) ïðèíèìàåò âèä
a a bn n n�
�1 .
Ïîñêîëüêó ñóùåñòâóåò lim
n
n
��
�� 0 , òî
1 2
1
�
�
�
�
�
n
n
� �1 2� �( , )0 1 è 1 2 1 3 0 11
2 1
� � � � ��
� �
�
�
�
�
�
�
�n
n
n
n
( , ) ïðè n � �.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 143
Èç ëåììû 4 çàêëþ÷àåì, ÷òî ñóùåñòâóåò ïðåäåë
lim ( , ) ( , )
n
n
n
n
n nd x z d x y
�� �
�$ �
�
�
��
�
�
2
1
2
12�
�
�
è
1 2 1 2
1
2 1
2 1
�
�
�
��
�
�
� � �
�
��
�
� �
�
�
�
�
�
�
�
�
�
n
n
n n
n
n
n
n
d y x( , ) ��
�
�
�
�
�
�
�
�
� ���
�
�
� d x yn n
n
2
1
1
( , ) .
Îòñþäà ïîëó÷àåì
lim ( , ) lim ( , ) lim ( , )
n
n n
n
n n
n
n nd y x d x y d x x
�� ��
�
��
�� � �1 1 0 (18)
è ñõîäèìîñòü ÷èñëîâûõ ïîñëåäîâàòåëüíîñòåé ( ( , ))d x zn $ , ( ( , ))d y zn $ äëÿ âñåõ
z S$� .  ÷àñòíîñòè, ïîñëåäîâàòåëüíîñòè ( )xn , ( )yn îãðàíè÷åíû.
Ðàññìîòðèì ïîäïîñëåäîâàòåëüíîñòü ( )xnk
, ñëàáî ñõîäÿùóþñÿ ê íåêîòîðîé
òî÷êå z C� . Òîãäà èç (18) ñëåäóåò, ÷òî ( )ynk�1 ñëàáî ñõîäèòñÿ ê z. Ïîêàæåì, ÷òî
z S� . Èç (12) ñëåäóåò
F y y F y xn n nk k k
( , ) ( , )� �� �1 1
� � �
�
��
1
2 1
2 2 2
11� n
n n n n
k
k k k k
d x x d x y d x y( ( , ) ( , ) ( , )) � �y C. (19)
Âîñïîëüçóåìñÿ íåðàâåíñòâîì (17) äëÿ îöåíêè ñíèçó ÷ëåíà F y xn nk k
( , )�1 â (19).
Ïîëó÷èì
F y y F y x F y yn n n n nk k k k k
( , ) ( , ) ( , )� � � �� � �1 2 2 1
� � � �
�
��
1
2 1
2 2 2
11� n
n n n n
k
k k k k
d x x d x y d x y( ( , ) ( , ) ( , )) (20)
� �� � �
�
�2
2
2 1
2
1
n
n n n n
k
k k k k
d y y d x y( ( , ) ( , )) .
Ðàçíîñòü F y x F y yn n n nk k k k
( , ) ( , )� � ��2 2 1 îöåíèì ñíèçó ñ ïîìîùüþ (11). Èìååì
F y x F y yn n n nk k k
( , ) ( , )� � �� �2 2 1
(21)
� � �
�
� � � �
1
2 1
2
1 1
2
1
2
� n
n n n n n n
k
k k k k k k
d x y d y x d x x( ( , ) ( , ) ( , 1 )) .
Êîìáèíèðóÿ (20) è (21), ïîëó÷àåì
F y y d x y d y x dn
n
n n n nk
k
k k k k
( , ) ( ( , ) ( , )�
�
� � �� � �1
1
2
1 1
2
1
1
2�
2
1( , ))x xn nk k�
�
� � � �
�
��
1
2 1
2 2 2
11� n
n n n n
k
k k k k
d x x d x y d x y( ( , ) ( , ) ( , ))
(22)
� �� � �
�
�2
2
2 1
2
1
n
n n n n
k
k k k k
d y y d x y( ( , ) ( , )) � �y C.
Ñîâåðøèâ ïðåäåëüíûé ïåðåõîä â (22) ñ ó÷åòîì (18) è ñëàáîé ïîëóíåïðåðûâ-
íîñòè ñâåðõó ôóíêöèè F y C( , ):� �� , ïîëó÷èì
F z y F y y
k
nk
( , ) lim ( , )� �
��
�1 0 � �y Ñ,
ò.å. z S� .
144 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
Ïðèìåíÿÿ âàðèàíò ëåììû Îïÿëà äëÿ ìåòðè÷åñêèõ ïðîñòðàíñòâ Àäàìàðà
(ëåììà 1), ïîëó÷àåì ñëàáóþ ñõîäèìîñòü ïîñëåäîâàòåëüíîñòè ( )xn ê òî÷êå z S� .
Ðàññóæäàåì îò ïðîòèâíîãî. Ïóñòü ñóùåñòâóåò ïîäïîñëåäîâàòåëüíîñòü ( )xmk
,
ñëàáî ñõîäÿùàÿñÿ ê íåêîòîðîé òî÷êå z C� è z z� . Î÷åâèäíî, ÷òî z S� . Äàëåå,
èìååì
lim ( , ) lim ( , ) lim ( , ) lim
n
n
k
n
k
n
n
d x z d x z d x z
k k�� �� �� ��
� � � d x z d x zn
k
mk
( , ) lim ( , )� �
��
� �
�� ��
lim ( , ) lim ( , )
k
m
n
nd x z d x z
k
,
÷òî íåâîçìîæíî. Ñëåäîâàòåëüíî, ( )xn ñëàáî ñõîäèòñÿ ê z S� . Èç (18) ñëåäóåò,
÷òî è ïîñëåäîâàòåëüíîñòü ( )yn ñëàáî ñõîäèòñÿ ê z S� . �
ÂÀÐÈÀÍÒ ÀÄÀÏÒÈÂÍÎÃÎ ÀËÃÎÐÈÒÌÀ ÄËß ÂÀÐÈÀÖÈÎÍÍÛÕ ÍÅÐÀÂÅÍÑÒÂ
Ðàññìîòðèì ÷àñòíûé ñëó÷àé çàäà÷è î ðàâíîâåñèè: âàðèàöèîííîå íåðàâåíñòâî â
ãèëüáåðòîâîì ïðîñòðàíñòâå H [14]:
íàéòè x Ñ� : ( , )Ax y x� � 0 � �y Ñ. (23)
Ïðåäïîëîæèì, ÷òî âûïîëíåíû ñëåäóþùèå óñëîâèÿ: ìíîæåñòâî C H� — âû-
ïóêëîå è çàìêíóòîå; îïåðàòîð A C H: � — ïñåâäîìîíîòîííûé, ëèïøèöåâûé è ñåê-
âåíöèàëüíî ñëàáî íåïðåðûâíûé; ìíîæåñòâî ðåøåíèé (23) íå ïóñòî. Ïóñòü PC —
îïåðàòîð ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ íà âûïóêëîå çàìêíóòîå ìíîæåñòâî C, ò.å.
P xC — åäèíñòâåííûé ýëåìåíò ìíîæåñòâà C ñî ñâîéñòâîì || || min || ||P x x z xC
z C
� � �
�
.
Äëÿ âàðèàöèîííûõ íåðàâåíñòâ (23) àëãîðèòì 1 ïðèíèìàåò ñëåäóþùèé âèä.
Àëãîðèòì 2
Èíèöèàëèçàöèÿ. Âûáèðàåì ýëåìåíò x1, y C0 � , � �
�
�
�
�
�
0
1
3
, , �1 0� ��( , ). Ïî-
ëàãàåì n �1 .
Øàã 1. Âû÷èñëèòü
y P x Ayn C n n n� � �( )� 1 .
Øàã 2. Âû÷èñëèòü
x P x Ayn C n n n� � �1 ( )� .
Åñëè x x yn n n� � �1 , òî îñòàíîâèòü è xn åñòü ðåøåíèå. Èíà÷å ïåðåéòè íà øàã 3.
Øàã 3. Âû÷èñëèòü
�
�
�
�n
n n n n n
n
n
Ay Ay x y
y y�
� �
��
� �
�1
1 1
1
0
2
, ( , ) ,
min ,
||
åñëè
n n n
n n n n
x y
Ay Ay x y
|| || ||
( , )
2
1
2
1 1
� �
� �
�
�
��
!
"
�
#�
�
� �
èíà�å.
�
�
�
�
Ïîëîæèòü n n:� �1 è ïåðåéòè íà øàã 1.
Èç òåîðåìû 1 âûòåêàåò ñëåäóþùèé ðåçóëüòàò.
Òåîðåìà 2. Ïóñòü H — ãèëüáåðòîâî ïðîñòðàíñòâî, C X� — íåïóñòîå âûïóê-
ëîå çàìêíóòîå ìíîæåñòâî, îïåðàòîð A C H: � ïñåâäîìîíîòîííûé, ëèïøèöåâûé,
ñåêâåíöèàëüíî ñëàáî íåïðåðûâíûé è ñóùåñòâóþò ðåøåíèÿ (23). Òîãäà ïîðîæäåí-
íûå àëãîðèòìîì 2 ïîñëåäîâàòåëüíîñòè ( )xn , ( )yn ñëàáî ñõîäÿòñÿ ê ðåøåíèþ âàðè-
àöèîííîãî íåðàâåíñòâà (23), ïðè÷åì lim || || lim || ||
n
n n
n
n ny x y x
�� ��
�� � � �1 0 .
Çàìå÷àíèå 8. Åñëè îïåðàòîð A ìîíîòîííûé, òî ðåçóëüòàò òåîðåìû 2 ñïðàâåä-
ëèâ áåç ïðåäïîëîæåíèÿ î ñåêâåíöèàëüíîé ñëàáîé íåïðåðûâíîñòè îïåðàòîðà A.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 145
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå â ïðîäîëæåíèå ðàáîò [18, 30] ðàññìîòðåí íîâûé àäàïòèâ-
íûé äâóõýòàïíûé ïðîêñèìàëüíûé àëãîðèòì äëÿ ïðèáëèæåííîãî ðåøåíèÿ çàäà÷
î ðàâíîâåñèè â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ Àäàìàðà. Àëãîðèòì èìååò ñòðóêòóðó
y x F y y d yn F y n y C n
n
n n
� � �
� � � �prox arg�
�
( , ) min ( ( , ) ( ,
1 1
21
2
x
x x F y y d
n
n F y n y C n
n
n n
)),
min ( ( , )( , )� � �� � �1
21
2
prox arg�
�
( , )),y xn
�
��
�
�
�
ãäå � n � 0 âûáèðàåòñÿ àäàïòèâíî.  îòëè÷èå îò ïðèìåíÿåìûõ ðàíåå ïðàâèë
âûáîðà âåëè÷èíû øàãà [9, 10, 27, 28, 30] â ïðåäëàãàåìîì àëãîðèòìå íå ïðîâî-
äèòñÿ âû÷èñëåíèé çíà÷åíèé áèôóíêöèè â äîïîëíèòåëüíûõ òî÷êàõ è íå òðåáó-
åòñÿ çíàíèÿ ëèïøèöåâûõ êîíñòàíò áèôóíêöèè. Äëÿ ïñåâäîìîíîòîííûõ
áèôóíêöèé ëèïøèöåâîãî òèïà äîêàçàíà òåîðåìà î ñëàáîé ñõîäèìîñòè ïîðîæ-
äåííûõ àëãîðèòìîì ïîñëåäîâàòåëüíîñòåé. Äîêàçàòåëüñòâî îñíîâàíî íà èñïîëü-
çîâàíèè ìîäèôèöèðîâàííîé îöåíêè èç ðàáîòû [30]. Ïîêàçàíî, ÷òî ïðåäëîæåí-
íûé àëãîðèòì ïðèìåíèì ê ïñåâäîìîíîòîííûì âàðèàöèîííûì íåðàâåíñòâàì
â ãèëüáåðòîâûõ ïðîñòðàíñòâàõ.
Àâòîðû ïëàíèðóþò ðàññìîòðåòü áîëåå ñïåöèàëüíûé âàðèàíò àäàïòèâíîãî
äâóõýòàïíîãî ïðîêñèìàëüíîãî àëãîðèòìà äëÿ âàðèàöèîííûõ íåðàâåíñòâ è ìèíè-
ìàêñíûõ çàäà÷ íà ìíîãîîáðàçèÿõ Àäàìàðà (íàïðèìåð, íà ìíîãîîáðàçèè ñèììåò-
ðè÷íûõ ïîëîæèòåëüíî îïðåäåëåííûõ ìàòðèö). Òàêæå ïðåäñòàâëÿåò èíòåðåñ
ïîñòðîåíèå ðàíäîìèçèðîâàíííûõ àäàïòèâíûé âåðñèé àëãîðèòìîâ.
Â.Â. Ñåìåíîâ âûðàæàåò áëàãîäàðíîñòü ïðîôåññîðó Þ.Â. Ìàëèöêîìó çà çà-
ìå÷àíèÿ îòíîñèòåëüíî ïîäõîäîâ ê ïîñòðîåíèþ àäàïòèâíûõ àëãîðèòìîâ îïòèìè-
çàöèè ïåðâîãî ïîðÿäêà è ðóêîâîäèòåëþ êîìïàíèè ËÓÍ Àíäðåþ Ìèìå çà ïîä-
äåðæêó èññëåäîâàíèé íà ôàêóëüòåòå êîìïüþòåðíûõ íàóê è êèáåðíåòèêè
Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Kassay G., Radulescu V.D. Equilibrium problems and applications. London: Academic Press, 2019.
xx+419 p.
2. Combettes P.L., Hirstoaga S.A. Equilibrium programming in Hilbert spaces. J. Nonlinear Convex
Anal. 2005. Vol. 6. P. 117–136.
3. Antipin A.S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997.
Vol. 37. P. 1285–1296. https://doi.org/10.1134/S0965542507120044.
4. Mastroeni G. On auxiliary principle for equilibrium problems. In: Daniele P. et al. (Eds.).
Equilibrium problems and variational models. Dordrecht: Kluwer Academic Publishers, 2003.
P. 289–298. https://doi.org/10.1007/978-1-4613-0239-1.
5. Quoc T.D., Muu L.D., Hien N.V. Extragradient algorithms extended to equilibrium problems.
Optimization. 2008. Vol. 57. P. 749–776. https://doi.org/10.1080/02331930601122876.
6. Semenov V.V. On the parallel proximal decomposition method for solving the problems of convex
optimization. Journal of Automation and Information Sciences. 2010. Vol. 42, Iss. 4. P. 13–18.
https://doi.org/10.1615/JAutomatInfScien.v42.i4.20.
7. Lyashko S.I., Semenov V.V., Voitova T.A. Low-cost modification of Korpelevich’s methods for
monotone equilibrium problems. Cybernetics and Systems Analysis. 2011. Vol. 47, N 4. P. 631–639.
https://doi.org/10.1007/s10559-011-9343-1.
8. Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of
solutions the equilibrium problems. In: Zgurovsky M.Z. and Sadovnichiy V.A. (Eds.). Continuous
and Distributed Systems. Solid Mechanics and Its Applications. Vol. 211. Springer International
Publishing Switzerland, 2014. P. 131–146. URL: https://doi.org/10.1007/978-3-319-03146-0_10.
146 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
9. Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of
equilibrium programming. In: Goldengorin B. (Ed.). Optimization and Its Applications in Control
and Data Sciences. Springer Optimization and Its Applications. Vol. 115. Cham: Springer, 2016.
P. 315–325. https://doi.org/10.1007/978-3-319-42056-1_10.
10. Chabak L., Semenov V., Vedel Y. A new non-euclidean proximal method for equilibrium problems.
In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (Eds.).
Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018.
Advances in Intelligent Systems and Computing. Vol. 836. Cham: Springer, 2019. P. 50–58.
https://doi.org/10.1007/978-3-319-97885-7_6.
11. Colao V., Lopez G., Marino G., Martin-Marquez V. Equilibrium problems in Hadamard manifolds.
Journal of Mathematical Analysis and Applications. 2012. Vol. 388. P. 61–77. https://doi.org/
10.1016/j.jmaa.2011.11.001.
12. Khatibzadeh H., Mohebbi V. Monotone and pseudo-monotone equilibrium problems in Hadamard
spaces. Journal of the Australian Mathematical Society. 2019. P. 1–23. https://doi.org/
10.1017/S1446788719000041.
13. Khatibzadeh H., Mohebbi V. Approximating solutions of equilibrium problems in Hadamard spaces.
Miskolc Mathematical Notes. 2019. Vol. 20, N 1. P. 281–297. https://doi.org/10.18514/MMN.2019.2361.
14. Kinderlehrer D., Stampacchia G. An introduction to variational inequalities and their applications.
New York: Academic Press, 1980. Russian transl., Moscow: Mir, 1983. 256 p.
15. Sandrakov G.V. Homogenization of variational inequalities for non-linear diffusion problems in
perforated domains. Izvestiya Mathematics. 2005. Vol. 69, Iss. 5. P. 1035–1059. http://dx.doi.org/
10.1070/IM2005v069n05ABEH002287.
16. Korpelevich G.M. An extragradient method for finding saddle points and for other problems.
Matecon. 1976. Vol. 12, N 4. P. 747–756.
17. 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
J. Optim. 2004. Vol. 15, Iss. 1. P. 229–251. https://doi.org/10.1137/S1052623403425629.
18. Denisov S.V., Semenov V.V., Stetsyuk P.I. Bregman extragradient method with monotone rule of
step adjustment. Cybernetics and Systems Analysis. 2019. Vol. 55, N 3. P. 377–383. https://doi.org/
10.1007/s10559-019-00144-5.
19. Stonyakin F.S. On the adaptive proximal method for a class of variational inequalities and related
problems. Trudy Inst. Mat. i Mekh. UrO RAN. 2019. Vol. 25, N 2. P. 185–197. https://doi.org/
10.21538/0134-4889-2019-25-2-185-197.
20. Stonyakin F.S., Vorontsova E.A., Alkousa M.S. New version of mirror prox for variational
inequalities with adaptation to inexactness. In: Jac$imovic$ M., Khachay M., Malkova V.,
Posypkin M. (Eds.). Optimization and Applications. OPTIMA 2019. Communications in Computer
and Information Science. Vol 1145. Cham: Springer, 2020. P. 427–442. https://doi.org/10.1007/
978-3-030-38603-0_31.
21. Semenov V.V. A strongly convergent splitting method for systems of operator inclusions with
monotone operators. Journal of Automation and Information Sciences. 2014. Vol. 46, Iss. 5.
P. 45–56. https://doi.org/10.1615/JAutomatInfScien.v46.i5.40.
22. Semenov V.V. Hybrid splitting methods for the system of operator inclusions with monotone
operators. Cybernetics and Systems Analysis. 2014. Vol. 50, N 5. P. 741–749. https://doi.org/
10.1007/s10559-014-9664-y.
23. Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for
variational inequalities with non-Lipschitz operators. Journal of Automation and Information
Sciences. 2015. Vol. 47, Iss. 7. P. 31–46. https://doi.org/10.1615/JAutomatInfScien.v47.i7.40.
24. Semenov V.V. Modified extragradient method with Bregman divergence for variational inequalities.
Journal of Automation and Information Sciences. 2018. Vol. 50, Iss. 8. P. 26–37. https://doi.org/
10.1615/JAutomatInfScien.v50.i8.30.
25. Denisov S.V., Nomirovskii D.A., Rublyov B.V., Semenov V.V. Convergence of extragradient
algorithm with monotone step size strategy for variational inequalities and operator equations.
Journal of Automation and Information Sciences. 2019. Vol. 51, Iss. 6. P. 12–24. https://doi.org/
10.1615/JAutomatInfScien.v51.i6.20.
26. Popov L.D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical
notes of the Academy of Sciences of the USSR. 1980. Vol, 28. Iss. 5. P. 845–848. https://doi.org/
10.1007/BF01141092.
27. Semenov V.V. A version of the mirror descent method to solve variational inequalities. Cybernetics
and Systems Analysis. 2017. Vol. 53, N 2. P. 234–243. https://doi.org/10.1007/s10559-017-9923-9.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 147
28. Nomirovskii D.A., Rublyov B.V., Semenov V.V. Convergence of two-stage method with Bregman
divergence for solving variational inequalities. Cybernetics and Systems Analysis. 2019. Vol. 55,
N 3. P. 359–368. https://doi.org/10.1007/s10559-019-00142-7.
29. Bacak M. Convex analysis and optimization in Hadamard spaces. Berlin; Boston: De Gruyter, 2014.
viii+185 p.
30. Âåäåëü ß.È., Ñàíäðàêîâ Ã.Â., Ñåìåíîâ Â.Â., ×àáàê Ë.Ì. Ñõîäèìîñòü äâóõýòàïíîãî ïðîêñè-
ìàëüíîãî àëãîðèòìà äëÿ çàäà÷è î ðàâíîâåñèè â ïðîñòðàíñòâàõ Àäàìàðà. Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. 2020. T. 56, ¹ 5. Ñ. 115–125.
31. Kirk W., Shahzad N. Fixed point theory in distance spaces. Cham: Springer, 2014. xii+173 p.
https://doi.org/10.1007/978-3-319-10927-5.
32. Burago D., Burago Yu., Ivanov S. A course in metric geometry. Graduate Studies in Mathematics.
Vol. 33. Providence: AMS, 2001. xiv+415 p.
33. Gidel G., Berard H., Vincent P., Lacoste-Julien S. A variational inequality perspective on generative
adversarial networks. arXiv preprint arXiv:1802.10551. 2018.
Íàäiéøëà äî ðåäàêö³¿ 22.01.2020
ß.². Âåäåëü, Ã.Â. Ñàíäðàêîâ, Â.Â. Ñåìåíîâ
ÀÄÀÏÒÈÂÍÈÉ ÄÂÎÅÒÀÏÍÈÉ ÏÐÎÊÑÈÌÀËÜÍÈÉ ÀËÃÎÐÈÒÌ ÄËß ÇÀÄÀײ
ÏÐΠвÂÍÎÂÀÃÓ Â ÏÐÎÑÒÎÐÀÕ ÀÄÀÌÀÐÀ
Àíîòàö³ÿ. Pîçãëÿíóòî çàäà÷³ ïðî ð³âíîâàãó â ìåòðè÷íèõ ïðîñòîðàõ Àäàìàðà.
Äëÿ íàáëèæåíîãî ðîçâ’ÿçàííÿ çàäà÷ çàïðîïîíîâàíî òà äîñë³äæåíî íîâèé ³òå-
ðàö³éíèé àäàïòèâíèé äâîåòàïíèé ïðîêñèìàëüíèé àëãîðèòì. Íà â³äì³íó â³ä
ïðàâèë âèáîðó âåëè÷èíè êðîêó, ùî çàñòîñîâóâàëèñÿ ðàí³øå, â çàïðîïîíîâà-
íîìó àëãîðèòì³ íå âèêîíóþòüñÿ îá÷èñëåííÿ çíà÷åíü á³ôóíêö³¿ â äîäàòêîâèõ
òî÷êàõ, à òàêîæ çíàííÿ ³íôîðìàö³¿ ïðî âåëè÷èíó ë³ïøèöåâèõ êîíñòàíò
á³ôóíêö³¿ íå ïîòð³áíî. Äëÿ ïñåâäîìîíîòîííèõ á³ôóíêö³é ë³ïøèöåâîãî òèïó
äîâåäåíî òåîðåìó ïðî ñëàáêó çá³æí³ñòü ïîðîäæåíèõ àëãîðèòìîì ïîñë³äîâ-
íîñòåé. Çàïðîïîíîâàíèé àëãîðèòì ìîæíà çàñòîñóâàòè äî ïñåâäîìîíîòîííèõ
âàð³àö³éíèõ íåð³âíîñòåé ó ã³ëüáåðòîâèõ ïðîñòîðàõ.
Êëþ÷îâi ñëîâà: ïðîñò³ð Àäàìàðà, çàäà÷à ïðî ð³âíîâàãó, ïñåâäîìîíî-
òîíí³ñòü, äâîåòàïíèé ïðîêñèìàëüíèé àëãîðèòì, àäàïòèâí³ñòü, çá³æí³ñòü.
Ya.I. Vedel, G.V. Sandrakov, V.V. Semenov
AN ADAPTIVE TWO-STAGE PROXIMAL ALGORITHM FOR EQUILIBRIUM PROBLEMS
IN HADAMARD SPACES
Abstract. Equilibrium problems in Hadamard metric spaces are considered in the
paper. For an approximate solution of problems, a new iterative adaptive
two-stage proximal algorithm is proposed and analyzed. In contrast to the
previously used rules for choosing the step size, the proposed algorithm does not
calculate bifunction values at additional points and does not require knowledge of
the value of bifunction’s Lipschitz constants. For pseudo-monotone bifunctions of
Lipschitz type, the theorem on weak convergence of the sequences generated by
the algorithm is proved. It is shown that the proposed algorithm is applicable to
pseudo-monotone variational inequalities in Hilbert spaces.
Keywords: Hadamard space, equilibrium problem, pseudo-monotonicity,
two-stage proximal algorithm, adaptivity, convergence.
Âåäåëü ßíà Èãîðåâíà,
àñïèðàíòêà Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: yana.vedel@gmail.com.
Ñàíäðàêîâ Ãåííàäèé Âèêòîðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê, âåäóùèé íàó÷íûé ñîòðóäíèê
Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî, e-mail: gsandrako@gmail.com.
Ñåìåíîâ Âëàäèìèð Âèêòîðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, e-mail: semenov.volodya@gmail.com.
148 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6
|