Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами

Запропоновано регуляризований модифікований екстраградієнтний метод з динамічним регулюванням величини кроку для розв’язання варіаційних нерівностей з монотонними операторами, що діють у гільбертовому просторі. Також розглянуто варіанти методу для варіаційних нерівностей та операторних рівнянь з апр...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблемы управления и информатики
Дата:	2015
Автори:	Верлань, Д.А., Семёнов, В.В., Чабак, Л.М.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/208018
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами / Д.А. Верлань, В.В. Семенов, Л.М. Чабак // Проблемы управления и информатики. — 2015. — № 4. — С. 37-50. — Бібліогр.: 37 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-208018
record_format	dspace
spelling	Верлань, Д.А. Семёнов, В.В. Чабак, Л.М. 2025-10-18T08:30:12Z 2015 Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами / Д.А. Верлань, В.В. Семенов, Л.М. Чабак // Проблемы управления и информатики. — 2015. — № 4. — С. 37-50. — Бібліогр.: 37 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208018 517.988 10.1615/JAutomatInfScien.v47.i7.40 Запропоновано регуляризований модифікований екстраградієнтний метод з динамічним регулюванням величини кроку для розв’язання варіаційних нерівностей з монотонними операторами, що діють у гільбертовому просторі. Також розглянуто варіанти методу для варіаційних нерівностей та операторних рівнянь з апріорною інформацією про розв’язок, що задана у вигляді множини нерухомих точок квазінерозтягуючого оператора. Доведено теореми про сильну збіжність методів без припущення про ліпшицевість операторів. Regularized modified extragradient method with dynamic rule for finding the step size for solving variational inequalities with monotone operators acting in a Hilbert space is presented. In addition the variants of this method for variational inequalities and operator equations with a priori information about solution which is given as the set of fixed points of quasi-nonexpansive operator. Strong convergence of methods without any Lipschitzian continuity assumption on operators is established. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами Сильно збіжний модифікований екстраградієнтний метод для варіаційних нерівностей з неліпшицевими операторами A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
spellingShingle	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами Верлань, Д.А. Семёнов, В.В. Чабак, Л.М. Оптимальное управление и методы оптимизации
title_short	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
title_full	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
title_fullStr	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
title_full_unstemmed	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
title_sort	сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами
author	Верлань, Д.А. Семёнов, В.В. Чабак, Л.М.
author_facet	Верлань, Д.А. Семёнов, В.В. Чабак, Л.М.
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
publishDate	2015
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Сильно збіжний модифікований екстраградієнтний метод для варіаційних нерівностей з неліпшицевими операторами A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators
description	Запропоновано регуляризований модифікований екстраградієнтний метод з динамічним регулюванням величини кроку для розв’язання варіаційних нерівностей з монотонними операторами, що діють у гільбертовому просторі. Також розглянуто варіанти методу для варіаційних нерівностей та операторних рівнянь з апріорною інформацією про розв’язок, що задана у вигляді множини нерухомих точок квазінерозтягуючого оператора. Доведено теореми про сильну збіжність методів без припущення про ліпшицевість операторів. Regularized modified extragradient method with dynamic rule for finding the step size for solving variational inequalities with monotone operators acting in a Hilbert space is presented. In addition the variants of this method for variational inequalities and operator equations with a priori information about solution which is given as the set of fixed points of quasi-nonexpansive operator. Strong convergence of methods without any Lipschitzian continuity assumption on operators is established.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/208018
citation_txt	Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами / Д.А. Верлань, В.В. Семенов, Л.М. Чабак // Проблемы управления и информатики. — 2015. — № 4. — С. 37-50. — Бібліогр.: 37 назв. — рос.
work_keys_str_mv	AT verlanʹda silʹnoshodâŝiisâmodificirovannyiékstragradientnyimetoddlâvariacionnyhneravenstvsnelipšicevymioperatorami AT semenovvv silʹnoshodâŝiisâmodificirovannyiékstragradientnyimetoddlâvariacionnyhneravenstvsnelipšicevymioperatorami AT čabaklm silʹnoshodâŝiisâmodificirovannyiékstragradientnyimetoddlâvariacionnyhneravenstvsnelipšicevymioperatorami AT verlanʹda silʹnozbížniimodifíkovaniiekstragradíêntniimetoddlâvaríacíinihnerívnosteiznelípšicevimioperatorami AT semenovvv silʹnozbížniimodifíkovaniiekstragradíêntniimetoddlâvaríacíinihnerívnosteiznelípšicevimioperatorami AT čabaklm silʹnozbížniimodifíkovaniiekstragradíêntniimetoddlâvaríacíinihnerívnosteiznelípšicevimioperatorami AT verlanʹda astronglyconvergentmodifiedextragradientmethodforvariationalinequalitieswithnonlipschitzoperators AT semenovvv astronglyconvergentmodifiedextragradientmethodforvariationalinequalitieswithnonlipschitzoperators AT čabaklm astronglyconvergentmodifiedextragradientmethodforvariationalinequalitieswithnonlipschitzoperators
first_indexed	2025-11-27T07:57:34Z
last_indexed	2025-11-27T07:57:34Z
_version_	1850807146794450944
fulltext	© Д.А. ВЕРЛАНЬ, В.В. СЕМЕНОВ, Л.М. ЧАБАК, 2015 Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 37 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 517.988 Д.А. Верлань, В.В. Семенов, Л.М. Чабак СИЛЬНО СХОДЯЩИЙСЯ МОДИФИЦИРОВАННЫЙ ЭКСТРАГРАДИЕНТНЫЙ МЕТОД ДЛЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ С НЕЛИПШИЦЕВЫМИ ОПЕРАТОРАМИ Введение Многие задачи управления и исследования операций могут быть записаны в виде вариационных неравенств: найти :Cx 0),(  xyxA ,Cy где C — непустое выпуклое подмножество гильбертова пространства H, A — монотонный оператор, действующий в H [1–3]. Решение вариационных нера- венств является активно развивающимся направлением прикладного анализа, и к настоящему времени предложено большое количество методов [4–30]. Извест- но, что в важных случаях (поиск седловой точки или равновесия Нэша) для схо- димости наиболее простого проекционного метода (аналога метода проекции гра- диента) необходимо выполнение усиленных условий монотонности [5, 6]. Для преодоления этой трудности существует несколько подходов. Один из них состо- ит в регуляризации исходной задачи с целью придать ей требуемое свойство [4]. Сходимость без модификации задачи обеспечивается в итерационных методах экстраградиентного типа, впервые предложенных Г.М. Корпелевич [19]. Экстра- градиентный алгоритм Корпелевич для липшицевого оператора A имеет вид:           ),( ),( , 1 0 nnCn nnCn AyxPx AxxPy Cx где )/1,0( L — постоянная Липшица оператора ,A CP — оператор метриче- ского проектирования на множество .C Обобщению и исследованию этого алго- ритма посвящено большое количество публикаций [20–30]. Недавно для вариаци- онных неравенств и задач равновесного программирования были предложены мо- дификации алгоритма Корпелевич с одним метрическим проектированием на допустимое множество [28, 29]. В так называемых субградиентных экстрагради- ентных алгоритмах первый этап итерации совпадает с первым этапом итерации в алгоритме Корпелевич. А далее для получения 1nx вместо проектирования точки 38 ISSN 0572-2691 nn Ayx  на допустимое множество C осуществляется ее проектирование на не- которое опорное для C полупространство. Субградиентный экстраградиентный алгоритм имеет вид:               ),( },0),(:{ ),( , 1 0 nnTn nnnnn nnCn AyxPx yzyAxxHzT AxxPy Hx n где )/1,0( L — постоянная Липшица оператора .A В [28, 29] доказана слабая сходимость порожденных этим алгоритмом последовательностей )( nx и )( ny к некоторому решению вариационного неравенства. Одним из недостатков cубградиентного экстраградиентного алгоритма, затрудняющим его широкое ис- пользование, является предположение о том, что константа Липшица L операто- ра A известна или допускает простую оценку. Кроме того, во многих задачах операторы могут не удовлетворять условию Липшица. Заметим, что в большинст- ве работ по алгоритмам решения вариационных неравенств рассматриваются именно липшицевые операторы. Кроме того, упомянутые методы генерируют слабо сходящиеся последовательности. В [22, 23] предложены и исследованы сильно сходящиеся модификации метода Корпелевич для неравенств с липшице- выми монотонными операторами. А в [30] с помощью гибридного метода [31] по- лучена сильно сходящаяся модификация cубградиентного экстраградиентного ал- горитма (также для липшицевых монотонных операторов). В данной работе предлагается сильно сходящийся модифицированный экст- раградиентный метод с динамической регулировкой величины шага для решения вариационных неравенств с монотонными нелипшицевыми операторами, дейст- вующими в гильбертовом пространстве, и доказывается его сходимость к реше- нию, ближайшему к заданной точке. Используемая нами регулировка величины шага взята из [20, 21], а для регуляризации применяется схема Гальперна [32, 33]. Также рассмотрены варианты метода для вариационных неравенств и оператор- ных уравнений с априорной информацией о решении, заданной в виде множества неподвижных точек квазинерастягивающего оператора. 1. Постановка задачи и вспомогательные сведения Далее H — действительное гильбертово пространство со скалярным произ- ведением ),(  и порожденной нормой  . Пусть C — непустое подмножество пространства ,H A — оператор, действующий в .H Рассмотрим вариационное неравенство: найти :Cx 0),(  xyAx .Cy (1) Множество решений вариационного неравенства (1) обозначим ).,( CAVI Далее предположим, что выполнены следующие условия:  множество HC  — выпуклое и замкнутое;  оператор HHA : — монотонный, равномерно непрерывный на ограни- ченных множествах и отображающий ограниченные множества в ограниченные;  .),( CAVI Замечание 1. Если Hdim , то достаточно требовать от оператора A мо- нотонности и непрерывности. Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 39 Пусть CP — оператор метрического проектирования на множество ,C т.е. xPC — единственный элемент множества C со свойством xzxxP Cz C   min . Полезны следующие характеризации элемента :xPC xPy C тогда и только тогда, когда Cy и 0),(  yzxy .Cz  (2) Из неравенства (2) следует, что ),( CAVIx тогда и только тогда, когда ),( AxxPx C  где 0 [4]. Если оператор HHA : — монотонный и непре- рывный, а множество C — выпуклое и замкнутое, то ),( CAVIx тогда и только тогда, когда Cx и 0),(  xyAy для всех Cy [4]. В частности, множество ),( CAVI выпуклое и замкнутое. Напомним, что оператор HHT : называют квазинерастягивающим (фей- еровским), если  }:{)( xTxHxTF и yxyTx  для всех ,Hx )(TFy [34]. Заметим, что множество неподвижных точек  TF квазинерастя- гивающего оператора замкнуто и выпукло [34]. Оператор HCS : называют демизамкнутым в ,Hy если для последовательности точек Cxn  из xxn  слабо и ySxn  сильно следует ySx  [6]. Известно, что для нерастягивающего оператора HCT : оператор TI  демизамкнут в нуле [6]. Следующие факты играют важную роль в доказательстве основного резуль- тата работы. Лемма 1 [35]. Пусть числовая последовательность )( na имеет подпоследова- тельность )( kna со свойством 1 kk nn aa для всех .k Тогда существует та- кая неубывающая последовательность )( km натуральных чисел, что km и ,1 kk mm aa 1 kmk aa для всех .1nk  Замечание 2. Лемма 1 является эффективным инструментом исследования сходимости итерационных процессов, не обладающих фейеровским свойством относительно множества решений [18, 26, 35–37]. Лемма 2 [4]. Пусть )( na — последовательность неотрицательных чисел, удовлетворяющих неравенству nnnnn aa  )1(1 для всех ,n где по- следовательности )( n и )( n обладают свойствами ),1,0(n    n n 1 , .0lim   n n Тогда .0lim   n n a Рассмотрим функцию )( tAxxPxt C  , ,t обладающую следующим полезным свойством. Лемма 3. Для Hx и 0 имеют место неравенства , )()(      AxxPxAxxPx CC )()( AxxPxAxxPx CC  . Доказательство. Положим ),( AxxPx C  ).( AxxPx C  Из (2) следует ,0,            xx Axxx .0,              xx Axxx 40 ISSN 0572-2691 Сложив неравенства, получим .)()(,,0                                  xxxx xxxx xx xxxx Отсюда         xxxxxxxxxxxx 22 0 . Следовательно, ).(0            xxxxxxxx Отсюда следует 0     xxxx и   xxxx , что и требовалось доказать. ■ 2. Регуляризованный модифицированный экстраградиентный алгоритм Для решения неравенства (1) предлагаем следующий алгоритм. Алгоритм 1. Инициализация. Задаем числовые параметры ,0 ),1,0( ),1,0( элемент Hx 0 и последовательность )1,0()( n такую, что ,0lim   n n   1n n . Итерационный шаг. Для Hxn  вычисляем ),( nnnCn AxxPy  где n получаем из условия       . },)()(:0{min)( )(nj n nn j nCnn j nC j xAxxPAxAxxAPjnj (3) Вычисляем ),()1(01 nnnTnnn AyxPxx n  где }.0),(:{  nnnnnn yzyAxxHzT Замечание 3. Динамическая регулировка величины шага — правило (3) — введена в [20, 21]. Прежде всего покажем, что процедура (3) всегда оканчивается за конечное число шагов. Лемма 4. Правило (3) выбора параметра n корректно, т.е. )(nj . Доказательство. Пусть ).,( CAVIxn  Тогда )( nnCn AxxPx  и .0)( nj Рассмотрим ситуацию ),( CAVIxn  и предположим, что для всех j выпол- няется неравенство nn j nCnn j nC j xAxxPAxAxxAP  )()( . Отсюда .0)(lim   nn j nC j xAxxP Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 41 Из равномерной непрерывности оператора A на ограниченных множествах следует .0)(lim   nn j nC j AxAxxAP Таким образом, .0 )( lim     j nn j nC j xAxxP (4) Положим ).( n j nC j n AxxPy  Имеем 0),(,             j nn j nj n j n yxAxyx xy .Cx (5) Совершив предельный переход в (5) с учетом (4), получим 0),(  nn xxAx ,Cx т.е. ).,( CAVIxn  В результате приходим к противоречию. ■ Замечание 4. При доказательстве леммы 4 вообще не использовалась моно- тонность оператора .A 3. Вспомогательные неравенства Положим ).( nnnTn AyxPz n  (6) Имеет место лемма. Лемма 5. Для последовательностей ),( nx )( ny и ),( nz порожденных алго- ритмом 1, имеет место неравенство ,)1()1( 2222 nnnnnn yzyxzxzz  (7) где ).,( CAVIz Доказательство. Приводя рассуждения из [28, доказательство леммы 3], приходим к неравенству  2 zzn  2 zxn  2 nn yx  2 nn zy ).,(2 nnnnn yzAyAx  (8) Слагаемое ),(2 nnnnn yzAyAx  в (8) оценим следующим образом  nnnnnnnnnn yzAyAxyzAyAx 2),(2 .2 22 nnnnnnnn yzyxyzyx  (9) Учитывая оценку (9) в (8), приходим к желаемому неравенству (7). ■ Лемма 6. Для порожденных алгоритмом 1 последовательностей ),( nx )( ny и )( nz имеет место неравенство  2 1 zxn  222 )1()1( nnnnn yzyxzx ),(2 10 zxzx nn   . где ).,( CAVIz Доказательство. Пусть ).,( CAVIz Применим элементарное неравенство ).,(2 22 bababa  Имеем  222 0 2 1 )1())(1()( zzzzzxzx nnnnnn   2 10 ),(2 zzzxzx nnn ),(2 10 zxzx nn   . (10) Учитывая в (10) неравенство (7), приходим к желаемой оценке. ■ 42 ISSN 0572-2691 Перейдем к доказательству сильной сходимости алгоритма 1. 4. Сильная сходимость алгоритма 1 Сначала докажем ограниченность порожденных алгоритмом последова- тельностей. Лемма 7. Порожденные алгоритмом 1 последовательности ),( nx )( ny и )( nz ограниченны. Доказательство. Пусть ).,( CAVIz Имеем  zzxzx nnnn )1(01   zzzxzzzx nnnnnn  )1())(1( 00 . Воспользовавшись неравенством леммы 5, получим  zxn 1 }.,{max)1( 00 zxzxzxzx nnnn  Следовательно,  zxn 1 },{max 10 zxzx  n . Таким образом, последовательность )( nx ограниченна. Ограниченность последовательностей )( ny и )( nz следует из ограниченно- сти )( nx и леммы 5. ■ Имеет место следующая теорема. Теорема 1. Пусть множество HC  — выпуклое и замкнутое, оператор HHA : — монотонный, равномерно непрерывный на ограниченных множе- ствах и отображающий ограниченные множества в ограниченные. Предположим, что ),( CAVI . Тогда последовательности ),( nx )( ny и ),( nz порожденные ал- горитмом 1, сильно сходятся к точке .0),(0 xPz CAVI Доказательство. Рассмотрим элемент .0),(0 xPz CAVI Из леммы 7 следует существование такого числа ,0M что Mzxzx n   ),( 0100 для всех n . Тогда из неравенства леммы 6 получим оценку  2 01 zxn  222 0 )1()1( nnnnn yzyxzx .2 Mn (11) Рассмотрим числовую последовательность ).( 0zxn  Возможны два варианта: a) существует номер n такой, что 001 zxzx nn  для всех ;nn  б) существует возрастающая последовательность номеров )( kn такая, что 001 zxzx kk nn  для всех k . Сначала рассмотрим вариант a). В этом случае существует   0lim zxn n . Поскольку 0 2 0 2 01  zxzx nn и ,0n то при n имеем ,0 nn yx (12) .0 nn yz (13) Из ограниченности )( nx следует существование подпоследовательности ),( knx слабо сходящейся к точке .Hw Из (12) следует, что wy kn  слабо. Следовательно, .Cw Покажем, что обязательно ).,( CAVIw Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 43 Возможны два варианта: 1) числовая последовательность )( kn не стремится к нулю; 2) .0lim   kn k Сначала рассмотрим вариант 1). Можно считать, что  kn для всех доста- точно больших k и некоторого .0 Имеем 0),(  kkkkk nnnnn yxAxxy .Cx Отсюда, используя монотонность оператора ,A выводим оценку        ),( ),(),( 0 kkk k kkk k kkkkk nnn n nnn n nnnnn yxAx yxxyyxAxxy ).,(),( ),( ),( kkkk k kkk kk nnnn n nnn nn xxAxyxAx yxxy xxAx     Совершив предельный переход с учетом (12), получим 0),( wxAx .Cx Следовательно, ).,( CAVIw Рассмотрим вариант 2). Пусть .0lim   kn k Положим ),( kkkk nnnCn AxxPw  где .0 1)(1   k k kk n nj nn Применим лемму 3. Имеем .0 1    kkkk nnnn yxwx В частности, последовательность )( knw ограниченна и ww kn  слабо. Из равномерной непрерывности оператора A на ограниченных множествах сле- дует .0 kk nn AwAx А неравенство kkkkk nnnnn xwAxAw  вле- чет асимптотику .0   k kk n nn wx (14) Далее имеем 0),(  kkkkk nnnnn wxAxxw .Cx Отсюда выводим оценку ).,(),( ),( 0 kkkk k kkk nnnn n nnn xxAxwxAx wxxw     Совершив предельный переход с учетом (14), получим 0),(  wxAx ,Cx отсюда ).,( CAVIw Докажем, что .0),(lim 0100    zxzx n n (15) Рассмотрим такую подпоследовательность ),( knx что ).,(lim),(lim 0100000 zxzxzxzx n n n k k    44 ISSN 0572-2691 Можно считать, что ),( CAVIwx kn  слабо. Тогда получаем ,0),(),(),(lim 0),(0),(0000000   xPwxPxzwzxzxzx CAVICAVIn k k чем и доказываем (15). Теперь из (15), оценки  2 0 22 000 2 01 )1())(1()( zzzzzxzx nnnnnn   2 00100 )1(),(2 zxzxzx nnnn ),(2 0100 zxzx nn   и леммы 2 делаем вывод, что .00  zxn Из (12), (13) получаем 00  zyn и .00  zzn Изучим вариант б). В этом случае рассмотрим последовательность номеров )( km со следующими свойствами (лемма 1): i) km   ; ii) 001 zxzx kk mm  для всех ;1nk  iii) 001 zxzx kmk  для всех .1nk  Из неравенства леммы 6 и ii) следует   ),(2)1()1( 0100 22 zxzxyzyx kkkkkk mmmmmm .2 M km Отсюда .0limlim   kkkk mm k mm k yzyx Из рассуждений, подобных вы- шеизложенным, видно, что частичные слабые пределы последовательностей )( kmx и )( kmy принадлежат множеству ).,( CAVI Из неравенства  kkkkkkkk mmmmmmmm xxxzxxx 001 )1( ))(1()1( 0 kkkkkkkkkk mmmmmmmmmm xyyzxxxz  следует .01  kk mm xx Из тождества ),(),(),( 1000000100 kkkk mmmm xxzxzxzxzxzx   получаем ).,(lim),(lim 0000100 zxzxzxzx kk m k m k     Как и ранее, получаем .0),(lim 0100    zxzx km k Далее имеем 2 01 zx km   2 0)1( zx kk mm   ),(2 0100 zxzx kk mm   2 01)1( zx kk mm ).,(2 0100 zxzx kk mm   Отсюда, учитывая условие iii), получаем  2 0zxk 2 01 zx km   ).,(2 0100 zxzx km   Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 45 Таким образом,   2 0lim zxk k .0),(lim2 0100    zxzx km k Следовательно, 0lim 0   zxn n и 0lim zyn n   .0lim 0   zzn n ■ 5. Алгоритм для вариационных неравенств с априорной информацией Рассмотрим вариант метода для поиска решения вариационного неравенст- ва (1), дополнительно являющегося неподвижной точкой заданного оператора. Пусть HHS : — квазинерастягивающий оператор, такой что SI  — демизамкнутый в нуле оператор со множеством неподвижных точек )(SF }.:{ xSxHx  Предположим,  )(),( SFCAVI . Замечание 5. Пусть Hg : — выпуклая дифференцируемая функция. Ес- ли множество  }0)(:{ xgHxD непусто, то его можно трактовать как множество неподвижных точек квазинерастягивающего оператора           , если , , если ),( )( )( 2 Dxx Dxxg xg xg x Sx где Hxg  )( — производная g в точке Hx [34]. Для демизамкнутости в нуле оператора SI  достаточно ограниченности g на любом ограниченном множестве [34]. Для поиска элементов множества )(),( SFCAVI  рассмотрим следующий алгоритм. Алгоритм 2. Инициализация. Задаем числовые параметры ,0 ),1,0( ),1,0( элемент ,0 Hx  последовательность )1,0(],[)(  ban и последовательность )1,0()( n такую, что ,0lim   n n   1n n . Итерационный шаг. Для Hxn  вычисляем ),( nnnCn AxxPy  где n получаем из условия       . },)()(:0{min)( )(nj n nn j nCnn j nC j xAxxPAxAxxAPjnj Вычисляем )),()1()(1(01 nnnTnnnnnn AyxSPxxx n  где }.0),(:{  nnnnnn yzyAxxHzT При анализе алгоритма 2 продолжим использовать обозначение (6). Лемма 8. Для порожденных алгоритмом 2 последовательностей ),( nx )( ny и )( nz имеет место неравенство  2 1 zxn  22 )1)(1( nnnn yxzx ),,(2)1()1)(1( 10 22 zxzxSzxyz nnnnnnnnn   где ).(),( SFCAVIz  46 ISSN 0572-2691 Доказательство. Пусть ).(),( SFCAVIz  Имеем  2 0 2 1 ))1()(1()( zSzxzxzx nnnnnnn   ),(2)1()1( 10 22 zxzxzSzx nnnnnnn  2 ))(1()( zSzzx nnnn   ),(2 10 zxzx nn   ),(2)1()1( 10 222 zxzxSzxzSzzx nnnnnnnnnn ).,(2)1()1( 10 222 zxzxSzxzzzx nnnnnnnnnn   (16) Используя лемму 5 для оценки слагаемого 2 )1( zznn  в (16), приходим к не- равенству  2 1 zxn  22 )1)(1( nnnn yxzx ),,(2)1()1)(1( 10 22 zxzxSzxyz nnnnnnnnn   что и следовало доказать. ■ Лемма 9. Порожденные алгоритмом 2 последовательности ),( nx )( ny и )( nz ограниченны. Доказательство. Пусть ).(),( SFCAVIz  Имеем  )))(1()()(1()( 01 zSzzxzxzx nnnnnnn  zSzzxzx nnnnnnn )1)(1()1(0 zzzxzx nnnnnnn  )1)(1()1(0 . Воспользовавшись неравенством (7), получим  zxn 1 },{max)1( 00 zxzxzxzx nnnn  . Следовательно,  zxn 1 },{max 10 zxzx  n . Таким образом, по- следовательность )( nx ограниченна. Ограниченность последовательностей )( ny и )( nz следует из ограниченности )( nx и неравенства (7). ■ Имеет место следующая теорема. Теорема 2. Пусть множество HC  — выпуклое и замкнутое, оператор HHA : — монотонный, равномерно непрерывный на ограниченных множе- ствах и отображающий ограниченные множества в ограниченные. Пусть оператор HHS : — квазинерастягивающий, причем оператор SI  демизамкнут в ну- ле. Предположим, что  )(),( SFCAVI . Тогда последовательности ),( nx )( ny и ),( nz порожденные алгоритмом 2, сильно сходятся к точке 0),(0 xPz CAVI и точке .0)(),(0 xPz SFCAVI  Доказательство. Рассмотрим элемент .0)(),(0 xPz SFCAVI  Из леммы 9 сле- дует существование такого числа ,0M что Mzxzx n   ),( 0100 для всех n . Тогда из неравенства леммы 8 получим оценку  2 01 zxn  22 0 )1)(1( nnnn yxzx .2)1()1)(1( 22 MSzxyz nnnnnnnn  (17) Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 47 Рассмотрим числовую последовательность ).( 0zxn  Возможны два вариан- та: a) существует номер n такой, что 001 zxzx nn  для всех ;nn  б) существует возрастающая последовательность номеров )( kn такая, что 001 zxzx kk nn  для всех k . Сначала рассмотрим вариант a). В этом случае существует .lim 0 Rzxn n   Поскольку 0 2 0 2 01  zxzx nn и ,0n то при n имеем ,0 nn yx (18) ,0 nn yz (19) .0 nn Szx (20) Из ограниченности )( nx следует существование подпоследовательности ),( knx слабо сходящейся к точке .Hw Из (11) следует, что wy kn  слабо. Следовательно, .Cw Рассуждая, как в доказательстве теоремы 1, получаем, что ).,( CAVIw Осталось показать, что ).(SFw Поскольку nnnnnnnn SzxxyyzSzz  , то из (18)–(20) следует .0lim   nn n Szz Оператор SI  демизамкнут в нуле. Следовательно, из wz kn  слабо и 0lim   kk nn k Szz получаем, что ).(SFw Как и при доказательстве теоремы 1, получаем .0),(lim 0100    zxzx n n (21) Из (21), неравенства 2 01 zxn    ),(2)1()1( 0100 2 0 2 zxzxzSzx nnnnnnn   ),(2)1)(1()1( 0100 2 0 2 0 zxzxzSzzx nnnnnnnn   ),(2)1)(1()1( 0100 2 0 2 0 zxzxzzzx nnnnnnnn ),(2)1( 0100 2 0 zxzxzx nnnn   . и леммы 2 делаем вывод, что .00  zxn Из (18), (19) получаем 00  zyn и .00  zzn Изучим вариант б). В этом случае рассмотрим последовательность номе- ров )( km со свойствами: i) km   ; ii) 001 zxzx kk mm  для всех ;1nk  iii) 001 zxzx kmk  для всех .1nk  Из ii) следует  22 )1)(1()1)(1( kkkkkk mmmmmm yzyx .2),(2)1( 0100 2 MzxzxSzx kkkkkkk mmmmmmm   48 ISSN 0572-2691 Отсюда .0limlimlim   kkkkkk mm k mm k mm k Szxyzyx Рассужде- ниями, подобными вышеизложенным, показываем, что частичные слабые пределы последовательностей ),( kmx )( kmy и )( kmz принадлежат множеству ).(),( SFCAVI  Из неравенства  ))(1)(1()( 01 kkkkkkkk mmmmmmmm xSzxxxx kkkkkk mmmmmm xSzxx  )1)(1(0 следует .01  kk mm xx Далее повторяем рассуждения доказательства теоремы 1. ■ Рассмотрим теперь операторное уравнение с априорной информацией, задан- ной в виде множества неподвижных точек квазинерастягивающего оператора :: HHT  ,fAx  ),(TFx (22) где .Hf  Подобные задачи рассматривались в работе [35]. Алгоритм 2 для задачи (22) принимает следующий вид. Алгоритм 3. Инициализация. Задаем числовые параметры ,0 ),1,0( ),1,0( элемент ,0 Hx  последовательность )1,0(],[)(  ban и последовательность )1,0()( n такую, что ,0lim   n n    n n 1 . Итерационный шаг. Для Hxn  вычисляем ),( fAxxy nnnn  где n получаем из условия       . },))((:0{min)( )(nj n nnn j n AxAxfAxxAjnj Вычисляем ),( fAyxz nnnn  ).)1()(1(01 nnnnnnn Tzxxx  Частным случаем теоремы 2 является следующий результат. Теорема 3. Пусть оператор HHA : — монотонный, равномерно непре- рывный на ограниченных множествах и отображающий ограниченные множества в ограниченные. Пусть оператор HHT : — квазинерастягивающий, причем оператор TI  демизамкнут в нуле. Предположим, что  )(1 TFfA для .Hf  Тогда последовательности ),( nx )( ny и ),( nz порожденные алгорит- мом 3, сильно сходятся к точке .0)(0 1 xPz TFfA  Заключение В статье предложен сильно сходящийся модифицированный экстраградиент- ный метод с динамической регулировкой величины шага для решения вариацион- ных неравенств с монотонными операторами, действующими в гильбертовом пространстве. Не предполагается липшицевость операторов. Также рассмотрены варианты метода для вариационных неравенств и операторных уравнений с априорной информацией о решении, заданной в виде множества неподвижных Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 49 точек квазинерастягивающего оператора. Основной теоретический результат — теоремы о сильной сходимости методов. В отличие от работы [30], где в липши- цевой ситуации применялся гибридный метод (как в [22]), в данной статье для ре- гуляризации использовалась более простая схема Гальперна [32, 33], по сути сов- падающая со схемой итеративной регуляризации [4]. Д.А. Верлань, В.В. Семенов, Л.М. Чабак СИЛЬНО ЗБІЖНИЙ МОДИФІКОВАНИЙ ЕКСТРАГРАДІЄНТНИЙ МЕТОД ДЛЯ ВАРІАЦІЙНИХ НЕРІВНОСТЕЙ З НЕЛІПШИЦЕВИМИ ОПЕРАТОРАМИ Запропоновано регуляризований модифікований екстраградієнтний метод з ди- намічним регулюванням величини кроку для розв’язання варіаційних нерівнос- тей з монотонними операторами, що діють у гільбертовому просторі. Також ро- зглянуто варіанти методу для варіаційних нерівностей та операторних рівнянь з апріорною інформацією про розв’язок, що задана у вигляді множини нерухо- мих точок квазінерозтягуючого оператора. Доведено теореми про сильну збіж- ність методів без припущення про ліпшицевість операторів. D.A. Verlan, V.V. Semenov, L.M. Chabak A STRONGLY CONVERGENT MODIFIED EXTRAGRADIENT METHOD FOR VARIATIONAL INEQUALITIES WITH NON-LIPSCHITZ OPERATORS Regularized modified extragradient method with dynamic rule for finding the step size for solving variational inequalities with monotone operators acting in a Hilbert space is presented. In addition the variants of this method for variational inequalities and op- erator equations with a priori information about solution which is given as the set of fixed points of quasi-nonexpansive operator. Strong convergence of methods without any Lipschitzian continuity assumption on operators is established. 1. Киндерлерер Д., Стампаккья Г. Введение в вариационные неравенства и их приложения. — М. : Мир, 1983. — 256 c. 2. Nagurney A. Network economics: A variational inequality approach. — Dordrecht : Kluwer Aca- demic Publishers, 1999. — 325 p. 3. Семенов В.В., Семенова Н.В. О задаче векторного управления в гильбертовом пространстве // Кибернетика и системный анализ. — 2005. — № 2. — С. 117–130. 4. Бакушинский А.Б., Гончарский А.В. Некорректные задачи. Численные методы и приложе- ния. — М. : Изд-во МГУ, 1989. — 200 c. 5. Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarity prob- lems. V. 2. — New York : Springer, 2003. — 704 p. 6. Bauschke H.H., Combettes P.L. Convex analysis and monotone operator theory in Hilbert spaces. — Berlin; Heidelberg; New York : Springer, 2011. — 408 p. 7. Konnov I.V. Combined relaxation methods for variational inequalities. — Berlin; Heidelberg; New York : Springer-Verlag, 2001. — 181 p. 8. Xiu N., Zhang J. Some recent advances in projection-type methods for variational inequalities // J. Comput. Appl. Math. — 2003. — 152. — Р. 559–585. 9. Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related problems // Mathematical Programming. — 2007. — 109, N 2-3. — P. 319–344. 10. Семенов В.В. О методе параллельной проксимальной декомпозиции для решения задач вы- пуклой оптимизации // «Международный научно-технический журнал «Проблемы управ- ления и информатики». — 2010. — № 2. — С. 42–46. 50 ISSN 0572-2691 11. Семенов В.В. О сходимости методов решения двухуровневых вариационных неравенств с монотонными операторами // Журнал обчислювальної та прикладної математики. — 2010. — № 2 (101). — С. 120–128. 12. Войтова Т.А., Семенов В.В. Метод решения двухэтапных операторных включений // Там же. — 2010. — № 3 (102). — С. 34–39. 13. Маліцький Ю.В., Семенов В.В. Нові теореми сильної збіжності проксимального методу для задачі рівноважного програмування // Там же. — 2010. — № 3 (102). — С. 79–88. 14. Денисов С.В., Семенов В.В. Проксимальний алгоритм для дворівневих варіаційних нерівностей: сильна збіжність // Там же. — 2011. — № 3 (106). — C. 27–32. 15. Войтова Т.А., Семенов В.В., Денисов С.В. Альтернуючий проксимальний алгоритм для задачі дворівневої опуклої мінімізації // Доповіді НАН України. — 2012. — № 2. — С. 56–62. 16. Семенов В.В. Параллельная декомпозиция вариационных неравенств с монотонными операто- рами // Журнал обчислювальної та прикладної математики. — 2012. — № 2 (108). — С. 53–58. 17. Семенов В.В. Явный алгоритм расщепления для вариационных неравенств с монотонными операторами // Там же. — 2013. — № 2 (112). — С. 42–52. 18. Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of solutions the equilibrium problems // In M.Z. Zgurovsky and V.A. Sadovnichiy (eds.), Continu- ous and Distributed Systems, Solid Mechanics and Its Applications. — Springer International Publishing Switzerland. — 2014. — 211. — P. 131–146. 19. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач // Экономика и математические методы. — 1976. — 12, № 4. — С. 747–756. 20. Хоботов Е.Н. О модификации экстраградиентного метода для решения вариационных не- равенств и некоторых задач оптимизации // Журнал вычислительной математики и матема- тической физики. — 1987. — 27, № 10. — С. 1462–1473. 21. Tseng P. A modified forward-backward splitting method for maximal monotone mappings // SIAM J. Control Optim. — 2000. — 38. — P. 431–446. 22. Nadezhkina N., Takahashi W. Strong convergence theorem by a hybrid method for nonexpansive mappings and Lipschitz-continuous monotone mappings // Ibid. — 2006. — 16, N 4. — P. 1230–1241. 23. Апостол Р.Я., Гриненко А.А., Семенов В.В. Ітераційні алгоритми для монотонних дворівневих варіаційних нерівностей // Журнал обчислювальної та прикладної математики. — 2012. — № 1 (107). — C. 3–14. 24. Запорожец Д.Н., Зыкина А.В., Меленьчук Н.В. Сравнительный анализ экстраградиентных методов решения вариационных неравенств для некоторых задач // Автоматика и телеме- ханика. — 2012. — № 4. — С. 32–46. 25. Малицкий Ю.В., Семенов В.В. Вариант экстраградиентного алгоритма для монотонных ва- риационных неравенств // Кибернетика и системный анализ. — 2014. — № 2. — C. 125–131. 26. Семенов В.В. Гибридные методы расщепления для системы операторных включений с мо- нотонными операторами // Там же. — 2014. — № 5. — C. 104–112. 27. Malitsky Yu.V., Semenov V.V. A hybrid method without extrapolation step for solving variational inequality problems // Journal of Global Optimization. — 2015. — 61, N 1. — P. 193–202. 28. Ляшко С.И., Семенов В.В., Войтова Т.А. Экономичная модификация метода Корпелевич для мо- нотонных задач о равновесии // Кибернетика и системный анализ. — 2011. — № 4. — C. 146–154. 29. Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space // Journal of Optimization Theory and Applications. — 2011. — 148. — P. 318–335. 30. Censor Y., Gibali A., Reich S. Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space // Optimization Methods Software. — 2011. — 26. — P. 827–845. 31. Nakajo K., Takahashi W. Strong convergence theorems for nonexpansive mappings and nonex- pansive semigroups // J. Math. Anal. Appl. — 2003. — 279. — P. 372–379. 32. Halpern B. Fixed points of nonexpanding maps // Bull. Amer. Math. Soc. — 1967. — 73. — P. 957–961. 33. Xu H. K. Viscosity approximation methods for nonexpansive mappings // J. Math. Anal. Appl. — 2004. — 298. — P. 279–291. 34. Васин В.В., Еремин И.И. Операторы и итерационные процессы фейеровского типа. — Мо- сква-Ижевск : Регулярная и хаотическая динамика, 2005. — 200 c. 35. Mainge P.-E. Strong convergence of projected subgradient methods for nonsmooth and non- strictly convex minimization // Set-Valued Analysis. — 2008. — 16. — P. 899–912. 36. Семенов В.В. Два методи апроксимації нерухомої точки фейєрівського оператора // Журнал обчислювальної та прикладної математики. — 2013. — № 1 (111). — С. 46–56. 37. Семенов В.В. Сильно сходящийся метод расщепления для системы операторных включе- ний с монотонными операторами // «Международный научно-технический журнал «Про- блемы управления и информатики». — 2014. — № 3. — С. 22–32. Получено 16.02.2015

Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами

Репозитарії

Схожі ресурси