Адаптивный алгоритм для вариационного неравенства на множестве решений задачи о равновесии
Рассмотрены двухуровневые задачи: вариационные неравенства на множестве решений задач о равновесии. Примером таких задач является поиск нормального равновесия Нэша. Для их решения предложен итерационный алгоритм, сочетающий в себе идеи двухэтапного проксимального метода, адаптивности и итеративной р...
Gespeichert in:
| Datum: | 2021 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schriftenreihe: | Кібернетика та системний аналіз |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/190588 |
| 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: | Адаптивный алгоритм для вариационного неравенства на множестве решений задачи о равновесии / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 104–114. — Бібліогр.: 29 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-190588 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1905882023-06-14T14:17:16Z Адаптивный алгоритм для вариационного неравенства на множестве решений задачи о равновесии Ведель, Я.И. Денисов, С.В. Семенов, В.В. Системний аналіз Рассмотрены двухуровневые задачи: вариационные неравенства на множестве решений задач о равновесии. Примером таких задач является поиск нормального равновесия Нэша. Для их решения предложен итерационный алгоритм, сочетающий в себе идеи двухэтапного проксимального метода, адаптивности и итеративной регуляризации. В отличие от применяемых ранее правил выбора величины шага в предлагаемом алгоритме не проводится вычислений значений бифункции в дополнительных точках, не требуются знания информации о липшицевых константах бифункции, константах липшицевости и сильной монотонности оператора. Для монотонных бифункций липшицевого типа и сильно монотонных липшицевых операторов доказана теорема о сильной сходимости алгоритма. Показано, что предложенный алгоритм применим к монотонным двухуровневым вариационным неравенствам в гильбертовых пространствах. Розглянуто дворівневі задачі: варіаційні нерівності на множині розв’язків задач про рівновагу. Прикладом таких задач є пошук нормальної рівноваги Неша. Для їх розв’язання запропоновано ітераційний алгоритм, що поєднує у собі ідеї двоетапного проксимального методу, адаптивності та ітеративної регуляризації. На відміну від правил вибору величини кроку, що застосовувалися раніше, в запропонованому алгоритмі не проводиться обчислень значень біфункції в додаткових точках та не потрібно знання інформації про величину ліпшицевих констант біфункції, констант ліпшицевості та сильної монотонності оператора. Для монотонних біфункцій ліпшицевого типу та сильно монотонних ліпшицевих операторів доведено теорему про сильну збіжність алгоритму. Показано, що запропонований алгоритм можна застосувати до монотонних дворівневих варіаційних нерівностей в гільбертових просторах. In this paper, we consider bilevel problems: variational inequality problems over the set of solutions of the equilibrium problem. An example of such a problem is finding a normal Nash equilibrium. To solve these problems, an iterative algorithm is proposed that combines the ideas of a two-stage proximal method, adaptability, and iterative regularization. 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 information on bifunction’s Lipschitz constants and operator’s Lipschitz and strong monotonicity constants. For monotone bifunctions of Lipschitz type and strongly monotone Lipschitz operators, the theorem on strong convergence of sequences generated by the algorithm is proved. It is shown that the proposed algorithm is applicable to monotone bilevel variational inequalities in Hilbert spaces. 2021 Article Адаптивный алгоритм для вариационного неравенства на множестве решений задачи о равновесии / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 104–114. — Бібліогр.: 29 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190588 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 |
2021 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/190588 |
| citation_txt |
Адаптивный алгоритм для вариационного неравенства на множестве решений задачи о равновесии / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 104–114. — Бібліогр.: 29 назв. — рос. |
| series |
Кібернетика та системний аналіз |
| work_keys_str_mv |
AT vedelʹâi adaptivnyjalgoritmdlâvariacionnogoneravenstvanamnožestverešenijzadačioravnovesii AT denisovsv adaptivnyjalgoritmdlâvariacionnogoneravenstvanamnožestverešenijzadačioravnovesii AT semenovvv adaptivnyjalgoritmdlâvariacionnogoneravenstvanamnožestverešenijzadačioravnovesii |
| first_indexed |
2025-07-16T13:32:15Z |
| last_indexed |
2025-07-16T13:32:15Z |
| _version_ |
1837810567027359744 |
| fulltext |
ÓÄÊ 517.988
ß.È. ÂÅÄÅËÜ, Ñ.Â. ÄÅÍÈÑÎÂ, Â.Â. ÑÅÌÅÍÎÂ
ÀÄÀÏÒÈÂÍÛÉ ÀËÃÎÐÈÒÌ ÄËß ÂÀÐÈÀÖÈÎÍÍÎÃÎ ÍÅÐÀÂÅÍÑÒÂÀ
ÍÀ ÌÍÎÆÅÑÒÂÅ ÐÅØÅÍÈÉ ÇÀÄÀ×È Î ÐÀÂÍÎÂÅÑÈÈ
Àííîòàöèÿ. Ðàññìîòðåíû äâóõóðîâíåâûå çàäà÷è: âàðèàöèîííûå íåðàâåíñòâà
íà ìíîæåñòâå ðåøåíèé çàäà÷ î ðàâíîâåñèè. Ïðèìåðîì òàêèõ çàäà÷ ÿâëÿåòñÿ
ïîèñê íîðìàëüíîãî ðàâíîâåñèÿ Íýøà. Äëÿ èõ ðåøåíèÿ ïðåäëîæåí èòåðàöè-
îííûé àëãîðèòì, ñî÷åòàþùèé â ñåáå èäåè äâóõýòàïíîãî ïðîêñèìàëüíîãî ìå-
òîäà, àäàïòèâíîñòè è èòåðàòèâíîé ðåãóëÿðèçàöèè.  îòëè÷èå îò ïðèìåíÿå-
ìûõ ðàíåå ïðàâèë âûáîðà âåëè÷èíû øàãà â ïðåäëàãàåìîì àëãîðèòìå íå
ïðîâîäèòñÿ âû÷èñëåíèé çíà÷åíèé áèôóíêöèè â äîïîëíèòåëüíûõ òî÷êàõ, íå
òðåáóþòñÿ çíàíèÿ èíôîðìàöèè î ëèïøèöåâûõ êîíñòàíòàõ áèôóíêöèè, êîí-
ñòàíòàõ ëèïøèöåâîñòè è ñèëüíîé ìîíîòîííîñòè îïåðàòîðà. Äëÿ ìîíîòîííûõ
áèôóíêöèé ëèïøèöåâîãî òèïà è ñèëüíî ìîíîòîííûõ ëèïøèöåâûõ îïåðàòî-
ðîâ äîêàçàíà òåîðåìà î ñèëüíîé ñõîäèìîñòè àëãîðèòìà. Ïîêàçàíî, ÷òî ïðåä-
ëîæåííûé àëãîðèòì ïðèìåíèì ê ìîíîòîííûì äâóõóðîâíåâûì âàðèàöèîí-
íûì íåðàâåíñòâàì â ãèëüáåðòîâûõ ïðîñòðàíñòâàõ.
Êëþ÷åâûå ñëîâà: äâóõóðîâíåâàÿ çàäà÷à, âàðèàöèîííîå íåðàâåíñòâî, çàäà÷à
î ðàâíîâåñèè, äâóõýòàïíûé ïðîêñèìàëüíûé ìåòîä, àäàïòèâíîñòü, èòåðàòèâ-
íàÿ ðåãóëÿðèçàöèÿ, ñèëüíàÿ ñõîäèìîñòü.
ÂÂÅÄÅÍÈÅ
 îïòèìèçàöèè è òåîðèè íåêîððåêòíûõ çàäà÷ èñïîëüçóåòñÿ ñëåäóþùèé ïðèåì
ðåøåíèÿ çàäà÷ ñ íååäèíñòâåííûì ðåøåíèåì [1–4]. Çàäà÷å ñòàâèòñÿ â ñîîòâåò-
ñòâèå ñåìåéñòâî âîçìóùåííûõ çàäà÷, îäíîçíà÷íî è êîððåêòíî ðàçðåøèìûõ.
×àñòíîå ðåøåíèå èñõîäíîé çàäà÷è ïîëó÷àþò êàê ïðåäåë ðåøåíèé âîçìóùåí-
íûõ çàäà÷ ïðè óìåíüøåíèè âîçìóùåíèé. Íàéäåííûå òàêèì îáðàçîì ÷àñòíûå
ðåøåíèÿ óäîâëåòâîðÿþò îïðåäåëåííûì äîïîëíèòåëüíûì óñëîâèÿì, íàïðèìåð
ìèíèìàëüíîñòü íîðìû íîðìàëüíîãî ðåøåíèÿ îïòèìèçàöèîííîé çàäà÷è, ïîëó-
÷åííîãî ìåòîäîì ðåãóëÿðèçàöèè Òèõîíîâà. Êðîìå òîãî, â èññëåäîâàíèè îïåðà-
öèé âîçíèêàþò çàäà÷è îïòèìèçàöèè ïî ïîñëåäîâàòåëüíî çàäàííûì êðèòåðèÿì
(ëåêñèêîãðàôè÷åñêàÿ, ïîñëåäîâàòåëüíàÿ èëè ìíîãîýòàïíàÿ îïòèìèçàöèÿ) [5].
Äâóõóðîâíåâûå âàðèàöèîííûå íåðàâåíñòâà âîçíèêëè êàê åñòåñòâåííîå îáîáùå-
íèå çàäà÷ ëåêñèêîãðàôè÷åñêîé îïòèìèçàöèè ñ äâóìÿ êðèòåðèÿìè, à òàêæå ïðè
àíàëèçå îáû÷íûõ îïòèìèçàöèîííûõ çàäà÷ ñ îãðàíè÷åíèÿìè â ôîðìå âàðèàöèîí-
íîãî íåðàâåíñòâà. Êàê ñàìîñòîÿòåëüíûé ìàòåìàòè÷åñêèé îáúåêò äâóõóðîâíå-
âûå âàðèàöèîííûå íåðàâåíñòâà âíà÷àëå ðàññìàòðèâàëèñü â [6]. Ðàçðåøèìîñòè
áîëåå îáùèõ n-óðîâíåâûõ âàðèàöèîííûõ íåðàâåíñòâ ïîñâÿùåíû ðàáîòû [7, 8].
 íàñòîÿùååå âðåìÿ èçâåñòíû ïðèáëèæåííûå ìåòîäû îäíîýòàïíîãî ðåøåíèÿ
âñåõ ýòèõ çàäà÷, èäåéíî áëèçêèå ìåòîäàì øòðàôà è ðåãóëÿðèçàöèè [9–14].
Îäíèì èç ïîïóëÿðíûõ íàïðàâëåíèé ñîâðåìåííîãî ïðèêëàäíîãî íåëèíåéíîãî
àíàëèçà ÿâëÿåòñÿ èññëåäîâàíèå çàäà÷ î ðàâíîâåñèè [15–21], ê êîòîðûì ìîæíî
ñâåñòè ïðîáëåìû ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, âàðèàöèîííûå
íåðàâåíñòâà è ìíîãèå èãðîâûå çàäà÷è.
 äàííîé ñòàòüå ðàññìàòðèâàåòñÿ äâóõóðîâíåâàÿ çàäà÷à: âàðèàöèîííîå íåðà-
âåíñòâî íà ìíîæåñòâå ðåøåíèé çàäà÷è î ðàâíîâåñèè. Ïîäîáíàÿ çàäà÷à ðàññìàòðè-
âàëàñü â ðàáîòå [22], ãäå ïðåäëîæåí ñèëüíî ñõîäÿùåéñÿ àëãîðèòì ñ èñïîëüçîâà-
íèåì îïåðàöèè âû÷èñëåíèÿ çíà÷åíèÿ ðåçîëüâåíòû áèôóíêöèè. Ïîñëåäíåå ñó-
ùåñòâåííî óâåëè÷èâàëî òðóäîåìêîñòü àëãîðèòìà. Íèæå äëÿ ðåøåíèÿ äàííîé
çàäà÷è áóäåò ïðåäëîæåí àäàïòèâíûé âàðèàíò ðàíåå èçó÷åííîãî àëãîðèòìà [23],
104 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
© ß.È. Âåäåëü, Ñ.Â. Äåíèñîâ, Â.Â. Ñåìåíîâ, 2021
îñíîâàííîãî íà äâóõýòàïíîì ïðîêñèìàëüíîì ìåòîäå [21] è èäåå èòåðàòèâíîé ðåãó-
ëÿðèçàöèè [1, 24].  ïðåäëàãàåìîì àëãîðèòìå íå ïðîâîäèòñÿ âû÷èñëåíèé çíà÷åíèé
áèôóíêöèè â äîïîëíèòåëüíûõ òî÷êàõ, íå òðåáóþòñÿ çíàíèÿ èíôîðìàöèè î ëèïøè-
öåâûõ êîíñòàíòàõ áèôóíêöèè, êîíñòàíòàõ ëèïøèöåâîñòè è ñèëüíîé ìîíîòîííîñòè
îïåðàòîðà. Äëÿ ìîíîòîííûõ áèôóíêöèé ëèïøèöåâîãî òèïà è ñèëüíî ìîíîòîííûõ
ëèïøèöåâûõ îïåðàòîðîâ äîêàçàíà òåîðåìà î ñèëüíîé ñõîäèìîñòè àëãîðèòìà.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Âñþäó äàëåå H — äåéñòâèòåëüíîå ãèëüáåðòîâî ïðîñòðàíñòâî ñî ñêàëÿðíûì ïðîèç-
âåäåíèåì ( , )� � è ïîðîæäåííîé íîðìîé || ||� . Äëÿ îïåðàòîðà A H H: � , ìíîæåñòâà
M H� è áèôóíêöèè F H H: � �� îáîçíà÷èì VI A M( , ) è EP F M( , ) ìíîæåñòâà
{ }x M Ax y x y M� � � �: ( , ) 0 è { }x M F x y y M� � �: ( , ) 0 ñîîòâåòñòâåííî.
Äëÿ âûïóêëîãî çàìêíóòîãî ìíîæåñòâà Ñ H� ðàññìîòðèì äâóõóðîâíåâóþ
çàäà÷ó:
íàéòè x VI A EP F C� ( , ( , )) . (1)
Ïðåäïîëîæèì âûïîëíåííûìè ñëåäóþùèå óñëîâèÿ:
(À1) F x x( , )
0 äëÿ âñåõ x Ñ� ;
(À2) F x y F y x( , ) ( , )� � 0 äëÿ âñåõ x, y Ñ� (ìîíîòîííîñòü);
(À3) äëÿ âñåõ x C� ôóíêöèÿ F x( , )� ïîëóíåïðåðûâíà ñíèçó è âûïóêëà íà Ñ;
(À4) äëÿ âñåõ y C� ôóíêöèÿ F y( , )� ñëàáî ïîëóíåïðåðûâíà ñâåðõó íà Ñ;
(À5) äëÿ âñåõ x, y, z Ñ� èìååò ìåñòî
F x y F x z F z y a x z b z y( , ) ( , ) ( , ) || || || ||� � � � � �2 2 ,
ãäå a, b — ïîëîæèòåëüíûå êîíñòàíòû (ëèïøèöåâîñòü);
(À6) EP F C( , )
�;
(À7) A C H: � — �-ñèëüíî ìîíîòîííûé è L-ëèïøèöåâûé îïåðàòîð.
Ïðè äàííûõ óñëîâèÿõ ìíîæåñòâî EP F C( , ) ÿâëÿåòñÿ âûïóêëûì è çàìêíó-
òûì [15, 18], à çàäà÷à (1) èìååò åäèíñòâåííîå ðåøåíèå x H� [25].
Çàìå÷àíèå 1. Óñëîâèå (À5) òèïà ëèïøèöåâîñòè ââåäåíî G. Mastroeni â [17].
Íàïðèìåð, áèôóíêöèÿ F x y Ax y x( , ) ( , )
� ñ ëèïøèöåâûì îïåðàòîðîì A C H: �
óäîâëåòâîðÿåò (À5) ïðè a L
� / 2 , b L
/ 2� , ãäå L � 0 — êîíñòàíòà Ëèïøèöà îïå-
ðàòîðà A , �� 0 .
Çàìå÷àíèå 2. Íàèáîëåå èçâåñòíûì ÷àñòíûì ñëó÷àåì (1) ÿâëÿåòñÿ çàäà÷à ïî-
èñêà íîðìàëüíîãî ðåøåíèÿ âàðèàöèîííîãî íåðàâåíñòâà (ïðè Ax x
,
F x y Bx y x( , ) ( , )
� , ãäå B C H: � ):
1
2
2|| || minx � , x Ñ� : ( , )Bx y x� � 0 �y Ñ.
Îòìåòèì ñëåäóþùåå âàæíîå ïîíÿòèå. Ïóñòü g H: � � ��� { } — ñîáñòâåí-
íàÿ âûïóêëàÿ ïîëóíåïðåðûâíàÿ ñíèçó ôóíêöèÿ. Ïðîêñèìàëüíûì îïåðàòî-
ðîì [26], àññîöèèðîâàííûì ñ ôóíêöèåé g, íàçûâàþò îïåðàòîð H x xg�
� prox
� �
�
�
�
�
�
��arg min domy g g y y x( ) || ||
1
2
2 . Îïåðàòîð ÿâëÿåòñÿ òâåðäî íåðàñòÿãèâàþ-
ùèì (firmly nonexpansive) è g y g z z x y z( ) ( ) ( , )� � � � � 0 äëÿ âñåõ y g�dom òîãäà
è òîëüêî òîãäà, êîãäà z xg
prox . Èñõîäÿ èç ýòîãî èìååì ñëåäóþùèé êðèòåðèé
îïòèìàëüíîñòè [26]: x g�arg min òîãäà è òîëüêî òîãäà, êîãäà x xg
prox .
Íèæå ïðåäëîæåí ñèëüíî ñõîäÿùèéñÿ àëãîðèòì ðåøåíèÿ çàäà÷è (1), íå òðåáó-
þùèé çíàíèÿ êîíñòàíò èç óñëîâèé (À5), (À7). Íî âíà÷àëå àïïðîêñèìèðóåì çàäà-
÷ó (1) îäíîóðîâíåâîé è áîëåå ðåãóëÿðíîé çàäà÷åé î ðàâíîâåñèè.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 105
ÀÏÏÐÎÊÑÈÌÀÖÈß ÒÈÕÎÍÎÂÀ–ÁÐÀÓÄÅÐÀ
Ðàññìîòðèì âñïîìîãàòåëüíóþ çàäà÷ó î ðàâíîâåñèè, çàâèñÿùóþ îò ïàðàìåòðà
�� 0 :
íàéòè x Ñ� : F x y Ax y x( , ) ( , )� � �� 0 �y Ñ. (2)
Ñëåäóÿ À.Á. Áàêóøèíñêîìó [1], íàçîâåì çàäà÷ó (2) àïïðîêñèìàöèåé Òèõîíî-
âà–Áðàóäåðà äâóõóðîâíåâîé çàäà÷è (1).
Çàìå÷àíèå 3. Äëÿ ðåøåíèÿ íåêîððåêòíûõ ýêñòðåìàëüíûõ çàäà÷ ïîäîáíàÿ àï-
ïðîêñèìàöèÿ áûëà ïðåäëîæåíà À.Í. Òèõîíîâûì ïðè ïîñòðîåíèè ðåãóëÿðèçóþ-
ùèõ àëãîðèòìîâ. Ïîçäíåå F. Browder [2, 3] ïðèìåíÿë ïîäîáíóþ ñõåìó.
Èç ðåçóëüòàòîâ ðàáîòû [18] ñëåäóåò ñóùåñòâîâàíèå è åäèíñòâåííîñòü ðåøå-
íèÿ x Ñ� � çàäà÷è (2) äëÿ ëþáîãî �� 0 . Ýëåìåíòû x Ñ� � èìåþò íåñêîëüêî
âàæíûõ ñâîéñòâ.
Ëåììà 1 [23]. Ñïðàâåäëèâû ñëåäóþùèå íåðàâåíñòâà:
1) || || ( ) || ||x L Ax� � �� �� �1 11 äëÿ âñåõ �� 0 ;
2) || || | | ( ) || ||x x L Ax� � � � � � �� � � �� � �1 1 11 äëÿ âñåõ �, �� 0 .
Ïðè ñòðåìëåíèè ìàëîãî ïîëîæèòåëüíîãî ïàðàìåòðà � ê íóëþ ýëåìåíòû x�
ñèëüíî ñõîäÿòñÿ ê ðåøåíèþ çàäà÷è (1).
Ëåììà 2 [23]. Ïóñòü âûïîëíÿþòñÿ óñëîâèÿ (A1)–(A4) è (A6), (A7). Òîãäà
lim || ||
�
�
�
�
0
0x x .
Äàëåå ïåðåéäåì ê íåïîñðåäñòâåííîìó ðàññìîòðåíèþ àëãîðèòìà äëÿ çàäà÷è (1).
ÀÄÀÏÒÈÂÍÛÉ ÀËÃÎÐÈÒÌ
Íà îñíîâàíèè ñõåìû äâóõýòàïíîãî ïðîêñèìàëüíîãî ìåòîäà [21, 27] äëÿ ðåøå-
íèÿ çàäà÷è (1) â ðàáîòå [23] áûë ïðåäëîæåí òàêîé ìåòîä:
z x Ax
y z
x
n n n n n
n F y n
n F y
n n
n n
�
� �
�
� �
�
�
,
,( , )
(
prox
prox
1
1 , ) ,�
�
�
�
�
� zn
(3)
ãäå � n çàäàâàëèñü èñõîäÿ èç òðåáîâàíèÿ � � �n
a b
� �
�
�
�
��
�
�
��[ , ] ,
( )
0
1
2 2
, à ïîëîæè-
òåëüíàÿ ïîñëåäîâàòåëüíîñòü ( )� n òàêîâà, ÷òî lim
n
n
��
� 0 , � nn
��
��
1
è
lim ( )
n
n n n
��
�
��
� � �1
2 0 .
×òîáû èñêëþ÷èòü èñïîëüçîâàíèå â (3) èíôîðìàöèè î çíà÷åíèÿõ a è b ïðè çàäà-
íèè ãðàíèö äëÿ � n , ðàññìîòðèì ñëåäóþùèé àëãîðèòì ñ àäàïòèâíûì âûáîðîì � n .
Àëãîðèòì 1
Èíèöèàëèçàöèÿ. Âûáèðàåì ýëåìåíòû x1, y C0 � , ��
�
�
�
�
�
�0
1
3
, , �1 0� ��( , ) .
Ïîëàãàåì n
1.
Øàã 1. Âû÷èñëèòü z x Axn n n n n
�� � .
Øàã 2. Âû÷èñëèòü y zn F y nn n
� �prox � ( , )1
.
Øàã 3. Âû÷èñëèòü x zn F y nn n� �
1 prox � ( , ) .
Øàã 4. Âû÷èñëèòü
�
�
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
y y y x
F y x F y2
1
2
1
2
1 1
� �
� �
� � �
� � ��
�
�
�
��
�
�
�
�
�
�
�
�
�
1 1, ) ( , ))y F y xn n n
èíà å.�
Ïîëîæèòü n n:
�1 è ïåðåéòè íà øàã 1.
106 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 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
� � � �� �max , ( || || || || ){ }a b y y y xn n n n1
2
1
2 .
Îòíîñèòåëüíî ïîëîæèòåëüíûõ ïàðàìåòðîâ � n ïðåäïîëàãàåì âûïîëíåííûìè
ñëåäóþùèå óñëîâèÿ:
(Â1) lim
n
n
��
� 0 ;
(Â2) � nn
��
��
1
;
(Â3) lim
n
n n
n
��
� �
� �
�
1
2
0 .
Çàìå÷àíèå 4.  êà÷åñòâå ïîñëåäîâàòåëüíîñòè ( )� n ìîæíî èñïîëüçîâàòü
� n
pn
� , p�( , )0 1 .
Ïåðåéäåì ê îáîñíîâàíèþ àëãîðèòìà 1. Äîêàçàòåëüñòâî ñõîäèìîñòè ïðîâå-
äåì ïî òàêîé ñõåìå. Ïóñòü x
n� — ðåøåíèå çàäà÷è (2) ïðè � �
n . Ïîñêîëüêó
|| || || || || ||x x x x x xn n n n
� � � � �� � , lim || ||
n
x x
n��
�
� 0 , òî äîñòàòî÷íî ïîêàçàòü, ÷òî
ïîðîæäåííàÿ ïîñëåäîâàòåëüíîñòü ( )xn îáëàäàåò ñâîéñòâîì lim || ||
n
nx x
n��
�
� 0 .
Áóäåì èñïîëüçîâàòü èçâåñòíóþ ëåììó î ðåêóððåíòíûõ ÷èñëîâèõ íåðàâåí-
ñòâàõ.
Ëåììà 3 [1]. Ïóñòü ïîñëåäîâàòåëüíîñòü íåîòðèöàòåëüíûõ ÷èñåë ( )�n óäîâëåò-
âîðÿåò ðåêóððåíòíîìó íåðàâåíñòâó � � � n n n n� � � �1 1( ) äëÿ âñåõ n��, ãäå ïî-
ñëåäîâàòåëüíîñòè ( )� n è ( ) n îáëàäàþò ñâîéñòâàìè: � n �( , )0 1 , � nn
��
��
1
,
lim
n
n n
��
� � � 1 0 . Òîãäà lim
n
n
��
� 0 .
Äîêàæåì âàæíîå íåðàâåíñòâî äëÿ ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn è ýëåìåí-
òîâ x
n� .
Ëåììà 4. Äëÿ ïîðîæäåííûõ àëãîðèòìîì 1 ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn è
ýëåìåíòîâ x
n� âûïîëíÿåòñÿ íåðàâåíñòâî
|| || ( ) || || ( ) ||x x x xn n n n n nn n� �
�� � � � � �1
2 2
1
11 1� �� � � � � � x yn n� � �1
2||
� � � � �
�
� �
�
�( ) || || ||1 2 2
1
1 2 1 2
1
1� � � � � � � � �n n n n n n n n nL y x x � �yn 1
2|| . (4)
Äîêàçàòåëüñòâî. Èìååì
|| || || || || || ( ,x x x x x x x x xn n n n n nn n� � ��
� � � � �1
2 2
1
2
12� � n x
n� �
1 � )
� � � � � ��|| || || || || ||x x x y y xn n n n nn�
2 2
1
2
(5)
� � � � � �� � �2 21 1 1( , ) ( , )x y y x x x x xn n n n n n n n� .
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 107
Èç îïðåäåëåíèÿ òî÷åê xn�1 è yn ñëåäóåò
� � � �� �n n n n n n n n n n nF y x F y x x x Ax x x
n n
( , ) ( , ) ( ,� � � � �� � �1 1 1 ) , (6)
� � � �n n n n n n n n n n n n nF y x F y y x Ax y y x( , ) ( , ) ( ,� � � �� � � � � �1 1 1 1 ) . (7)
Èñïîëüçóÿ íåðàâåíñòâà (6), (7) äëÿ îöåíêè ñêàëÿðíûõ ïðîèçâåäåíèé â (5), ïî-
ëó÷àåì
|| || || || || || | | | |x x x x x y y xn n n n n nn n� �� � � � � � � �1
2 2 2
1
2
� �
� � � �� � � �2 1 1 1 1� �n n n n n n n nF y x F y x F y x F y y
n
( ( , ) ( , ) ( , ) ( , )) �
� �2� � �n n n nAx x y
n
( , ) . (8)
Ñîãëàñíî ïðàâèëó âû÷èñëåíèÿ � n�1 èìååì íåðàâåíñòâî
F y x F y y F y xn n n n n n( , ) ( , ) ( , )� � � �� � �1 1 1 1
� � � ��
�
�
� �� �2 1
1
1
1
2
1
2
n n n n ny y x y( || || || || ) . (9)
Äëÿ îöåíêè âûðàæåíèÿ F y x F y y F y xn n n n n n( , ) ( , ) ( , )� � � �� �1 1 1 1 â (8) âîñïîëü-
çóåìñÿ (9). Ïîëó÷èì
|| || || || || || || ||x x x x x y y xn n n n n nn n� �� � � � � � � �1
2 2 2
1
2
� � �� �n n n ny y
�
�
� � �
1
1
1
2|| ||
� � � � �
�
�
�� � � � � �� �n n n n n n n n nx y F y x Ax x
n n1
1
1
2 2 2|| || ( , ) ( , yn ) .
×ëåí || ||y yn n� �1
2 îöåíèì ñëåäóþùèì îáðàçîì: || ||y yn n� � �1
2 2 1
2|| ||y xn n� � �
� �2 2|| ||x yn n . Èìååì
|| || || || || || || ||x x x x x y y xn n n n n nn n� �� � � � � � � �1
2 2 2
1
2
� � 2
1
1
1
2�� �n n n ny x
�
�
� � �|| ||
� � � � �
�
�
�
�
�2
1
1 2
1
1
1
2�� � �� �n n n n n n n nx y x y|| || || ||
� � �2 2� � �� �n n n n n nF y x Ax x y
n n
( , ) ( , ) . (10)
Èç ìîíîòîííîñòè áèôóíêöèè F ñëåäóåò F y x F x yn nn n
( , ) ( , )� �� , îòêóäà
F y x Ax y x F x y Ax y xn n n n n nn n n n n
( , ) ( , ) ( , ) ( ,� � � � � �� �� � � � � �
n
) .
Ïîñêîëüêó F x y Ax y x
n n nn n n( , ) ( , )� � ��� � � 0 , òî
F y xn n
( , )� � � � �n nAx y x
n n
( , )� .
Ñ ó÷åòîì ïîñëåäíåé îöåíêè â (10) ïîëó÷èì íåðàâåíñòâî
|| || || || || || || ||x x x x x y y xn n n n n nn n� �� � � � � � � �1
2 2 2
1
2
� �
� � � � �
�
�
� �
�2 2
1
1
1
2
1
1 2�� � �� � �� �n n n n n n n n n n
y x x y|| || || ||
�
�
� � �
1
1
1
2|| ||x yn n
� � �2� � � �n n n nAx Ax x y
n n
( , ) . (11)
Îöåíèì ñâåðõó ÷ëåí ( , )Ax Ax x yn nn n
� �� � . Èìååì
( , ) ( , ) ( ,Ax Ax x y Ax Ax x x Ax Ax x yn n n n n nn n n n n
� �
� � � � �� � � � � n ) �
� � � � � � � � � �� �� � �|| || || || || || || ||x x L x x x y x x
n n nn n n n n
2 2
� ��2 21 2 2 1 1 2� � �� � �
|| || || ||x x L x yn n nn
� � � �� � �� ��2 21 2 2 1 1 2|| || || ||x x L x yn n nn
. (12)
108 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
Èç íåðàâåíñòâ (11) è (12) ïîëó÷àåì
|| || ( ) || || ( ) ||x x x xn n n n n nn n� �
�� � � � � �1
2 2
1
11 1� �� � � �� � x yn n� � �1
2||
� � � � �
�
� �
�
�( ) || || ||1 2 2
1
1 2 1 2
1
1�� � � � � �� �n n n n n n n n nL y x x � �yn 1
2|| ,
÷òî è òðåáîâàëîñü äîêàçàòü. �
Äîêàæåì îöåíêó, èç êîòîðîé ñëåäóåò ñõîäèìîñòü ê íóëþ ïîñëåäîâàòåëüíî-
ñòåé ( || || )x xn n
� � è ( || || )x yn n� �1 .
Ëåììà 5. Äëÿ ïîðîæäåííûõ àëãîðèòìîì 1 ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn è
ýëåìåíòîâ x
n� ïðè áîëüøèõ n âûïîëíÿåòñÿ íåðàâåíñòâî
|| || || ||x x x yn
n n
n n
n nn�
� �
�
� �
�� �
�
�
�1
2 1 2
1
1 1
11
2
1
�
�� �
� � �
2 �
� �
�
�
�
�
�
� � �
�
��
�
1
2
2
1
2 1
1
� � � �� �
� � �
�
n n
n
n n
n n
nx x x y
n
|| || || n�
�
�
�
�
�
�
�
�
�1
2||
2 1
2
3
M
n
n n
n
� �
� �
�
( )� �
, (13)
ãäå M L Ax
�� �� �1 11( ) | | | | .
Äîêàçàòåëüñòâî. Èìååì
|| || || || || || (x x x x x x xn n nn n n n� � ��
� � � �
� �1
2
1
2 2
1 1
2� � � � 1 1 1
� � �
� �
x x x
n n n� � �, )
� � � � � �� �� � �
|| || || || || || ||x x x x x x xn nn n n n1
2 2
11 1 1
2� � � � � �n n
x
�
� �
1
||
� � � �
�
�� � �
( ) || || || ||1
1
1
2 2
1 1
�
�
�
� � �x x x xn n n n
, (14)
ãäå �� 0 . Ïîëîæèì â (14) � � � �
1
2
n n . Ïîëó÷èì
|| ||x xn n� � �1
2
�
2
2
2
1
2 2
1 1
�
� �
�
�� � �
� � � � � �
� � �
� � �
n n
n
n n
n n
x x x x
n n n
|| || || || . (15)
 ñèëó ïðàâèë ñîãëàñîâàíèÿ çíà÷åíèé ïàðàìåòðîâ � n , � n ïðè áîëüøèõ n
èìååì1 0� �� � �n n . Ñ ó÷åòîì âòîðîãî íåðàâåíñòâà ëåììû 1 èç (15) âûâîäèì
|| || || ||x x x xn
n n
nn n� �� �
�
� �
�1
2
1
22
2 1� �
� � �
�
� �
�� � �( ) ( )
( ) || ||
2
11
2
2
1 1� � �
� � �
� �
�
� �n n
n n
n n
n
L Ax (16)
äëÿ âñåõ n n� 0 . Èñïîëüçîâàâ (16) â (4), ïîëó÷èì (äëÿ n n� 0)
2
2
11
2 2
1
�
� � � � �� �
� � �
� � �� �
n n
n n n nx x x x
n n
|| || ( ) || ||
� � � � � �
�
�
� �
� �( ) || || (1 1 2
1
1
1
2
1
1 2 1�� � �� � � � �n n n n n n n nx y L ) || ||y xn n� �2
� � �
� �
�
�
�
�2
2
1
1
1
2 1
2
� � �
� � �
� � �
� �
�
n n n n
n n
n n
n n
n
x y|| ||
( ) ( )
2
M ,
ãäå M L Ax
�� �� �1 11( ) || || . Îòñþäà ñëåäóåò íåðàâåíñòâî
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 109
|| || || ||
(
x x x xn
n n
n n
n
n
n n� � �
�
�
� �
�
�1
2 2
1
2 2
2
2 1
� �
� � �
� � �
�� �
� � �
n
n n
n nx y�
�
�
�
� �1
1
1
2
2
)
|| ||
�
� �
�
� ��
� �2 1 2
2
4
1
1 2 1
2
( )
|| ||
�� � � � �
� � �
�� �n n n n
n n
n n
n n
L
y x �
�
�
�
� �1
1
1
2
2 � � �n n
n nx y|| ||
�
��2 1
2
3
M
n
n n
n
� �
� �
�
( )
. (17)
Ïåðåãðóïïèðîâàâ ÷ëåíû â (17), ïîëó÷èì
|| || || ||x x x yn
n n
n n
n nn�
� �
�
� �
�� �
�
�
�1
2 1 2
1
1 1
11
2
1
�
�� �
� � �
2 �
�
�
�
� �
�
��
�
2 2
2
2
1
2 1
1
� � �
� � �
�� �
� � �
�
n n
n n
n
n n
n n
nx x x
n
|| || || yn�
�
�
�
�
�
�
�
�
�1
2|| (18)
�
� �
�
� ��
� �2 1 2
2
1
1 2 1
2
( )
|| ||
�� � � � �
� � �
n n n n
n n
n n
L
y x
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
� �
1
1
1
2
2
1
1
1
1 2
1
1 1
�� �
� � �
�� �
� � �
n n
n n
n n
n n�
�
�
�
�
�
�
� ��|| ||x yn n1
2 2 1
2
3
M
n
n n
n
� �
� �
�
( )� �
.
Ïîñêîëüêó ��
�
�
�
�
�
�0
1
3
, , ñóùåñòâóåò lim
n
n
��
�� 0 è lim
n
n
��
� 0 , òî, íà÷èíàÿ ñ íåêî-
òîðîãî íîìåðà n1 , áóäóò âûïîëíÿòüñÿ íåðàâåíñòâà
1 2
2
01
1 2 1� �
�
��
� ��� � � � �
� � �
n n n n
n n
L
,
1
1
1
2
2
1
01
1
1 2
1
1 1
�
�
�
�
��
�
� �
�
� �
�� �
� � �
�� �
� � �
n n
n n
n n
n n
,
2 2
2
1
2
�
�
! �
� � �
� � �
� � �n n
n n
n n .
Òàêèì îáðàçîì, äëÿ n N n n�
max ,{ }0 1 èç (18) ñëåäóåò
|| || || ||x x x yn
n n
n n
n nn�
� �
�
� �
�� �
�
�
�1
2 1 2
1
1 1
11
2
1
�
�� �
� � �
2 �
� �
�
�
�
�
�
� � �
�
��
�
1
2
2
1
2 1
1
� � � �� �
� � �
�
n n
n
n n
n n
nx x x y
n
|| || || n�
�
�
�
�
�
�
�
�
�1
2||
2 1
2
3
M
n
n n
n
� �
� �
�
( )� �
,
÷òî è òðåáîâàëîñü äîêàçàòü. �
Ñôîðìóëèðóåì îñíîâíîé ðåçóëüòàò.
Òåîðåìà 1. Ïóñòü âûïîëíÿþòñÿ óñëîâèÿ (À1)–(À7) è (B1)–(B3). Òîãäà äëÿ
ïîðîæäåííûõ àëãîðèòìîì 1 ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn èìååò ìåñòî
lim || || lim || ||
n
n
n
nx x y x
�� ��
�
�
0 , (19)
ãäå x H� — åäèíñòâåííîå ðåøåíèå çàäà÷è (1).
110 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
Äîêàçàòåëüñòâî. Â ñèëó ëåììû 3 è íåðàâåíñòâà (13) èìååì
|| || ( ) || ||x x x yn n n n n n nn
� � � � �
�
� �
�� �� � � � �2
1
1 1
1
22 1 0 ïðè n � �,
îòêóäà
lim || || lim || ||
n
n
n
n nx x y x
n�� ��
��
�
� 1 0 . (20)
Èç íåðàâåíñòâà || || || || || ||x x x x x xn n n n
� � � � �� � , ëåììû 2 è (20) ïîëó÷àåì ðà-
âåíñòâà (19). �
Çàìå÷àíèå 5. Î÷åâèäíî, ÷òî ïîñëåäîâàòåëüíîñòü ( )zn òàêæå ñèëüíî ñõîäèò-
ñÿ ê x H� .
ÂÀÐÈÀÍÒ ÀËÃÎÐÈÒÌÀ ÄËß ÂÀÐÈÀÖÈÎÍÍÛÕ ÍÅÐÀÂÅÍÑÒÂ
Ðàññìîòðèì ÷àñòíûé ñëó÷àé çàäà÷è (1): äâóõóðîâíåâîå âàðèàöèîííîå íåðàâåí-
ñòâî â ãèëüáåðòîâîì ïðîñòðàíñòâå H:
íàéòè x VI A VI A C� ( , ( , ))2 1 . (21)
Ïðåäïîëîæèì âûïîëíåííûìè ñëåäóþùèå óñëîâèÿ: ìíîæåñòâî C H� âû-
ïóêëîå è çàìêíóòîå; îïåðàòîð A C H1: � ìîíîòîííûé è ëèïøèöåâûé; ìíîæåñòâî
VI A C( , )1 íå ïóñòî; îïåðàòîð A C H2 : � ñèëüíî ìîíîòîííûé è ëèïøèöåâûé.
Ïóñòü PC — îïåðàòîð ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ íà âûïóêëîå çàìêíóòîå
ìíîæåñòâî C, ò.å. P xC — åäèíñòâåííûé ýëåìåíò ìíîæåñòâà C ñî ñâîéñòâîì
|| || min || ||P x x z xC
z C
�
�
�
.
Äëÿ çàäà÷è (21) àëãîðèòì 1 ïðèíèìàåò ñëåäóþùèé âèä.
Àëãîðèòì 2
Èíèöèàëèçàöèÿ. Âûáèðàåì ýëåìåíòû x1, y C0 � , ��
�
�
�
�
�
�0
1
3
, , �1 0� ��( , ).
Ïîëàãàåì n
1.
Øàã 1. Âû÷èñëèòü z x A xn n n n n
�� � 2 .
Øàã 2. Âû÷èñëèòü y P z A yn C n n n
� �( )� 1 1 .
Øàã 3. Âû÷èñëèòü x P z A yn C n n n�
�1 1( )� .
Øàã 4. Âû÷èñëèòü
�
�
�
�n
n n n n n
n
n
A y A y x y
y�
� �
�
� � �
1
1 1 1 1
1
0
2
, ( , ) ,
min ,
||
åñëè
� � �
� �
�
�
�
��
�
�
�
�
�
� �
y x y
A y A y x y
n n n
n n n n
|| || ||
( , )
2
1
2
1 1 1 1
èíà å.�
�
�
�
�
�
Ïîëîæèòü n n:
�1 è ïåðåéòè íà øàã 1.
Èç òåîðåìû 1 âûòåêàåò ñëåäóþùèé ðåçóëüòàò.
Òåîðåìà 2. Ïóñòü H — ãèëüáåðòîâî ïðîñòðàíñòâî; C X� — íåïóñòîå âûïóê-
ëîå çàìêíóòîå ìíîæåñòâî; îïåðàòîð A C H1: � ìîíîòîííûé è ëèïøèöåâûé; ìíî-
æåñòâî VI A C( , )1 íå ïóñòî; îïåðàòîð A C H2 : � ñèëüíî ìîíîòîííûé è ëèïøèöå-
âûé; âûïîëíÿþòñÿ óñëîâèÿ (B1)–(B3). Òîãäà ïîðîæäåííûå àëãîðèòìîì 2 ïîñëåäî-
âàòåëüíîñòè ( )xn è ( )yn ñèëüíî ñõîäÿòñÿ ê åäèíñòâåííîìó ðåøåíèþ çàäà÷è (21).
Çàìå÷àíèå 6. Àíàëîãè÷íûé òåîðåìå 2 ðåçóëüòàò èìååò ìåñòî äëÿ ìîäèôèêà-
öèè àëãîðèòìà 2 ñ çàìåíîé èíñòðóêöèè ïåðåñ÷åòà � n íà ñëåäóþùóþ:
�
�
� �
n
n n n
n n n
A y A y
y y A y
�
�
�
�
�
1
1 1 1
1 1
0, ,
min , || || ||
åñëè
{ n nA y�
��
�
�
� 1 1
1|| } èíà å,�
ãäå ��
�
�
�
�
�
�0
1
3
, .
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 111
Çàìå÷àíèå 7. Ìîæíî ïîñòðîèòü ýêîíîìíóþ ìîäèôèêàöèþ àëãîðèòìà 2.
Ñëåäóåò èçìåíèòü øàã 3, ïîëîæèâ x P z A yn T n n nn�
�1 1( )� , ãäå T z Hn
�{ :
( , )z A y y z yn n n n n� � � ��� 1 1 0}. Äåòàëè ìû ïëàíèðóåì ïðåäñòàâèòü â áëèæàé-
øåé ðàáîòå.
ÇÀÊËÞ×ÅÍÈÅ
 ñòàòüå ðàññìàòðèâàåòñÿ äâóõóðîâíåâàÿ çàäà÷à: âàðèàöèîííîå íåðàâåíñòâî íà
ìíîæåñòâå ðåøåíèé çàäà÷è î ðàâíîâåñèè [22, 23]. Äëÿ ðåøåíèÿ äàííîé çàäà÷è
ïðåäëîæåí èòåðàöèîííûé àëãîðèòì, ñî÷åòàþùèé â ñåáå èäåè äâóõýòàïíîãî
ïðîêñèìàëüíîãî ìåòîäà [21, 27], àäàïòàöèè [28] è èòåðàòèâíîé ðåãóëÿðèçà-
öèè [1, 24]. Àëãîðèòì èìååò ñëåäóþùóþ ñòðóêòóðó:
z x Ax
y z
x
n n n n n
n F y n
n F y
n n
n n
�
� �
�
� �
�
�
,
,( , )
(
prox
prox
1
1 , ) ,�
�
�
�
�
� zn
ãäå � n � 0 ïîäáèðàåòñÿ àäàïòèâíî, à ïîëîæèòåëüíàÿ ïîñëåäîâàòåëüíîñòü ( )� n
òàêîâà, ÷òî lim
n
n
��
� 0 , � nn
��
��
1
è lim ( )
n
n n n
��
�
��
� � �1
2 0 .  îòëè÷èå
îò ïðèìåíÿåìûõ ðàíåå [23] ïðàâèë âûáîðà âåëè÷èíû øàãà â ïðåäëàãàåìîì àë-
ãîðèòìå íå ïðîâîäèòñÿ âû÷èñëåíèé çíà÷åíèé áèôóíêöèè â äîïîëíèòåëüíûõ
òî÷êàõ è íå òðåáóþòñÿ çíàíèÿ èíôîðìàöèè î ëèïøèöåâûõ êîíñòàíòàõ áèôóíê-
öèè. Äëÿ ìîíîòîííûõ áèôóíêöèé ëèïøèöåâîãî òèïà è ñèëüíî ìîíîòîííûõ
ëèïøèöåâûõ îïåðàòîðîâ äîêàçàíà òåîðåìà î ñèëüíîé ñõîäèìîñòè àëãîðèòìà.
Äîêàçàòåëüñòâî îïèðàåòñÿ íà ðåçóëüòàòû è òåõíèêó ðàáîò [21, 23, 24, 28].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Bakushinskii A.B., Goncharskii A.V. Iterative methods for solving ill-posed problems. Moscow:
Nauka, 1989. 126 p.
2. Browder F. Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat.
Acad. Sci. USA. 1966. Vol. 56, N 4. P. 1080–1086.
3. Browder F. Convergence of approximants of fixed points of nonexpansive non-linear mappings in
Banach spaces. Arch. Rational Mech. Anal. 1967. Vol. 24. P. 82–90.
4. Attouch H. Viscosity solutions of minimization problems. SIAM J. Optim. 1996. Vol. 6. Iss. 3.
P. 769–806. https://doi.org/10.1137/S1052623493259616.
5. Ïîäèíîâñêèé Â.Â., Ãàâðèëîâ Â.Í. Îïòèìèçàöèÿ ïî ïîñëåäîâàòåëüíî ïðèìåíÿåìûì êðèòåðèÿì.
Ìîñêâà: Ñîâ. ðàäèî, 1975. 192 ñ.
6. Kalashnikov V.V., Kalashnikova N.I. Solution of two-level variational inequality. Cybernetics and
Systems Analysis. 1994. Vol. 30, N 4. P. 623–625. https://doi.org/10.1007/BF02366574.
7. Êîííîâ È.Â. Î ñèñòåìàõ âàðèàöèîííûõ íåðàâåíñòâ. Èçâ. âóçîâ. Ìàòåì. 1997. ¹ 12. C. 79–88.
8. Ïîïîâ Ë.Ä. Ëåêñèêîãðàôè÷åñêèå âàðèàöèîííûå íåðàâåíñòâà è íåêîòîðûå ïðèëîæåíèÿ. Ìàòå-
ìàòè÷åñêîå ïðîãðàììèðîâàíèå. Ðåãóëÿðèçàöèÿ è àïïðîêñèìàöèÿ. Ñá. ñòàòåé. Òð. ÈÌÌ. 2002.
T. 8, ¹ 1. Ñ. 103–115.
9. Ïîïîâ Ë.Ä. Îá îäíîýòàïíîì ìåòîäå ðåøåíèÿ ëåêñèêîãðàôè÷åñêèõ âàðèàöèîííûõ íåðàâåíñòâ.
Èçâ. âóçîâ. Ìàòåì. 1998. ¹ 12. C. 71–81.
10. Solodov M. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis.
2007. Vol. 14. P. 227–238.
11. 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, N 4. P. 13–18.
https://doi.org/10.1615/JAutomatInfScien.v42.i4.20.
112 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
12. 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, N 5. P. 45–56.
https://doi.org/10.1615/JAutomatInfScien.v46.i5.40.
13. 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.
14. 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, N 7. P. 31–46. https://doi.org/10.1615/JAutomatInfScien.v47.i7.40.
15. Kassay G., Radulescu V.D. Equilibrium problems and applications. London: Academic Press, 2019.
xx+419 p.
16. Antipin A.S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997.
Vol. 37. P. 1285–1296. https://doi.org/10.1134/S0965542507120044.
17. 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.
18. Combettes P.L., Hirstoaga S.A. Equilibrium programming in Hilbert spaces. J. Nonlinear Convex
Anal. 2005. Vol. 6. P. 117–136.
19. 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.
20. 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.
21. 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, 115. Cham: Springer, 2016.
P. 315–325. https://doi.org/10.1007/978-3-319-42056-1_10.
22. Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of
solutions the equilibrium problems. In: Zgurovsky M.Z., Sadovnichiy V.A. (eds.). Continuous and
Distributed Systems. Solid Mechanics and Its Applications, 211, Springer International Publishing
Switzerland, 2014. P. 131–146. https://doi.org/10.1007/978-3-319-03146-0_10.
23. Vedel Ya.I., Denisov S.V., Semenov V.V. Algorithm for variational inequality problem over the set
of solutions the equilibrium problems. Journal of Numerical and Applied Mathematics. 2020.
N 1 (133). P. 18–30.
24. Popov L.D. On schemes for the formation of a master sequence in a regularized extragradient
method for solving variational inequalities. Russian Mathematics. 2004. Vol. 48, N 1. P. 67–76.
25. Kinderlehrer D., Stampacchia G. An introduction to variational inequalities and their applications.
New York: Academic Press, 1980. Russian transl., Moscow: Mir, 1983. 256 p.
26. Bauschke H.H., Combettes P.L. Convex analysis and monotone operator theory in Hilbert spaces.
Berlin; Heidelberg; New York: Springer, 2011. 408 p.
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.
28. 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.
29. Malitsky Yu.V., Semenov V.V. An extragradient algorithm for monotone variational inequalities.
Cybernetics and Systems Analysis. 2014. Vol. 50, N 2. P. 271–277. https://doi.org/10.1007/
s10559-014-9614-8.
Íàä³éøëà äî ðåäàêö³¿ 19.05.2020
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 113
ß.². Âåäåëü, Ñ.Â. Äåíèñîâ, Â.Â. Ñåìåíîâ
ÀÄÀÏÒÈÂÍÈÉ ÀËÃÎÐÈÒÌ ÄËß ÂÀвÀÖ²ÉÍί ÍÅвÂÍÎÑÒ²
ÍÀ ÌÍÎÆÈͲ ÐÎÇÂ’ßÇʲ ÇÀÄÀײ ÏÐΠвÂÍÎÂÀÃÓ
Àíîòàö³ÿ. Ðîçãëÿíóòî äâîð³âíåâ³ çàäà÷³: âàð³àö³éí³ íåð³âíîñò³ íà ìíîæèí³
ðîçâ’ÿçê³â çàäà÷ ïðî ð³âíîâàãó. Ïðèêëàäîì òàêèõ çàäà÷ º ïîøóê íîðìàëüíî¿
ð³âíîâàãè Íåøà. Äëÿ ¿õ ðîçâ’ÿçàííÿ çàïðîïîíîâàíî ³òåðàö³éíèé àëãîðèòì,
ùî ïîºäíóº ó ñîá³ ³äå¿ äâîåòàïíîãî ïðîêñèìàëüíîãî ìåòîäó, àäàïòèâíîñò³ òà
³òåðàòèâíî¿ ðåãóëÿðèçàö³¿. Íà â³äì³íó â³ä ïðàâèë âèáîðó âåëè÷èíè êðîêó,
ùî çàñòîñîâóâàëèñÿ ðàí³øå, â çàïðîïîíîâàíîìó àëãîðèòì³ íå ïðîâîäèòüñÿ
îá÷èñëåíü çíà÷åíü á³ôóíêö³¿ â äîäàòêîâèõ òî÷êàõ òà íå ïîòð³áíî çíàííÿ
³íôîðìàö³¿ ïðî âåëè÷èíó ë³ïøèöåâèõ êîíñòàíò á³ôóíêö³¿, êîíñòàíò ë³ïøèöå-
âîñò³ òà ñèëüíî¿ ìîíîòîííîñò³ îïåðàòîðà. Äëÿ ìîíîòîííèõ á³ôóíêö³é ë³ïøè-
öåâîãî òèïó òà ñèëüíî ìîíîòîííèõ ë³ïøèöåâèõ îïåðàòîð³â äîâåäåíî òåîðå-
ìó ïðî ñèëüíó çá³æí³ñòü àëãîðèòìó. Ïîêàçàíî, ùî çàïðîïîíîâàíèé àëãîðèòì
ìîæíà çàñòîñóâàòè äî ìîíîòîííèõ äâîð³âíåâèõ âàð³àö³éíèõ íåð³âíîñòåé
â ã³ëüáåðòîâèõ ïðîñòîðàõ.
Êëþ÷îâ³ ñëîâà: äâîð³âíåâà çàäà÷à, âàð³àö³éíà íåð³âí³ñòü, çàäà÷à ïðî ð³âíî-
âàãó, äâîåòàïíèé ïðîêñèìàëüíèé ìåòîä, àäàïòèâí³ñòü, ³òåðàòèâíà ðåãóëÿðè-
çàö³ÿ, ñèëüíà çá³æí³ñòü.
Ya.I. Vedel, S.V. Denisov, V.V. Semenov
AN ADAPTIVE ALGORITHM FOR THE VARIATIONAL INEQUALITY OVER
THE SET OF SOLUTIONS OF THE EQUILIBRIUM PROBLEM
Àbstract. In this paper, we consider bilevel problems: variational inequality
problems over the set of solutions of the equilibrium problem. An example of
such a problem is finding a normal Nash equilibrium. To solve these problems, an
iterative algorithm is proposed that combines the ideas of a two-stage proximal
method, adaptability, and iterative regularization. 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
information on bifunction’s Lipschitz constants and operator’s Lipschitz and strong
monotonicity constants. For monotone bifunctions of Lipschitz type and strongly
monotone Lipschitz operators, the theorem on strong convergence of sequences
generated by the algorithm is proved. It is shown that the proposed algorithm is
applicable to monotone bilevel variational inequalities in Hilbert spaces.
Keywords: bilevel problem, variational inequality, equilibrium problem, two-
stage proximal algorithm, adaptivity, iterative regularization, strong convergence.
Âåäåëü ßíà Èãîðåâíà,
àñïèðàíòêà Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: yana.vedel@gmail.com.
Äåíèñîâ Cåðãåé Âèêòîðîâè÷,
àññèñòåíò êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: sireukr@gmail.com.
Ñåìåíîâ Âëàäèìèð Âèêòîðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, e-mail: semenov.volodya@gmail.com.
114 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
|