Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств
Предложен новый двухэтапный метод для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами, который является модификацией нескольких известных двухэтапных алгоритмов с использованием расхождения Брэгмана вместо евклидового расстояния. Как и другие подобные схем...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/180865 |
| 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: | Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств / Д.А. Номировский, Б.В. Рублев, В.В. Семёнов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 17-27. — Бібліогр.: 23 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-180865 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1808652021-10-24T01:26:01Z Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств Номировский, Д.А. Рублев, Б.В. Семёнов, В.В. Системний аналіз Предложен новый двухэтапный метод для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами, который является модификацией нескольких известных двухэтапных алгоритмов с использованием расхождения Брэгмана вместо евклидового расстояния. Как и другие подобные схемы, данный метод в некоторых случаях позволяет явно учесть структуру допустимого множества задачи. Доказана теорема сходимости метода. Для монотонного оператора и выпуклого компактного допустимого множества получены неасимптотические оценки его эффективности. Запропоновано новий двоетапний метод для наближеного розв'язання варіаційних нерівностей з псевдомонотонними та ліпшицевими операторами, що є модифікацією декількох відомих двоетапних алгоритмів з використанням розбіжності Брегмана замість евклідової відстані. Як і інші подібні схеми, даний метод в деяких випадках дозволяє явно врахувати структуру допустимої множини задачі. Доведено теорему збіжності методу. Для монотонного оператора та опуклої компактної допустимої множини отримано неасимптотичні оцінки його ефективності. A new two-step method for the approximate solution of variational inequalities with pseudo-monotone and Lipschitz-continuous operators acting in a finite-dimensional linear normed space is proposed. This method is a modification of several previously studied two-stage algorithms using the Bregman divergence instead of the Euclidean distance. Like other schemes using Bregman divergence, the proposed method can sometimes efficiently take into account the structure of the feasible set of the problem. A theorem on the convergence of the method is proved and, in the case of a monotone operator and convex compact feasible set, non-asymptotic estimates of the efficiency of the method are obtained. 2019 Article Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств / Д.А. Номировский, Б.В. Рублев, В.В. Семёнов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 17-27. — Бібліогр.: 23 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/180865 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 |
2019 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/180865 |
| citation_txt |
Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств / Д.А. Номировский, Б.В. Рублев, В.В. Семёнов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 17-27. — Бібліогр.: 23 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT nomirovskijda shodimostʹdvuhétapnogometodasrashoždeniembrégmanadlâvariacionnyhneravenstv AT rublevbv shodimostʹdvuhétapnogometodasrashoždeniembrégmanadlâvariacionnyhneravenstv AT semënovvv shodimostʹdvuhétapnogometodasrashoždeniembrégmanadlâvariacionnyhneravenstv |
| first_indexed |
2025-07-15T21:12:41Z |
| last_indexed |
2025-07-15T21:12:41Z |
| _version_ |
1837748939441307648 |
| fulltext |
Ä.À. ÍÎÌÈÐÎÂÑÊÈÉ, Á.Â. ÐÓÁËÅÂ, Â.Â. ÑĄ̊ÍÎÂ
ÓÄÊ 517.988 ÑÕÎÄÈÌÎÑÒÜ ÄÂÓÕÝÒÀÏÍÎÃÎ ÌÅÒÎÄÀ
Ñ ÐÀÑÕÎÆÄÅÍÈÅÌ ÁÐÝÃÌÀÍÀ
ÄËß ÂÀÐÈÀÖÈÎÍÍÛÕ ÍÅÐÀÂÅÍÑÒÂ1
Àííîòàöèÿ. Ïðåäëîæåí íîâûé äâóõýòàïíûé ìåòîä äëÿ ïðèáëèæåííîãî ðå-
øåíèÿ âàðèàöèîííûõ íåðàâåíñòâ ñ ïñåâäîìîíîòîííûìè è ëèïøèöåâûìè
îïåðàòîðàìè, êîòîðûé ÿâëÿåòñÿ ìîäèôèêàöèåé íåñêîëüêèõ èçâåñòíûõ äâóõ-
ýòàïíûõ àëãîðèòìîâ ñ èñïîëüçîâàíèåì ðàñõîæäåíèÿ Áðýãìàíà âìåñòî åâêëè-
äîâîãî ðàññòîÿíèÿ. Êàê è äðóãèå ïîäîáíûå ñõåìû, äàííûé ìåòîä â íåêîòî-
ðûõ ñëó÷àÿõ ïîçâîëÿåò ÿâíî ó÷åñòü ñòðóêòóðó äîïóñòèìîãî ìíîæåñòâà çàäà-
÷è. Äîêàçàíà òåîðåìà ñõîäèìîñòè ìåòîäà. Äëÿ ìîíîòîííîãî îïåðàòîðà è
âûïóêëîãî êîìïàêòíîãî äîïóñòèìîãî ìíîæåñòâà ïîëó÷åíû íåàñèìïòîòè÷åñ-
êèå îöåíêè åãî ýôôåêòèâíîñòè.
Êëþ÷åâûå ñëîâà: âàðèàöèîííîå íåðàâåíñòâî, ïñåâäîìîíîòîííîñòü, ìîíî-
òîííîñòü, óñëîâèå Ëèïøèöà, äâóõýòàïíûé ìåòîä, ðàñõîæäåíèå Áðýãìàíà,
ñõîäèìîñòü.
ÂÂÅÄÅÍÈÅ
 ôîðìå âàðèàöèîííûõ íåðàâåíñòâ [1, 2] ìîæíî çàïèñàòü áîëüøîå êîëè÷åñòâî
àêòóàëüíûõ çàäà÷ èññëåäîâàíèÿ îïåðàöèé è ìàòåìàòè÷åñêîé ôèçèêè. Îñîáåííî
÷àñòî òàêèå íåðàâåíñòâà ïðèìåíÿþòñÿ â ìàòåìàòè÷åñêîé ýêîíîìèêå, ìàòåìàòè-
÷åñêîì ìîäåëèðîâàíèè òðàíñïîðòíûõ ïîòîêîâ è òåîðèè èãð [1, 2]. Äëÿ èõ ðå-
øåíèÿ ïðåäëîæåíî ìíîãî ìåòîäîâ, â ÷àñòíîñòè ïðîåêöèîííîãî òèïà (èñïîëüçóþ-
ùèõ îïåðàöèþ ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ íà äîïóñòèìîå ìíîæåñòâî) [1–17].
Íàèáîëåå èçâåñòíûì àíàëîãîì ìåòîäà ïðîåêöèè ãðàäèåíòà äëÿ âàðèàöèîííûõ
íåðàâåíñòâ ÿâëÿåòñÿ ýêñòðàãðàäèåíòíûé ìåòîä Ã.Ì. Êîðïåëåâè÷ [3]. Åãî îáîá-
ùåíèþ è èññëåäîâàíèþ ïîñâÿùåíî äîñòàòî÷íî ìíîãî ïóáëèêàöèé [4–6, 9–14].
 ÷àñòíîñòè, ïðåäëîæåíû ìîäèôèêàöèè àëãîðèòìà Êîðïåëåâè÷ ñ îäíèì ìåò-
ðè÷åñêèì ïðîåêòèðîâàíèåì íà äîïóñòèìîå ìíîæåñòâî [9–14].  òàê íàçûâàå-
ìûõ ñóáãðàäèåíòíûõ ýêñòðàãðàäèåíòíûõ àëãîðèòìàõ [9, 10, 13, 14] è àëãîðèò-
ìå Êîðïåëåâè÷ ïåðâûå ýòàïû èòåðàöèè ñîâïàäàþò, à äëÿ ïîëó÷åíèÿ ñëå-
äóþùåãî ïðèáëèæåíèÿ âìåñòî ïðîåêòèðîâàíèÿ íà äîïóñòèìîå ìíîæåñòâî åãî
îñóùåñòâëÿþò íà íåêîòîðîå îïîðíîå äëÿ äîïóñòèìîãî ìíîæåñòâà ïîëóïðîñòðàí-
ñòâî.  íà÷àëå 1980-õ ãîäîâ Ë.Ä. Ïîïîâ ïðåäëîæèë èíòåðåñíóþ ìîäèôèêàöèþ
àëãîðèòìà Ýððîó–Ãóðâèöà ïîèñêà ñåäëîâûõ òî÷åê âûïóêëî-âîãíóòûõ ôóíê-
öèé [15]. Â ðàáîòå [16] èññëåäîâàíà ìîäèôèêàöèÿ ìåòîäà Ïîïîâà äëÿ ðåøåíèÿ
âàðèàöèîííûõ íåðàâåíñòâ ñ ìîíîòîííûìè îïåðàòîðàìè. Â [18] ïðåäëîæåí äâóõ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 17
1Ðàáîòà âûïîëíåíà ïðè ÷àñòè÷íîé ôèíàíñîâîé ïîääåðæêå ÌÎÍ Óêðàèíû (ïðîåêò «Ðîçðîáêà
àëãîðèòì³â ìîäåëþâàííÿ òà îïòèì³çàö³¿ äèíàì³÷íèõ ñèñòåì äëÿ îáîðîíè, ìåäèöèíè òà åêîëî㳿»,
0116U004777).
� Ä.À. Íîìèðîâñêèé, Á.Â. Ðóáëåâ, Â.Â. Ñåì¸íîâ, 2019
ýòàïíûé ïðîêñèìàëüíûé àëãîðèòì äëÿ ðåøåíèÿ çàäà÷è ðàâíîâåñíîãî ïðîãðàì-
ìèðîâàíèÿ, ÿâëÿþùèéñÿ àäàïòàöèåé ìåòîäà [15] ê îáùèì íåðàâåíñòâàì Êè Ôàíÿ.
 áîëüøèíñòâå óêàçàííûõ ìåòîäîâ èñïîëüçóþòñÿ åâêëèäîâû ðàññòîÿíèå è
ïðîåêöèÿ.  íåêîòîðûõ ñëó÷àÿõ ýòî íå ïîçâîëÿåò ïðèìåíÿòü ñòðóêòóðó äîïóñòè-
ìûõ ìíîæåñòâ è ýôôåêòèâíî ðåøàòü çàäà÷è. Âîçìîæíûé âûõîä èç ñèòóàöèè ñî-
ñòîèò â áîëåå ãèáêîì ïîäáîðå ðàññòîÿíèÿ äëÿ îñóùåñòâëåíèÿ ïðîåêòèðîâàíèÿ íà
äîïóñòèìîå ìíîæåñòâî. Îäíîé èç ïåðâûõ óñïåøíûõ ðåàëèçàöèé òàêîé ñòðàòåãèè
ÿâëÿåòñÿ ðàáîòà Ë.Ì. Áðýãìàíà [19], â êîòîðîé ïðåäëîæåí ìåòîä òèïà öèêëè÷åñ-
êîãî ïðîåêòèðîâàíèÿ äëÿ íàõîæäåíèÿ îáùåé òî÷êè âûïóêëûõ ìíîæåñòâ. Äàííàÿ
ñòàòüÿ îòêðûëà öåëîå íàïðàâëåíèå â ìàòåìàòè÷åñêîì ïðîãðàììèðîâàíèè è íåëè-
íåéíîì àíàëèçå. Â êîíöå 1970-õ ãîäîâ À.Ñ. Íåìèðîâñêèì è Ä.Á. Þäèíûì äëÿ ðå-
øåíèÿ âûïóêëûõ çàäà÷ îïòèìèçàöèè áûë ïðåäëîæåí ìåòîä çåðêàëüíîãî
ñïóñêà [20], ïîëó÷èâøèé øèðîêîå ðàñïðîñòðàíåíèå äëÿ ðåøåíèÿ çàäà÷ áîëüøèõ
ðàçìåðíîñòåé.  ñëó÷àå çàäà÷ ñ îãðàíè÷åíèÿìè åãî ìîæíî ïðîèíòåðïðåòèðîâàòü
êàê âàðèàíò ìåòîäà ïðîåêöèè ñóáãðàäèåíòà, êîãäà ïðîåêòèðîâàíèå ïîíèìàåòñÿ
â ñìûñëå ðàñõîæäåíèÿ Áðýãìàíà [21]. Ìåòîä çåðêàëüíîãî ñïóñêà ïîçâîëÿåò ó÷èòû-
âàòü ñòðóêòóðó äîïóñòèìîãî ìíîæåñòâà çàäà÷è îïòèìèçàöèè. Íàïðèìåð, äëÿ ñèìï-
ëåêñà â êà÷åñòâå ðàññòîÿíèÿ ìîæíî èñïîëüçîâàòü ðàñõîæäåíèå Êóëüáàêà–Ëåéáëåðà
è ïîëó÷èòü ÿâíî âû÷èñëÿåìûé îïåðàòîð ïðîåêòèðîâàíèÿ íà ñèìïëåêñ [21]. Äëÿ âà-
ðèàöèîííûõ íåðàâåíñòâ îäíèì èç ñîâðåìåííûõ âàðèàíòîâ ýêñòðàãðàäèåíòíîãî
ìåòîäà ÿâëÿåòñÿ ïðîêñèìàëüíûé çåðêàëüíûé ìåòîä À.Ñ. Íåìèðîâñêîãî [4]. Ïî-
äîáíûå ìåòîäû ïîäðîáíî ðàññìîòðåíû â [5]. Èíòåðåñíûé ìåòîä äâîéñòâåííîé
ýêñòðàïîëÿöèè äëÿ ðåøåíèÿ âàðèàöèîííûõ íåðàâåíñòâ ïðåäëîæåí â [6]. Â ðàáî-
òå [17] èññëåäîâàí äâóõýòàïíûé ïðîêñèìàëüíûé çåðêàëüíûé ìåòîä, ÿâëÿþùèéñÿ
ìîäèôèêàöèåé äâóõýòàïíîãî ïðîêñèìàëüíîãî àëãîðèòìà [18] ñ èñïîëüçîâàíèåì
ðàñõîæäåíèÿ Áðýãìàíà âìåñòî åâêëèäîâîãî ðàññòîÿíèÿ.
Íàñòîÿùàÿ ñòàòüÿ ïðîäîëæàåò ðàáîòó [22] è ïîñâÿùåíà èçó÷åíèþ íîâîãî
äâóõýòàïíîãî ìåòîäà äëÿ ïðèáëèæåííîãî ðåøåíèÿ âàðèàöèîííûõ íåðàâåíñòâ
ñ ïñåâäîìîíîòîííûìè è ëèïøèöåâûìè îïåðàòîðàìè, îïðåäåëåííûìè â êîíå÷íî-
ìåðíîì ëèíåéíîì íîðìèðîâàííîì ïðîñòðàíñòâå. Äàííûé ìåòîä — ìîäèôèêàöèÿ
îïèñàííûõ ðàíåå äâóõýòàïíûõ àëãîðèòìîâ [16, 18]. Ïðåäëàãàåìóþ ñõåìó ìîæíî
ïîëó÷èòü òàêæå çàìåíîé äîïóñòèìîãî ìíîæåñòâà ñïåöèàëüíûìè îïîðíûìè äëÿ
íåãî ïîëóïðîñòðàíñòâàìè íà ïåðâîì ýòàïå ïðîêñèìàëüíîãî çåðêàëüíîãî ìåòîäà [17].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ
Ïóñòü E — êîíå÷íîìåðíîå äåéñòâèòåëüíîå ëèíåéíîå ïðîñòðàíñòâî ñ íîðìîé
| | | |� (íå îáÿçàòåëüíî åâêëèäîâîé). Äâîéñòâåííîå ïðîñòðàíñòâî îáîçíà÷èì E * .
Äëÿ a E� * è b E� îáîçíà÷èì ( , )a b çíà÷åíèå ëèíåéíîé ôóíêöèè a â òî÷êå b.
Äâîéñòâåííóþ íîðìó | | | |
*
� íà E * îïðåäåëèì ñòàíäàðòíûì ñïîñîáîì:
| | | | max ( , ): | | | |
*
a a b b� �{ }1 , îáåñïå÷èâàþùèì âûïîëíåíèå íåðàâåíñòâà Øâàðöà
( , ) | | | | | | | |
*
a b a b� äëÿ âñåõ a E� * , b E� .
Ïóñòü C — íåïóñòîå ïîäìíîæåñòâî ïðîñòðàíñòâà E, A — îïåðàòîð, äåéñòâó-
þùèé èç E â E * . Ðàññìîòðèì âàðèàöèîííîå íåðàâåíñòâî: íàéòè
x C� : ( , )Ax y x� � 0 �y C , (1)
ìíîæåñòâî ðåøåíèé êîòîðîãî îáîçíà÷èì S .
Ïðåäïîëîæèì, ÷òî âûïîëíåíû ñëåäóþùèå óñëîâèÿ:
ìíîæåñòâî C E� âûïóêëîå è çàìêíóòîå;
îïåðàòîð A E E: *� ïñåâäîìîíîòîííûé è ëèïøèöåâûé ñ êîíñòàíòîé L
0
íà C;
ìíîæåñòâî S íå ïóñòî.
18 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
Çàìå÷àíèå 1. Íàïîìíèì, ÷òî ïñåâäîìîíîòîííîñòü îïåðàòîðà A íà ìíîæåñ-
òâå C çàêëþ÷àåòñÿ â òîì, ÷òî äëÿ âñåõ x, y C� èç ( , )Ax y x� � 0 ñëåäóåò
( , )Ay y x� � 0.
Ðàññìîòðèì äóàëüíîå âàðèàöèîííîå íåðàâåíñòâî: íàéòè
x C� : ( , )Ay x y� � 0 �y C . (2)
Ìíîæåñòâî ðåøåíèé (2) îáîçíà÷èì S d . Çàìåòèì, ÷òî ìíîæåñòâî S d âûïóêëîå
è çàìêíóòîå. Íåðàâåíñòâî (2) èíîãäà íàçûâàþò ñëàáîé èëè äóàëüíîé ïîñòàíîâ-
êîé (1), à ðåøåíèÿ (2) — ñëàáûìè ðåøåíèÿìè (1) [1]. Äåéñòâèòåëüíî, ïðè
ïñåâäîìîíîòîííîñòè îïåðàòîðà A èìååì S S d� . Â ðàññìàòðèâàåìûõ óñëîâèÿõ
S Sd � [1].
Ââåäåì íåîáõîäèìûå äëÿ ôîðìóëèðîâêè àëãîðèòìà êîíñòðóêöèè. Ïóñòü
ôóíêöèÿ �:E � � � ��� � { } óäîâëåòâîðÿåò óñëîâèÿì:
int dom � � E — íåïóñòîå âûïóêëîå ìíîæåñòâî;
� íåïðåðûâíî äèôôåðåíöèðóåìà íà int dom �;
åñëè int dom bd dom� �� � �x xn , òî | | ( )| |
*
� � ��� xn ;
� ñèëüíî âûïóêëà îòíîñèòåëüíî íîðìû || | |� ñ êîíñòàíòîé ñèëüíîé âûïóê-
ëîñòè �
0:
� � �
�
( ) ( ) ( ( ), ) | | | |a b b a b a b� � � � � �
2
2 �a dom �, b� int dom �.
Çàìå÷àíèå 2. Ôóíêöèè � ïðèíÿòî íàçûâàòü distance generating functions.
Ñîîòâåòñòâóþùåå ôóíêöèè � ðàñõîæäåíèå Áðýãìàíà çàäàåòñÿ ôîðìóëîé [21]
V a b a b b a b( , ) ( ) ( ) ( ( ), )� � � � �� � � �à dom �, b� int dom �.
Çàìå÷àíèå 3. Èíîãäà ðàñõîæäåíèå Áðýãìàíà íàçûâàþò ðàññòîÿíèåì [4, 21, 23],
íî ýòî íå ñîâñåì êîððåêòíîå îïðåäåëåíèå: èç àêñèîì ìåòðèêè äëÿ V â îáùåì
ñëó÷àå âûïîëíÿåòñÿ òîëüêî V x y( , ) � 0 � �x y.
Ïðèìåðû ïðàêòè÷åñêè âàæíûõ ðàñõîæäåíèé Áðýãìàíà ïðèâåäåíû â [21].
Ðàññìîòðèì çäåñü äâà îñíîâíûõ ïðèìåðà. Ïðè �( ) | | | |� � �
1
2 2
2 , ãäå | | | |� 2 — åâêëè-
äîâà íîðìà, èìååì V x y x y( , ) | | | |� �
1
2 2
2 . Äëÿ íåîòðèöàòåëüíîãî îðòàíòà
� �� � � �m m
ix x{ }: 0 è ôóíêöèè îòðèöàòåëüíîé ýíòðîïèè �( ) lnx x xi i
i
m
�
�
�
1
(ñèëüíî âûïóêëîé ñ êîíñòàíòîé 1 îòíîñèòåëüíî � 1-íîðìû íà ñèìïëåêñå
S x x xm
m
i ii
m� � � �
�
�
�
�
�
���� : ,0 1
1
) ïîëó÷àåì ðàñõîæäåíèå (ðàññòîÿíèå) Êóëüáà-
êà–Ëåéáëåðà
V x y x x y x yi i i i i
i
m
i
m
( , ) ln ( / ) ( )� � �
��
��
11
, x m� �� , y m m� �� �� �= int ( ).
Èìååò ìåñòî ïîëåçíîå 3-òî÷å÷íîå òîæäåñòâî [21]
V a c V a b V b c b c a b( , ) ( , ) ( , ) ( ( ) ( ), )� � � � �� �� � . (3)
Èç ñèëüíîé âûïóêëîñòè ôóíêöèè � ñëåäóåò îöåíêà
V a b a b( , ) | | | |� �
�
2
2 �a dom �, b� int dom �.
(4)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 19
Ïóñòü K � dom � — íåïóñòîå çàìêíóòîå âûïóêëîå ìíîæåñòâî, ïðè÷åì
K � ��int dom � . Ðàññìîòðèì ñèëüíî âûïóêëûå çàäà÷è ìèíèìèçàöèè âèäà
P a a y x V y xx
K
y K( ) min ( , ) ( , )� � � ��arg { } �a E * , x � int dom �. (5)
Èçâåñòíî [4, 21], ÷òî çàäà÷à (5) èìååò åäèíñòâåííîå ðåøåíèå
z K� � int dom �, ïðè÷åì
� � � � �� � �( , ) ( ( ) ( ), )a y z z x y z� � 0 �y K . (6)
Çàìå÷àíèå 4. Òî÷êà P ax
K ( ) â åâêëèäîâîì ñëó÷àå ñîâïàäàåò ñ åâêëèäîâîé
ìåòðè÷åñêîé ïðîåêöèåé P x a y x aK y K( ) arg min | | ( )| |� � � �� 2 .
Çàìå÷àíèå 5. Äëÿ ñèìïëåêñà S x x xm
m
i ii
m� � � �
�
�
�
�
�
���� : ,0 1
1
è ðàñõîæäå-
íèÿ Êóëüáàêà–Ëåéáëåðà èìååì [21]
P a
x e
x e
x e
x e
x e
x e
x
S
a
j
a
j
m
a
j
a
j
m
m
a
j
m
j j
m
( ) , , ,�
� �� �
1
1
2
1
1 2
�
a
j
m j
��
�
�
!
"
#
#
#
1
, a m�� , x S m�ri ( ).
Äëÿ ñëó÷àÿ ïîëóïðîñòðàíñòâà H b y b y� � �( , ) : ( , )� �{ }, ãäå b E� * \ { }0 ,
� �� , èìååì [23]
P a x ax
H b� � � � ��( , )
( ) ( ) ( ( ) )
� � �1 ,
åñëè ( ) ( ( ) ) ( , )� � � ��
�� � �1 x a H b , èíà÷å
P a x a bx
H b� � � � � ��( , )
( ) ( ) ( ( ) )
� � � �1 ,
ãäå � � � �� � � � �
arg min ( ( ) )*
t x a tb t0 , �* — ñîïðÿæåííàÿ ê � ôóíêöèÿ, ò.å.
� ��
* ( ) sup (( , ) ( ))y y x xx� ��dom .
Îïèøåì àëãîðèòì äëÿ ðåøåíèÿ âàðèàöèîííîãî íåðàâåíñòâà (1).
Àëãîðèòì 1. Äâóõýòàïíûé ìåòîä ñ ðàñõîæäåíèåì Áðýãìàíà. Âûáèðàåì
ýëåìåíòû x0 , y C0 � è ïîëîæèòåëüíîå ÷èñëî �. Ïîëàãàåì n �1.
Øàã 0. Âû÷èñëèòü
x P Ay
x
C
1 0
0
� �( )� , y P Ay
x
C
1 0
1
� �( )� .
Øàã 1. Âû÷èñëèòü x P Ayn x
T
n
n
n
� � �1 ( )� , y P Ayn x
C
n
n
� � �
�
1
1
( )� ,
ãäå
T z E x Ay y z yn n n n n� � � � �� � ��{ }: ( ( ) ( ), )� � �1 0 .
Øàã 2. Åñëè x xn n� �1 è y y yn n n� �� �1 1, òî ÑÒÎÏ è y Sn � , èíà÷å ïîëî-
æèòü n n:� �1 è ïåðåéòè íà øàã 1.
Çàìå÷àíèå 6. Èìååì C Tn� . Äåéñòâèòåëüíî, åñëè ïðåäïîëîæèòü ñóùåñòâî-
âàíèå òî÷êè w C Tn� \ , òî íåðàâåíñòâî
( ( ) ( ), )� � �� �
�� � �x Ay y w yn n n n1 0
ïðîòèâîðå÷èò ðàâåíñòâó y P Ayn x
C
n
n
� � �( )� 1 .
20 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
Çàìå÷àíèå 7. Åñëè �( ) | | | |� � �
1
2 2
2 , òî àëãîðèòì 1 ïðèíèìàåò âèä ìåòîäà,
ïðåäëîæåííîãî â [16]:
T z H x Ay y z y
x P x Ay
y
n n n n n
n T n nn
� � � � � �
� �
�
�
{ : ( , ) ,
( ),
�
�
1
1
0}
n C n nP x Ay� �� �
�
�
$
�
$
1 1( ).�
Èìååò ìåñòî ñëåäóþùàÿ ëåììà.
Ëåììà 1. Åñëè äëÿ íåêîòîðîãî n�� â àëãîðèòìå 1 èìååì x xn n� �1 è
y y yn n n� �� �1 1, òî y Sn � .
Äîêàçàòåëüñòâî. Ðàâåíñòâî x P Ayn x
T
n
n
n
� � �1 ( )� â ñèëó (6) ðàâíîñèëüíî
íåðàâåíñòâó
( , )
( ( ) ( ), )
Ay y x
x x y y
n n
n n n� �
� �� �
��
�
1
1 0
� �
�
�y Tn .
Èç ðàâåíñòâà x xn n� �1 ñëåäóåò
( , )Ay y xn n� � 0 �y Tn . (7)
Ó÷èòûâàÿ x Tn n� �1 è y yn n� �1, ïîëó÷àåì ( ( ) ( ), )� � �� � �� � �x Ay y x yn n n n n 0,
îòêóäà èìååì ( , )Ay x yn n n� � 0. Ïðåäñòàâèì (7) â âèäå
( , ) ( , )Ay y y Ay x yn n n n n� � � � 0 �y Tn .
Ñëåäîâàòåëüíî,
( , ) ( , )Ay y y Ay x yn n n n n� � � � 0 �y Tn .
Ïîñêîëüêó y C Tn n� � , èìååì y Sn � . �
Äàëåå áóäåì ïðåäïîëàãàòü, ÷òî äëÿ âñåõ íîìåðîâ n�� óñëîâèå îñòàíîâêè íà
øàãå 2 àëãîðèòìà 1 íå èìååò ìåñòà, è ïåðåéäåì ê îáîñíîâàíèþ ñõîäèìîñòè
àëãîðèòìà 1.
ÎÑÍÎÂÍÎÅ ÍÅÐÀÂÅÍÑÒÂÎ ÄËß ÒÎ×ÅÊ, ÏÎÐÎÆÄÅÍÍÛÕ ÀËÃÎÐÈÒÌÎÌ
Âíà÷àëå äîêàæåì âàæíóþ îöåíêó, ñâÿçûâàþùóþ ðàñõîæäåíèÿ Áðýãìàíà ìåæ-
äó ïîðîæäåííîé äâóõýòàïíûì àëãîðèòìîì 1 òî÷êîé xn è ïðîèçâîëüíûì ýëå-
ìåíòîì ìíîæåñòâà ðåøåíèé S .
Ëåììà 2. Äëÿ ïîñëåäîâàòåëüíîñòåé ( )xn , ( )yn , ïîðîæäåííûõ àëãîðèòìîì 1,
èìååò ìåñòî íåðàâåíñòâî
V z x V z x
L
V y xn n n n( , ) ( , ) ( ) ( , )� � � � �
�
�
!
"
# �1 1 1 2
�
�
� �
�
�
!
"
# �� �1 2 1 1
�
�
�
�
L
V x y
L
V x yn n n n( , ) ( , ), (8)
ãäå z S� .
Äîêàçàòåëüñòâî. Ïóñòü z S� . Çàïèøåì 3-òî÷å÷íîå òîæäåñòâî (3) â âèäå
V z x V z x V x x x x xn n n n n n n( , ) ( , ) ( , ) ( ( ) ( ),� � � �� � � � ��1 1 1 1� � � z). (9)
Èç îïðåäåëåíèÿ òî÷êè xn�1 è z S Tn� � ñëåäóåò
� � �( , ) ( ( ) ( ), )Ay z x x x z xn n n n n� � � �� � �� � �1 1 1 0. (10)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 21
Èñïîëüçóÿ íåðàâåíñòâà (10) äëÿ îöåíêè ñêàëÿðíîãî ïðîèçâåäåíèÿ â (9), ïîëó-
÷àåì
V z x V z x V x x Ay z xn n n n n n( , ) ( , ) ( , ) ( , )� � �� � � �1 1 1� . (11)
Èç ïñåâäîìîíîòîííîñòè A è y Cn � ñëåäóåò ( , )Ay z yn n� � 0. Ê ïðàâîé ÷àñòè
íåðàâåíñòâà (11) äîáàâèì ñëàãàåìîå �( , )Ay y zn n � . Ïîëó÷èì
V z x V z x V x x Ay y xn n n n n n n( , ) ( , ) ( , ) ( , )� � �� � � � �1 1 1�
� � � � � �� � � �V z x V x x Ay y x Ay Ay yn n n n n n n n( , ) ( , ) ( , ) ( ,1 1 1 1� � n nx� �1 ). (12)
Çàïèøåì ñëàãàåìîå �( , )Ay y xn n n� ��1 1 â âèäå
� � � �( , ) ( ( ) ( ), )Ay y x x Ay y x yn n n n n n n n� � � �� � � � �� � �1 1 1 1
� � �� ��( ( ) ( ), )� �y x x yn n n n1 .
Èç âêëþ÷åíèÿ x Tn n� �1 âûòåêàåò íåðàâåíñòâî
( ( ) ( ), )� � �� � �� �� � �x Ay y x yn n n n n1 1 0.
Ñëåäîâàòåëüíî, èìååì
� � �( , ) ( ( ) ( ), )Ay y x y x x yn n n n n n n� � �� � � �� �1 1 1 .
Èñïîëüçóÿ 3-òî÷å÷íîå òîæäåñòâî (3), ïîëó÷àåì
�( , ) ( , ) ( , ) ( , )Ay y x V x x V x y V y xn n n n n n n n n� � � �� � � �1 1 1 1 . (13)
Îöåíèâ ïðàâóþ ÷àñòü (12) ñ ïîìîùüþ (13), ïîëó÷èì íåðàâåíñòâî
V z x V z x V x y V y x Ay Ayn n n n n n n n( , ) ( , ) ( , ) ( , ) ( ,� � �� � � � �1 1 1� x yn n� �1 ). .(14)
Òåïåðü îöåíèì ñëàãàåìîå �( , )Ay Ay x yn n n n� �� �1 1 . Èìååì
� �( , ) | | | | | | | |
*
Ay Ay x y Ay Ay x yn n n n n n n n� � � �� � � � � �1 1 1 1
� � � � � �� � �� �L y y x y L y y xn n n n n n n| | | | | | | | | | | | | |1 1 1
21
2 2
1
2
� �
�
�
�
�
�
�
�1
2yn | |
� � � � � � �� �
� �L
y x x y
L
x yn n n n n n
2 2
2 2 2
2
1
2 2
1{ }| | | | ( )| | | | | | | | 2 �
� � �
�
� � �� �
�
�
�L
y x L x y
L
x yn n n n n n
2
1 2
2 2
1
2 2
1
2| | | | | | | | | | | | . (15)
Çäåñü âîñïîëüçîâàëèñü ýëåìåíòàðíûìè íåðàâåíñòâàìè
ab a b� �
�
�
2
2
2
2
2
1
2
, ( ) ( )a b a b� � � �2 2 22 2 2 .
Îöåíèâàÿ íîðìû â (15) ñ ïîìîùüþ íåðàâåíñòâà (4), èìååì
�
�
�
( , ) ( , )Ay Ay y x
L
V x yn n n n n n� � � �� � �1 1 1
� � � �
�
�
�
�
L
V y x
L
V x yn n n n( ) ( , ) ( , )1 2 2 1 .
(16)
Ïðèìåíèâ (16) â (14), ïîëó÷èì
V z x V z x V x y V y xn n n n n n( , ) ( , ) ( , ) ( , )� �� � � �1 1
22 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
� � � � �� �
�
�
�
�
�
�
L
V x y
L
V y x
L
V x yn n n n n n( , ) ( ) ( , ) ( , )1 11 2 2
� � �
�
�
!
"
# ��V z x
L
V x yn n n( , ) ( , )1 2 1
�
�
� � �
�
�
!
"
# � �1 1 2 1
�
�
�
�
L
V y x
L
V x yn n n n( ) ( , ) ( , ),
÷òî è òðåáîâàëîñü äîêàçàòü. �
Ïåðåéäåì ê äîêàçàòåëüñòâó ñõîäèìîñòè àëãîðèòìà 1.
ÑÕÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÀ 1
Äëÿ äîêàçàòåëüñòâà ñõîäèìîñòè àëãîðèòìà ïîòðåáóåòñÿ ýëåìåíòàðíàÿ ëåììà
î ÷èñëîâûõ ïîñëåäîâàòåëüíîñòÿõ.
Ëåììà 3. Ïóñòü ( )an , ( )bn — ïîñëåäîâàòåëüíîñòè íåîòðèöàòåëüíûõ ÷èñåë,
óäîâëåòâîðÿþùèå íåðàâåíñòâó a a bn n n� � �1 äëÿ âñåõ n��. Òîãäà ñóùåñòâóåò
êîíå÷íûé ïðåäåë lim
n
na
��
è bn
n�
�
� % ��
1
.
Côîðìóëèðóåì îäèí èç îñíîâíûõ ðåçóëüòàòîâ äàííîé ðàáîòû.
Òåîðåìà 1. Ïóñòü ìíîæåñòâî C E� âûïóêëîå è çàìêíóòîå, îïåðàòîð
A E E: *� ïñåâäîìîíîòîííûé è ëèïøèöåâûé ñ êîíñòàíòîé L
0, S �� è
�
�
� �
�
�
!
"
#0 2 1, ( )
L
. Òîãäà ïîñëåäîâàòåëüíîñòè ( )xn è ( )yn , ïîðîæäåííûå àëãîðèò-
ìîì 1, ñõîäÿòñÿ ê íåêîòîðîé òî÷êå z S� .
Äîêàçàòåëüñòâî. Ïóñòü z S� . Ïîëîæèì
a V z x
L
V x yn n n n� � �( , ) ( , )
�
�
1 ,
b
L
V y x V x yn n n n n� � �
�
�
!
"
# � �1 1 2 1
�
�
( ) ( ( , ) ( , )).
Íåðàâåíñòâî (8) ïðèíèìàåò âèä a a bn n n� � �1 . Òîãäà èç ëåììû 3 î ÷èñëîâûõ
ïîñëåäîâàòåëüíîñòÿõ ñëåäóåò ñóùåñòâîâàíèå êîíå÷íîãî ïðåäåëà
lim ( , ) ( , )
n
n n nV z x
L
V x y
��
��
�
�
!
"
#
�
�
1 ,
1 1 2 1
1
� �
�
�
!
"
# � % ���
�
�
�
�
�
L
V y x V x yn n n n
n
( ) ( ( , ) ( , )) .
Îòñþäà ïîëó÷àåì
lim ( , ) lim ( , )
n
n n
n
n nV y x V x y
�� ��
�� �1 0 (17)
è ñõîäèìîñòü ÷èñëîâîé ïîñëåäîâàòåëüíîñòè ( ( , ))V z xn äëÿ âñåõ z S� . Èç (17)
âûòåêàåò
lim | | | | lim | | | |
n
n n
n
n ny x x y
�� ��
�� � � �1 0. (18)
Ñëåäîâàòåëüíî,
lim | | | |
n
n nx x
��
� � �1 0. (19)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 23
Èç íåðàâåíñòâà V z x z xn n( , ) | | | |� �
�
2
2 è (18) ñëåäóåò îãðàíè÷åííîñòü ïîñëåäî-
âàòåëüíîñòåé ( )xn , ( )yn .
Ðàññìîòðèì ïîäïîñëåäîâàòåëüíîñòü ( )xnk
, ñõîäÿùóþñÿ ê íåêîòîðîé òî÷êå
z E� . Òîãäà èç (18) ñëåäóåò, ÷òî y znk
� è x znk�
�1 , ïðè÷åì z C� . Ïîêàæåì,
÷òî z S� . Èìååì
( , ) ( ( ) ( ), )Ay y x x x y xn n n n nk k k k k
� � � �� � �� � �1 1 1
1
0
�
� � � �y C Tn . (20)
Âûïîëíèâ â (20) ïðåäåëüíûé ïåðåõîä ñ ó÷åòîì (18), (19), ïîëó÷èì ( , )Az y z� � 0
�y C, ò.å. z C� .
Ïîêàæåì, ÷òî x zn � (òîãäà èç | | | |x yn n� � 0 ñëåäóåò, ÷òî è y zn � ).
Èçâåñòíî, ÷òî ñóùåñòâóåò ïðåäåë
lim ( , ) lim ( ( ) ( ) ( ( ), ))
n
n
n
n n nV z x z x x z x
�� ��
� � � � �� � � .
Ïîñêîëüêó lim ( , )
n
nV z x
k��
� 0, èìååì òàêæå lim ( , )
n
nV z x
��
� 0, îòêóäà
| | | |x zn � � 0. �
ÎÖÅÍÊÀ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÀËÃÎÐÈÒÌÀ 1
Ðàññìîòðèì âàðèàöèîííîå íåðàâåíñòâî (1) ñ ìîíîòîííûì ëèïøèöåâûì îïåðà-
òîðîì A è âûïóêëûì êîìïàêòíûì ìíîæåñòâîì C. Ïîëó÷èì äëÿ ýòîãî ñëó÷àÿ
íåàñèìïòîòè÷åñêèå îöåíêè ýôôåêòèâíîñòè àëãîðèòìà 1.
Íàïîìíèì îäíî âàæíîå ïîíÿòèå. Ôóíêöèåé ðàçðûâà (gap function) íàçûâàþò
ôóíêöèþ âèäà
G x Ay x y
y C
( ) max ( , )� �
�
, x C� .
Ôóíêöèÿ ðàçðûâà âûïóêëà, íåîòðèöàòåëüíà è ïðèíèìàåò íóëåâîå çíà÷åíèå
â òî÷êå x C� òîãäà è òîëüêî òîãäà, êîãäà ýòà òî÷êà ïðèíàäëåæèò ìíîæåñòâó S [1].
Ôóíêöèÿ ðàçðûâà ÷àñòî ïðèìåíÿåòñÿ äëÿ îöåíêè êà÷åñòâà ïðèáëèæåííîãî ðå-
øåíèÿ âàðèàöèîííîãî íåðàâåíñòâà (1) [4, 6, 22].
Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Ïóñòü ìíîæåñòâî C E� âûïóêëîå è êîìïàêòíîå, îïåðàòîð
A E E: *� ìîíîòîííûé è ëèïøèöåâûé ñ êîíñòàíòîé L
0 è �
�
� �
�
�
!
"
#0 2 1, ( )
L
.
Òîãäà èìååò ìåñòî íåðàâåíñòâî
G z Ay z y
R x
L
V x y
N
N
y C
N
C
( ) max ( , )
( ) ( , )
� � �
�
�
1
1 1 0
� � ,
ãäå z
y
N
N
nn
N
� �� 1 — óñðåäíåííûé âûõîä ðàáîòû àëãîðèòìà 1, R xC ( )1 �
�
�
max ( , )
y C
V y x
1
.
Äîêàçàòåëüñòâî. Äëÿ ïðîèçâîëüíîãî ýëåìåíòà y C� èìååò ìåñòî íåðàâåíñòâî
V y x V y x V x x Ay y xn n n n n n( , ) ( , ) ( , ) ( , )� � �� � � �1 1 1� .
Èç ìîíîòîííîñòè îïåðàòîðà A ñëåäóåò
( , ) ( , ) ( , ) ( , ) (Ay y x Ay y y Ay y x Ay y y An n n n n n n n� � � � � � � �� �1 1 y y xn n n, )� �1 .
24 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
Òàêèì îáðàçîì,
V y x V y x V x x Ay y x Ay yn n n n n n n( , ) ( , ) ( , ) ( , ) ( ,� � �� � � � �1 1 1� � � �yn )
� � � � �� � �V y x V x x Ay y xn n n n n n( , ) ( , ) ( , )1 1 1�
� � � � �� �� �( , ) ( , )Ay Ay y x Ay y yn n n n n1 1 . (21)
Äàëåå, êàê è ïðè äîêàçàòåëüñòâå ëåììû 2, èç (21) ïîëó÷àåì íåðàâåíñòâî
V y x V y x
L
V y xn n n n( , ) ( , ) ( ) ( , )� � � � �
�
�
!
"
# �1 1 1 2
�
�
� �
�
�
!
"
# � � �� �1 2 1 1
�
�
�
�
�
L
V x y
L
V x y Ay y yn n n n n( , ) ( , ) ( , ).
(22)
Ïåðåïèøåì (22) â ñëåäóþùåì âèäå:
�
�
�
�
( , ) ( , ) ( , ) ( , )Ay y y V y x
L
V x y V y xn n n n n� � �
�
�
!
"
#� �� �1 1
L
V x yn n
�
( , )�
�
�
!
"
#�1
� � �
�
�
!
"
# � �1 1 2 1
�
�
L
V y x V x yn n n n( ) ( ( , ) ( , )) . (23)
Ñóììèðóÿ (23) ïî n îò 1 äî N , ïîëó÷àåì
�
�
�
( , ) ( , ) ( , ) ( ,Ay y y V y x
L
V x y V y xn
n
N
N� � �
�
�
!
"
#�
�
��
1
1 1 0 1 ) ( , )�
�
�
!
"
#��
�
�
L
V x yN N1
� � �
�
�
!
"
# � �
�
�1 1 2 1
1
�
�
L
V y x V x yn n n n
n
N
( ) ( ( , ) ( , )).
Îòñþäà ñëåäóåò
( , )
( , ) ( , )
Ay z y
V y x
L
V x y
N
N � �
�
1
1 1 0
� � ,
(24)
ãäå z
y
N
N
nn
N
� �� 1 . Ïåðåéäÿ â (24) ê ìàêñèìóìó ïî y C� , ïîëó÷èì
G z Ay z y
R x
L
V x y
N
N
y C
N
C
( ) max ( , )
( ) ( , )
� � �
�
�
1
1 1 0
� � ,
ãäå R x V y xC
y C
( ) max ( , )1 1
�
�
. �
Èç òåîðåìû 2 âûòåêàåò ñëåäñòâèå.
Ñëåäñòâèå 1. Ïóñòü íåîáõîäèìî ðåøèòü çàäà÷ó (1) ñ ïîìîùüþ àëãîðèòìà 1
ïðè �
�
�
3L
è �
0. Òîãäà ïîñëå
N
L
R x V x yC� �
&
''
(
))
1
3 1 1 0
� �
( ( ) ( , ))
èòåðàöèé èìååò ìåñòî ñëåäóþùàÿ îöåíêà:
G z Ay z yN
y C
N( ) max ( , )� � �
�
�,
ãäå z
y
N
N
nn
N
� �� 1 — óñðåäíåííûé âûõîä ðàáîòû àëãîðèòìà 1 çà N èòåðàöèé.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 25
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ïðåäëîæåí íîâûé äâóõýòàïíûé ìåòîä äëÿ ïðèáëèæåííîãî ðåøåíèÿ
âàðèàöèîííûõ íåðàâåíñòâ ñ ïñåâäîìîíîòîííûìè è ëèïøèöåâûìè îïåðàòîðàìè,
îïðåäåëåííûìè â êîíå÷íîìåðíîì ëèíåéíîì íîðìèðîâàííîì ïðîñòðàíñòâå.
Äàííûé ìåòîä ÿâëÿåòñÿ ìîäèôèêàöèåé íåñêîëüêèõ ðàíåå îïèñàííûõ äâóõýòàï-
íûõ àëãîðèòìîâ [16, 18] ñ ïðèìåíåíèåì ðàñõîæäåíèÿ Áðýãìàíà âìåñòî åâêëè-
äîâîãî ðàññòîÿíèÿ. Êàê è äðóãèå ñõåìû, èñïîëüçóþùèå ðàñõîæäåíèå Áðýãìàíà
[4–6, 17, 19–23], ïðåäëîæåííûé ìåòîä â íåêîòîðûõ ñëó÷àÿõ ïîçâîëÿåò ýôôåê-
òèâíî ïðèìåíÿòü ñòðóêòóðó äîïóñòèìîãî ìíîæåñòâà çàäà÷è, ò.å. ñòðîèòü ïî-
ñëåäîâàòåëüíîñòü ïðèáëèæåíèé ñ ïîìîùüþ ÿâíî âû÷èñëÿåìîãî îïåðàòîðà ïðî-
åêòèðîâàíèÿ íà äîïóñòèìîå ìíîæåñòâî.
Äîêàçàíà òåîðåìà ñõîäèìîñòè ìåòîäà. Äëÿ ñëó÷àÿ ìîíîòîííîãî îïåðàòîðà è
âûïóêëîãî êîìïàêòíîãî äîïóñòèìîãî ìíîæåñòâà ïîëó÷åíû íåàñèìïòîòè÷åñêèå
îöåíêè ýôôåêòèâíîñòè ìåòîäà.
Èíòåðåñ ïðåäñòàâëÿåò ïîñòðîåíèå àäàïòèâíîãî àíàëîãà ðàññìîðåííîãî ìåòî-
äà, ïîçâîëÿþùåãî ïîëó÷àòü àïïðîêñèìèðóþùèå ïîñëåäîâàòåëüíîñòè áåç çíàíèÿ
òî÷íîãî çíà÷åíèÿ êîíñòàíòû Ëèïøèöà îïåðàòîðà. Îòìåòèì òàêæå, ÷òî ïîÿâëå-
íèå ãåíåðèðóþùèõ ñîñòÿçàòåëüíûõ íåéðîííûõ ñåòåé (generative adversarial
network, GAN) îáóñëîâèëî èíòåðåñ ê àäàïòèâíûì àëãîðèòìàì ðåøåíèÿ âàðèàöè-
îííûõ íåðàâåíñòâ ñïåöèàëèñòîâ ïî ìàøèííîìó îáó÷åíèþ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Konnov I.V. Combined relaxation methods for variational inequalities. Berlin; Heidelberg; New
York: Springer-Verlag, 2001. 181 p.
2. Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic
Publishers, 1999. 325 p.
3. Êîðïåëåâè÷ Ã.Ì. Ýêñòðàãðàäèåíòíûé ìåòîä äëÿ îòûñêàíèÿ ñåäëîâûõ òî÷åê è äðóãèõ çàäà÷.
Ýêîíîìèêà è ìàò. ìåòîäû. 1976. Ò. 12, ¹ 4. Ñ. 747–756.
4. Nemirovski A. Prox-method with rate of convergence O t( / )1 for variational inequalities
with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.
SIAM Journal on Optimization. 2004. Vol. 15. P. 229–251.
5. Auslender A., Teboulle M. Interior projection-like methods for monotone variational inequalities.
Mathematical Programming. 2005. Vol. 104, Iss. 1. P. 39–68.
6. Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related
problems. Mathematical Programming. 2007. Vol. 109, Iss. 2–3. P. 319–344.
7. Íóðìèíñêèé Å.À. Èñïîëüçîâàíèå äîïîëíèòåëüíûõ ìàëûõ âîçäåéñòâèé â ôåéåðîâñêèõ ìîäåëÿõ èòåðà-
òèâíûõ àëãîðèòìîâ. Æóðíàë âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. 2008. T. 48, ¹ 12. Ñ. 2121–2128.
8. Ñåìåíîâ Â.Â. Î ìåòîäå ïàðàëëåëüíîé ïðîêñèìàëüíîé äåêîìïîçèöèè äëÿ ðåøåíèÿ çàäà÷ âû-
ïóêëîé îïòèìèçàöèè. Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2010. ¹ 2. Ñ. 42–46.
9. Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities
in Hilbert space. Journal of Optimization Theory and Applications. 2011. Vol. 148. P. 318–335.
10. Ëÿøêî Ñ.È., Ñåìåíîâ Â.Â., Âîéòîâà Ò.À. Ýêîíîìè÷íàÿ ìîäèôèêàöèÿ ìåòîäà Êîðïåëåâè÷ äëÿ
ìîíîòîííûõ çàäà÷ î ðàâíîâåñèè. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2011. ¹ 4. C. 146–154.
11. Ñåìåíîâ Â.Â. Ñèëüíî ñõîäÿùèéñÿ ìåòîä ðàñùåïëåíèÿ äëÿ ñèñòåìû îïåðàòîðíûõ âêëþ÷åíèé
ñ ìîíîòîííûìè îïåðàòîðàìè. Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2014. ¹ 3. Ñ. 22–32.
12. Ñåìåíîâ Â.Â. Ãèáðèäíûå ìåòîäû ðàñùåïëåíèÿ äëÿ ñèñòåìû îïåðàòîðíûõ âêëþ÷åíèé ñ ìîíî-
òîííûìè îïåðàòîðàìè. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014. Ò. 50, ¹ 5. C. 104–112.
13. Âåðëàíü Ä.À., Ñåìåíîâ Â.Â., ×àáàê Ë.Ì. Ñèëüíî ñõîäÿùèéñÿ ìîäèôèöèðîâàííûé ýêñòðàãðà-
äèåíòíûé ìåòîä äëÿ âàðèàöèîííûõ íåðàâåíñòâ ñ íåëèïøèöåâûìè îïåðàòîðàìè. Ïðîáëåìû
óïðàâëåíèÿ è èíôîðìàòèêè. 2015. ¹ 4. Ñ. 37–50.
14. Äåíèñîâ Ñ.Â., Ñåìåíîâ Â.Â., ×àáàê Ë.Ì. Ñõîäèìîñòü ìîäèôèöèðîâàííîãî ýêñòðàãðàäèåíòíî-
ãî ìåòîäà äëÿ âàðèàöèîííûõ íåðàâåíñòâ ñ íåëèïøèöåâûìè îïåðàòîðàìè. Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. 2015. Ò. 51, ¹ 5. Ñ. 102–110.
15. Ïîïîâ Ë.Ä. Ìîäèôèêàöèÿ ìåòîäà Ýððîó–Ãóðâèöà ïîèñêà ñåäëîâûõ òî÷åê. Ìàò. çàìåòêè.
1980. Ò. 28, ¹ 5. Ñ. 777–784.
26 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
16. Ìàëèöêèé Þ.Â., Ñåìåíîâ Â.Â. Âàðèàíò ýêñòðàãðàäèåíòíîãî àëãîðèòìà äëÿ ìîíîòîííûõ âàðè-
àöèîííûõ íåðàâåíñòâ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014. Ò. 50, ¹ 2. C. 125–131.
17. Ñåìåíîâ Â.Â. Âàðèàíò ìåòîäà çåðêàëüíîãî ñïóñêà äëÿ âàðèàöèîííûõ íåðàâåíñòâ. Êèáåðíåòè-
êà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 2. C. 83–93.
18. 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. Cham: Springer, 2016. Vol. 115. P. 315–325.
19. Áðýãìàí Ë.Ì. Ðåëàêñàöèîííûé ìåòîä íàõîæäåíèÿ îáùåé òî÷êè âûïóêëûõ ìíîæåñòâ è åãî
ïðèìåíåíèå äëÿ ðåøåíèÿ çàäà÷ âûïóêëîãî ïðîãðàììèðîâàíèÿ. Æóðí. âû÷èñë. ìàòåìàòèêè è
ìàò. ôèçèêè. 1967. ¹ 3. Ñ. 620–631.
20. Íåìèðîâñêèé À.Ñ., Þäèí Ä.Á. Ñëîæíîñòü çàäà÷ è ýôôåêòèâíîñòü ìåòîäîâ îïòèìèçàöèè. Ìîñ-
êâà: Íàóêà, 1979. 384 ñ.
21. Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied
Mathematics, 2017. 479 p.
22. Ñåìåíîâ Â.Â. Ìîäèôèöèðîâàííûé ýêñòðàãðàäèåíòíûé ìåòîä ñ ðàñõîæäåíèåì Áðýãìàíà äëÿ
âàðèàöèîííûõ íåðàâåíñòâ. Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2018. ¹ 4. Ñ. 43–53.
23. Lorenz D.A., Schopfer F., Wenger S. The linearized Bregman method via split feasibility problems.
Analysis and generalizations. SIAM Journal on Imaging Sciences. 2014. Vol. 7, Iss. 2. P. 1237–1262.
Íàä³éøëà äî ðåäàêö³¿ 06.07.2018
Ä.À. Íîì³ðîâñüêèé, Á.Â. Ðóáëüîâ, Â.Â. Ñåìåíîâ
ÇÁ²ÆͲÑÒÜ ÄÂÎÅÒÀÏÍÎÃÎ ÌÅÒÎÄÓ Ç ÐÎÇÁ²ÆͲÑÒÞ ÁÐÅÃÌÀÍÀ
ÄËß ÂÀвÀÖ²ÉÍÈÕ ÍÅвÂÍÎÑÒÅÉ
Àíîòàö³ÿ. Çàïðîïîíîâàíî íîâèé äâîåòàïíèé ìåòîä äëÿ íàáëèæåíîãî ðîçâ’ÿçàí-
íÿ âàð³àö³éíèõ íåð³âíîñòåé ç ïñåâäîìîíîòîííèìè òà ë³ïøèöåâèìè îïåðàòî-
ðàìè, ùî º ìîäèô³êàö³ºþ äåê³ëüêîõ â³äîìèõ äâîåòàïíèõ àëãîðèòì³â ç âèêî-
ðèñòàííÿì ðîçá³æíîñò³ Áðåãìàíà çàì³ñòü åâêë³äîâî¿ â³äñòàí³. ßê ³ ³íø³
ïîä³áí³ ñõåìè, öåé ìåòîä ó äåÿêèõ âèïàäêàõ äîçâîëÿº ÿâíî âðàõóâàòè ñòðóê-
òóðó äîïóñòèìî¿ ìíîæèíè çàäà÷³. Äîâåäåíî òåîðåìó çá³æíîñò³ ìåòîäó. Äëÿ
ìîíîòîííîãî îïåðàòîðà òà îïóêëî¿ êîìïàêòíî¿ äîïóñòèìî¿ ìíîæèíè îòðèìà-
íî íåàñèìïòîòè÷í³ îö³íêè éîãî åôåêòèâíîñò³.
Êëþ÷îâ³ ñëîâà: âàð³àö³éíà íåð³âí³ñòü, ïñåâäîìîíîòîíí³ñòü, ìîíîòîíí³ñòü,
óìîâà ˳ïøèöÿ, äâîåòàïíèé ìåòîä, ðîçá³æí³ñòü Áðåãìàíà, çá³æí³ñòü.
D.A. Nomirovskii, B.V. Rublyov, V.V. Semenov
CONVERGENCE OF TWO-STEP METHOD WITH BREGMAN DIVERGENCE FOR SOLVING
VARIATIONAL INEQUALITIES
Abstract. A new two-step method for the approximate solution of variational inequalities
with pseudo-monotone and Lipschitz-continuous operators acting in a finite- dimensional
linear normed space is proposed. This method is a modification of several
previously studied two-stage algorithms using the Bregman divergence instead of
the Euclidean distance. Like other schemes using Bregman divergence, the
proposed method can sometimes efficiently take into account the structure of the
feasible set of the problem. A theorem on the convergence of the method is
proved and, in the case of a monotone operator and convex compact feasible set,
non-asymptotic estimates of the efficiency of the method are obtained.
Keywords: variational inequality, pseudo-monotonicity, monotonicity, Lipschitz
condition, two-step method, Bregman divergence, convergence.
Íîìèðîâñêèé Äìèòðèé Àíàòîëèåâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, å-mail: kashpir74@gmail.com.
Ðóáëåâ Áîãäàí Âëàäèñëàâîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, å-mail: rublyovbv@gmail.com.
Ñåì¸íîâ Âëàäèìèð Âèêòîðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, å-mail: semenov.volodya@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 27
|