Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара

Одним із напрямків сучасного прикладного нелінійного аналізу, що інтенсивно розвивається, є дослідження задач про рівновагу, відомих як нерівності Кі Фаня, задачі рівноважного програмування. У вигляді задачі про рівновагу можна сформулювати варіаційні нерівності, задачі математичного програмування,...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Ведель, Я.И., Денисов, С.В., Семенов, В.В.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Головна астрономічна обсерваторія НАН України 2011
Schriftenreihe:	Advances in Astronomy and Space Physics
Schlagworte:	Методы оптимизации и оптимальное управление
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/208778
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Проблемы управления и информатики. — 2020. — № 5. — С. 15-27. — Бібліогр.: 30 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208778
record_format	dspace
spelling	irk-123456789-2087782025-11-06T12:05:00Z Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара Регуляризований адаптивний екстрапроксимальний алгоритм для задачі про рівновагу в просторах адамара Regularized adaptive extra-proximal algorithm for equilibrium problem in hadamard spaces Ведель, Я.И. Денисов, С.В. Семенов, В.В. Методы оптимизации и оптимальное управление Одним із напрямків сучасного прикладного нелінійного аналізу, що інтенсивно розвивається, є дослідження задач про рівновагу, відомих як нерівності Кі Фаня, задачі рівноважного програмування. У вигляді задачі про рівновагу можна сформулювати варіаційні нерівності, задачі математичного програмування, пошук рівноваги Неша. Останнім часом виник обумовлений проблемами математичної біології та машинного навчання інтерес до побудови теорії та алгоритмів розв’язання задач математичного програмування в метричних просторах Адамара. У даній роботі розглядаються загальні задачі про рівновагу в метричних просторах Адамара. Для наближеного розв’язання задач запропоновано та досліджено новий ітераційний регуляризований адаптивний екстрапроксимальний алгоритм. На відміну від правил вибору величини кроку, що застосовувалися раніше, в запропонованому алгоритмі не проводиться обчислень значень біфункції в додаткових точках та не потрібно знання про величину її ліпшіцевих констант. Для регуляризації базової екстрапроксимальної схеми використано класичну схему Гальперна. Для псевдомонотонних біфункцій ліпшіцевого типу доведено теорему про збіжність породжених алгоритмом послідовностей. Доведення засновано на використанні фейєрівської властивості екстрапроксимального алгоритму відносно множини розв’язків задачі та відомих результатів про збіжність схеми Гальперна. Показано, що запропонований алгоритм можна застосувати до псевдомонотонних варіаційних нерівностей в гільбертових просторах. One of the intensively developing areas of modern applied nonlinear analysis is the study of equilibrium problems, also known as Ky Fan inequalities, equilibrium programming problems. In the form of an equilibrium problem, one can formulate variational inequalities, mathematical programming problems, and many game theory problems (search of Nash equilibrium). Recently, interest has arisen due to the problems of mathematical biology and machine learning to construct the theory and algorithms for solving mathematical programming problems in Hadamard metric spaces. In this paper, we consider equilibrium problems in Hadamard metric spaces. For an approximate solution of problems, a new iterative regularized adaptive extra-proximal algorithm is proposed and studied. 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 of bifunction’s Lipschitz constants. For regularization of basic extrproximal scheme, the classic Halpern scheme is used. For pseudomonotone bifunctions of Lipschitz type, the theorem on convergence of sequences generated by the algorithm is proved. The proof is based on the use of the Fejer property of the extraproximal algorithm with respect to the set of solutions of problem and known results on the convergence of the Halpern scheme. It is shown that the proposed algorithm is applicable to pseudo-monotone variational inequalities in Hilbert spaces. Работа выполнена при финансовой поддержке МОН Украины(проект «Математичне моделю-вання та оптимiзацiя динамiчних систем для оборони, медицини та екології», номер госрегистра-ции0219U008403) и НАН Украины (проект «Нові методи дослідження коректності та розвʼязання задач дискретної оптимізації, варіаційних нерівностей та їх застосування», номергосрегистрации 0119U101608). 2011 Article Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Проблемы управления и информатики. — 2020. — № 5. — С. 15-27. — Бібліогр.: 30 назв. — рос. 2227-1481 https://nasplib.isofts.kiev.ua/handle/123456789/208778 517.988 10.1615/JAutomatInfScien.v52.i9.20 en Advances in Astronomy and Space Physics application/pdf Головна астрономічна обсерваторія НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление
spellingShingle	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление Ведель, Я.И. Денисов, С.В. Семенов, В.В. Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара Advances in Astronomy and Space Physics
description	Одним із напрямків сучасного прикладного нелінійного аналізу, що інтенсивно розвивається, є дослідження задач про рівновагу, відомих як нерівності Кі Фаня, задачі рівноважного програмування. У вигляді задачі про рівновагу можна сформулювати варіаційні нерівності, задачі математичного програмування, пошук рівноваги Неша. Останнім часом виник обумовлений проблемами математичної біології та машинного навчання інтерес до побудови теорії та алгоритмів розв’язання задач математичного програмування в метричних просторах Адамара. У даній роботі розглядаються загальні задачі про рівновагу в метричних просторах Адамара. Для наближеного розв’язання задач запропоновано та досліджено новий ітераційний регуляризований адаптивний екстрапроксимальний алгоритм. На відміну від правил вибору величини кроку, що застосовувалися раніше, в запропонованому алгоритмі не проводиться обчислень значень біфункції в додаткових точках та не потрібно знання про величину її ліпшіцевих констант. Для регуляризації базової екстрапроксимальної схеми використано класичну схему Гальперна. Для псевдомонотонних біфункцій ліпшіцевого типу доведено теорему про збіжність породжених алгоритмом послідовностей. Доведення засновано на використанні фейєрівської властивості екстрапроксимального алгоритму відносно множини розв’язків задачі та відомих результатів про збіжність схеми Гальперна. Показано, що запропонований алгоритм можна застосувати до псевдомонотонних варіаційних нерівностей в гільбертових просторах.
format	Article
author	Ведель, Я.И. Денисов, С.В. Семенов, В.В.
author_facet	Ведель, Я.И. Денисов, С.В. Семенов, В.В.
author_sort	Ведель, Я.И.
title	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
title_short	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
title_full	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
title_fullStr	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
title_full_unstemmed	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
title_sort	регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара
publisher	Головна астрономічна обсерваторія НАН України
publishDate	2011
topic_facet	Методы оптимизации и оптимальное управление
url	https://nasplib.isofts.kiev.ua/handle/123456789/208778
citation_txt	Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара / Я.И. Ведель, С.В. Денисов, В.В. Семенов // Проблемы управления и информатики. — 2020. — № 5. — С. 15-27. — Бібліогр.: 30 назв. — рос.
series	Advances in Astronomy and Space Physics
work_keys_str_mv	AT vedelʹâi regulârizovannyjadaptivnyjékstraproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT denisovsv regulârizovannyjadaptivnyjékstraproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT semenovvv regulârizovannyjadaptivnyjékstraproksimalʹnyjalgoritmdlâzadačioravnovesiivprostranstvahadamara AT vedelʹâi regulârizovanijadaptivnijekstraproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT denisovsv regulârizovanijadaptivnijekstraproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT semenovvv regulârizovanijadaptivnijekstraproksimalʹnijalgoritmdlâzadačíprorívnovaguvprostorahadamara AT vedelʹâi regularizedadaptiveextraproximalalgorithmforequilibriumprobleminhadamardspaces AT denisovsv regularizedadaptiveextraproximalalgorithmforequilibriumprobleminhadamardspaces AT semenovvv regularizedadaptiveextraproximalalgorithmforequilibriumprobleminhadamardspaces
first_indexed	2025-11-07T02:33:52Z
last_indexed	2025-11-07T02:33:52Z
_version_	1848097198923841536
fulltext	© Я.И. ВЕДЕЛЬ, С.В. ДЕНИСОВ, В.В. СЕМЕНОВ, 2020 Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 15 МЕТОДЫ ОПТИМИЗАЦИИ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ УДК 517.988 Я.И. Ведель, С.В. Денисов, В.В. Семенов РЕГУЛЯРИЗОВАННЫЙ АДАПТИВНЫЙ ЭКСТРАПРОКСИМАЛЬНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ О РАВНОВЕСИИ В ПРОСТРАНСТВАХ АДАМАРА Ключевые слова: регуляризация, адаптивность, сходимость, экстрапрокси- мальный алгоритм, схема Гальперна, задача о равновесии, псевдомонотон- ность, пространство Адамара. Введение Одним из интенсивно развивающихся направлений современного прикладно- го нелинейного анализа является исследование задач о равновесии (неравенств Ки Фаня, задач равновесного программирования) вида [1–13]: найти (1) где — непустое подмножество гильбертова пространства — функция, такая, что (называемая бифункцией). В виде (1) можно сформулировать задачи математического программирования, вариацион- ные неравенства и многие игровые задачи. Исследование алгоритмов решения равновесных и близких задач активно продолжается. Частным случаем задач о равновесии являются вариационные не- равенства [14]. Для их решения еще в 1970-х годах Г.М. Корпелевич предложила экстраградиентный метод [15]. В [16] рассмотрен экстраградиентный метод для неравенств в бесконечномерном гильбертовом пространстве и доказана его слабая сходимость. Одним из современных вариантов экстраградиентного метода явля- ется проксимальный зеркальный метод Немировского [17]. Данный метод можно интерпретировать как вариант экстраградиентного метода с проектированием, понимаемым в смысле расхождения Брэгмана. В [18, 19] предложены адаптивные модификации проксимального зеркального метода, не требующие знания кон- стант Липшица операторов для определения величины шага. Аналогам экстрагра- диентного метода для задач о равновесии и близким вопросам посвящены работы [2, 5, 7, 8, 20–24]. Следуя А.С. Антипину, экстрапроксимальным будем называть следующий аналог экстраградиентного метода для задач о равновесии [2, 5]  Работа выполнена при финансовой поддержке МОН Украины (проект «Математичне моделю- вання та оптимiзацiя динамiчних систем для оборони, медицини та екології», номер госрегистра- ции 0219U008403) и НАН Украины (проект «Нові методи дослідження коректності та розвʼязання задач дискретної оптимізації, варіаційних нерівностей та їх застосування», номер госрегистрации 0119U101608). 16 ISSN 0572-2691 где — проксимальный оператор функции [25]. В последнее время возник обусловленный проблемами математической био- логии и машинного обучения интерес к построению теории и алгоритмов реше- ния задач математического программирования в метрических пространствах Адамара [26] (также известных под названием -пространств). Еще одной сильной мотивацией для изучения данных задач является возможность записать некоторые невыпуклые задачи в виде выпуклых (точнее, геодезически выпуклых) в пространстве со специально подобранной римановой метрикой [10, 26]. Некоторые авторы начали изучать задачи о равновесии в пространствах Ада- мара [10–13]. В работе [10] получены теоремы существования для задач о равно- весии на многообразиях Адамара, рассмотрены приложения к вариационным не- равенствам и обоснован резольвентный метод для аппроксимации решений задач о равновесии и вариационных неравенств. В [11] для более общих задач о равно- весии с псевдомонотонными бифункциями в пространствах Адамара получены теоремы существования, предложен проксимальный алгоритм и доказана его схо- димость. Более конструктивному подходу посвящена работа [12], авторы которой, отталкиваясь от результатов статьи [5], предложили и обосновали для псевдомо- нотонных задач о равновесии в пространствах Адамара аналог экстраградиентно- го (или экстрапроксимального) метода. А в работе [13] предложен новый адап- тивный экстрапроксимальный алгоритм, который, в отличие от применяемых ра- нее правил выбора величины шага [5, 8, 17, 19], не производит вычислений значений бифункции в дополнительных точках и не требует знаний липшицевых констант бифункции. Для псевдомонотонных бифункций липшицевого типа дока- зана теорема о слабой сходимости (или -cходимости) порожденных алгоритмом последовательностей. В данной работе, продолжающей статью [13], предлагается новый итерацион- ный регуляризованный адаптивный экстрапроксимальный алгоритм для прибли- женного решения задач о равновесии в метрических пространствах Адамара. Для регуляризации базовой адаптивной экстрапроксимальной схемы [13] использована классическая схема Гальперна [27], вариант которой для пространств Адамара изу- чен в [26]. Для псевдомонотонных бифункций липшицевого типа доказана теорема о сходимости порожденных алгоритмом последовательностей. Доказательство ос- новано на использовании фейеровского свойства экстрапроксимального алгоритма относительно множества решений задачи и известных результатов о сходимости схем типа Гальперна [4, 8, 21, 23, 26–28]. Показано, что предложенный алгоритм применим к псевдомонотонным вариационным неравенствам в гильбертовых пространствах. Вспомогательные сведения Прежде всего, приведем основные понятия и факты, связанные с метриче- скими пространствами Адамара. С деталями можно ознакомиться в [26, 29, 30]. Пусть ⎯ метрическое пространство и Геодезическим путем, соединяющим точки и , называют изометрию , такую, что Множество обозначают и назы- вают геодезическим сегментом с концами и (или просто геодезическим). Метрическое пространство именуют геодезическим, если любые две точ- Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 17 ки можно соединить геодезической, и однозначно геодезическим — если для любых двух точек существует в точности одна их соединяющая геоде- зическая. Геодезическое пространство называют -пространст- вом, если для любой тройки точек , таких, что = выполняется неравенство (2) Неравенство (2) иногда именуют -неравенством [29] (заметим, что в евклидовом пространстве (2) превращается в тождество), а точку ⎯ сере- диной между точками и (она всегда существует в геодезическом про- странстве). Известно, что -пространство является однозначно геоде- зическим [26]. Для двух точек и -пространства и будем обозначать , такую единственную точку сегмента что и Множество называется вы- пуклым (геодезически выпуклым), если для всех и выполняется Полезным инструментом для работы в -пространстве является следующее неравенство: . (3) Примерами -пространств являются евклидовы пространства, -деревья, гильбертов шар с гиперболической метрикой и многообразия Адамара (полные связные римановы многообразия неположительной кривизны) [26, 29, 30]. Полное -пространство называют пространством Адамара. Как и в гильбертовом пространстве, в пространствах Адамара корректно определен оператор метрического проектирования на замкнутое выпуклое мно- жество [26]. Точнее, для каждого существует единственный элемент множества со свойством причем имеет место ха- рактеризация [26]: и Пусть — метрическое пространство, — ограниченная по- следовательность элементов X и Число называют асимптотическим радиусом а множество — асимптотическим центром Извест- но, что в пространстве Адамара состоит из одной точки [26]. Последова- тельность элементов пространства Адамара слабо сходится (или, как иногда говорят, -сходится [29]) к элементу если для лю- бой подпоследовательности Известно, что произвольная последователь- 18 ISSN 0572-2691 ность элементов ограниченного, замкнутого и выпуклого подмножества про- странства Адамара имеет подпоследовательность, слабо сходящуюся к элементу из [26, 29]. В гильбертовом пространстве рассмотренная -сходимость совпа- дает с классической слабой сходимостью [26]. Пусть ⎯ пространство Адамара. Функция называется выпуклой (геодезически выпуклой), если для всех и выполняется неравенство Например, в пространстве Адамара функции выпуклы. Если же существует такая константа что для всех и выполняется неравенство то функция называется сильно выпуклой. Известно, что для выпуклых функ- ций полунепрерывность снизу и слабая полунепрерывность снизу эквивалентны [26, p. 64], а сильно выпуклая полунепрерывная снизу функция достигает мини- мума в единственной точке. Для выпуклой, собственной и полунепрерывной снизу функции проксимальный оператор определяется следующим образом [26]: (4) Поскольку функции сильно выпуклы, определение проксималь- ного оператора (4) корректно, т.е. для каждого существует единственный элемент Следующие известные факты играют важную роль в доказательстве основно- го результата работы. Лемма 1 [28]. Пусть числовая последовательность имеет подпоследова- тельность со свойством для всех Тогда существует такая неубывающая последовательность натуральных чисел, что и для всех Лемма 2. Пусть — последовательность неотрицательных чисел, удо- влетворяющих неравенству для всех где последо- вательности и обладают свойствами: Тогда Задача о равновесии в пространстве Адамара Перейдем к формулировке задачи о равновесии в пространстве Адамара. Пусть — пространство Адамара. Для непустого выпуклого замкнутого множества и бифункции рассмотрим задачу о равновесии (или задачу равновесного программирования [2, 4, 9]): найти (5) Предположим, что выполнены следующие условия: 1) для всех Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 19 2) функции выпуклы и полунепрерывны снизу для всех 3) функции слабо полунепрерывны сверху для всех 4) бифункция псевдомонотонна, т.е. для всех из следует 5) бифункция липшицевого типа, т.е. существуют две констан- ты такие, что (6) Замечание 1. Условие 5 типа липшицевости в евклидовом пространстве вве- дено в [3]. Замечание 2. Если где ⎯ непустое под- множество гильбертова пространства то задача (5) сводится к классическому вариационному неравенству найти (7) Если множество выпуклое и замкнутое, а оператор псев- домонотонный, липшицевый и секвенциально слабо непрерывный, то для (7) вы- полняются условия 3–5. Рассмотрим дуальную задачу о равновесии: найти (8) Множества решений задач (5) и (8) обозначим и При выполнении условий 1–4 имеем [11]. Кроме того, множество выпукло и замкнуто. Далее будем предполагать, что Регуляризованный адаптивный экстрапроксимальный алгоритм Для приближенного решения задачи о равновесии (5) рассмотрим регуляри- зованный с помощью схемы Гальперна [27] экстрапроксимальный алгоритм с адаптивным выбором величины шага [13]. Алгоритм 1 Инициализация. Выбираем элементы числа и последовательность такую, что Полагаем Шаг 1. Вычислить Шаг 2. Вычислить . Шаг 3. Вычислить Шаг 4. Вычислить (9) 20 ISSN 0572-2691 Положить : 1n n= + и перейти на шаг 1. Замечание 3. Очевидно, что числовая последовательность ( )n неубываю- щая. Также она ограничена снизу числом 1min , 2max{ , }a b       . Перейдем к обоснованию сходимости алгоритма 1. Основные неравенства Сначала сформулируем важный факт. Лемма 3 [13]. Для x С и ( , )prox ,F xx x+  = где 0,  имеет место неравенство ( , ) ( , )F x x F x y+ −  2 2 21 ( ( , ) ( , ) ( , )) 2 d y x d x x d x y+ +− −  .y С  (10) Из неравенства (10) следует, что для последовательностей ( )ny и ( ),nz по- рожденных проксимальными шагами алгоритма 1, имеют место неравенства ( , ) ( , )n n nF x y F x y−  2 2 21 ( ( , ) ( , ) ( , )) 2 n n n n n d y x d x y d y y− −  .y С  (11) ( , ) ( , )n n nF y z F y y−  2 2 21 ( ( , ) ( , ) ( , )) 2 n n n n n d y x d x z d z y− −  .y С  (12) Лемма 4. Для последовательностей ( ),nx ( )ny и ( ),nz порожденных алго- ритмом 1, имеет место неравенство 2 2 2 2 1 1 ( , ) ( , ) 1 ( , ) 1 ( , ),n n n n n n n n n n d z z d x z d z y d y x + +       − −  − −          (13) где .z S Доказательство. Пусть .z S Из псевдомонотонности бифункции F следует ( , ) 0.nF y z  (14) Из (14) и (12) вытекает, что 2 ( , )n n nF y z  2 2 2( , ) ( , ) ( , ).n n n nd z x d x z d z z− − (15) Из правила вычисления 1n+ следует оценка 2 2 1 ( , ) ( , ) ( , ) ( ( , ) ( , )). 2 n n n n n n n n n n n F x z F x y F y z d x y d z y +  − −  +  (16) Оценив снизу левую часть (15) с помощью (16), получим 2 2 1 2 ( ( , ) ( , )) ( ( , ) ( , ))n n n n n n n n n n n F x z F x y d x y d z y +   − −  +    2 2 2( , ) ( , ) ( , ).n n n nd z x d x z d z z− − (17) Для оценки снизу 2 ( ( , ) ( , ))n n n n nF x z F x y − в (17) воспользуемся неравен- ством (11). Имеем 2 2 2 2 2 1 ( , ) ( , ) ( , ) ( ( , ) ( , ))n n n n n n n n n n n n d x y d y z d z x d x y d z y +  + − −  +    2 2 2( , ) ( , ) ( , ).n n n nd z x d x z d z z− − (18) Перегруппировав (18), получим (13). ■ Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 21 Лемма 5. Для последовательностей ( ),nx ( )ny и ( ),nz порожденных алго- ритмом 1, имеет место неравенство 2 2 2 1 1 ( , ) (1 ) ( , ) (1 ) 1 ( , )n n n n n n n n d x z d x z d z y+ +   − − + − −  +    2 2 2 1 (1 ) 1 ( , ) ( , ) (1 ) ( , ),n n n n n n n n n d y x d a z d a z +   + − −    − −    (19) где .z S Доказательство. Пусть .z S Из равенства 1 (1 )n n n nx a z+ =   − и нера- венства сильной выпуклости (3) следует оценка 2 1( , )nd x z+  2 2 2( , ) (1 ) ( , ) (1 ) ( , ).n n n n n nd a z d z z d a z + − − − Для оценки сверху 2 ( , )nd z z воспользуемся леммой 4 и получим неравен- ство (19). ■ Сходимость алгоритма Докажем ограниченность порожденных алгоритмом последовательностей. Лемма 6. Порожденные алгоритмом 1 последовательности ( ),nx ( )ny и ( )nz ограниченны. Доказательство. Пусть .z S Имеем 1( , ) ( (1 ) , )n n n nd x z d a z z+ =   −  ( , ) (1 ) ( , ).n n nd a z d z z + − Поскольку существует lim 0,n n→   1 1 n n+  −   1→ − (0,1) при n → . Воспользовавшись неравенством леммы 4, получим 1( , )nd x z+  ( , ) (1 ) ( , )n n nd a z d x z + − max{ ( , ), ( , )}nd a z d x z для всех 0.n n Следовательно, 1( , )nd x z+  0 max{ ( , ), ( , )}nd a z d x z 0.n n Таким образом, последовательность ( )nx ограниченна. Ограниченность последовательностей ( )ny и ( )nz следует из ограниченно- сти ( )nx и леммы 4. ■ Сформулируем основной результат работы. Теорема 1. Пусть ( , )X d — пространство Адамара, C X — непустое вы- пуклое замкнутое множество, для бифункции :F C C → выполнены условия 1–5 и S  . Тогда порожденные алгоритмом 1 последовательности ( ),nx ( )ny и ( )nz сходятся к элементу .SP a Доказательство. Рассмотрим элемент 0 .Sz P a= Из леммы 5 следует суще- ствование такого числа 0,M  что 2 2 0( , ) (1 ) ( , )n nd a z d a z M− −  для всех N.n 22 ISSN 0572-2691 Тогда из неравенства леммы 5 получим оценку 2 2 2 1 0 0 1 ( , ) (1 ) ( , ) (1 ) 1 ( , )n n n n n n n n d x z d x z d z y+ +   − − + − −  +    2 1 (1 ) 1 ( , ) .n n n n n n d y x M +   + − −       (20) Рассмотрим числовую последовательность 0( ( , )).nd x z Возможны два вари- анта: a) существует номер Nn , такой, что 1 0 0( , ) ( , )n nd x z d x z+  для всех ;n n б) существует возрастающая последовательность номеров ( ),kn такая, что 1 0 0( , ) ( , ) k kn nd x z d x z+  для всех N.k Сначала рассмотрим вариант a). В этом случае существует 0lim ( , ) .n n d x z →  Поскольку 2 2 1 0 0( , ) ( , ) 0,n nd x z d x z+ − → 0n → и 1 1 n n+  −   1→ − (0,1), то при n → имеем ( , ) 0,n nd x y → (21) ( , ) 0.n nd z y → (22) Из ограниченности ( )nx следует существование подпоследовательности ( ), knx слабо сходящейся к точке .w X Тогда из (21), (22) вытекает, что ( ) kny и ( ) knz слабо сходятся к .w Очевидно, что .w C Покажем, что обязательно .w S Имеем 2 2 21 ( , ) ( , ) ( ( , ) ( , ) ( , )) 2k k k k k k k k n n n n n n n n F y y F y z d y x d x z d z y − − −   2 1 ( , ) ( , ) ( ( , ) 2k k k k k k k n n n n n n n F x z F x y d x y +   − − +  2 2 2 21 ( , )) ( ( , ) ( , ) ( , )) 2k k k k k k k n n n n n n n d z y d y x d x z d z y+ − − −   2 2 2 2 1 1 ( ( , ) ( , ) ( , )) ( ( , ) 2 2k k k k k k k k k k n n n n n n n n n n d z x d x y d y z d x y +   − − − − +   2 2 2 21 ( , )) ( ( , ) ( , ) ( , )) 2k k k k k k k n n n n n n n d z y d y x d x z d z y+ − − −  .y С  (23) Совершив предельный переход в (23) с учетом (21), (22) и слабой полунепре- рывности сверху функции ( , ) :F y C → , получаем ( , ) lim ( , ) 0 kn k F z y F y y →   .y С  т.е. .z S Докажем, что 2 2 0lim ( ( , ) (1 ) ( , )) 0.n n n d a z d a z → − −  (24) Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 23 Рассмотрим такую подпоследовательность ( ), knz что 2 2 2 2 0 0lim ( ( , ) (1 ) ( , )) lim ( ( , ) (1 ) ( , )). k kn n n n k n d a z d a z d a z d a z → → − − = − − Дополнительно можно считать, что knz w S→  слабо. Тогда, воспользо- вавшись слабой полунепрерывностью снизу функции 2 ( , ),d a  получаем 2 2 2 2 0 0lim ( ( , ) (1 ) ( , )) ( , ) ( , ). k kn n k d a z d a z d a z d a w → − −  − (25) Поскольку 0 arg min ( , ),S w Sz P a d a w= = то из (25) следует (24). Теперь из (24), неравенства 2 1 0( , )nd x z+  2 2 2 0 0(1 ) ( , ) ( ( , ) (1 ) ( , )),n n n n nd x z d a z d a z− + − − имеющего место для достаточно больших ,n и леммы 2 делаем вывод, что 0( , ) 0.nd x z → Из (21), (22) получаем 0( , ) 0nd y z → и 0( , ) 0.nd z z → Изучим вариант б). В этом случае рассмотрим последовательность номеров ( )km со следующими свойствами (лемма 1): i) km + ; ii) 1 0 0( , ) ( , ) k km md x z d x z+  для всех 1;k n iii) 1 0 0( , ) ( , ) km kd x z d x z+  для всех 1.k n Из неравенства леммы 5 и свойства ii следует 2 2 0 1 ( , ) (1 ) 1 ( , )k k k k k k k m m m m m m m d x z d z y +     + − −  +     2 1 (1 ) 1 ( , )k k k k k m m m m m d y x +    + − −       2 2 0( , ) (1 ) ( , ) k k k k km m m m md a z d a z M  − −   . Отсюда lim ( , ) lim ( , ) 0. k k k km m m m k k d x y d z y → → = = Рассуждениями, подобными вышеизложенным, показываем, что частичные слабые пределы последовательностей ( ), kmx ( ) kmy и ( ) kmz принадлежат множе- ству .S Как и ранее, получаем 2 2 0lim ( ( , ) (1 ) ( , )) 0. k km m k d a z d a z → − −  Далее для достаточно больших номеров k имеем 2 2 2 2 1 0 0 0( , ) (1 ) ( , ) ( ( , ) (1 ) ( , )) k k k k k km m m m m md x z d x z d a z d a z+  − + − −  2 2 2 1 0 0(1 ) ( , ) ( ( , ) (1 ) ( , )). k k k k km m m m md x z d a z d a z+ − + − − Отсюда, учитывая свойство iii, получаем 2 0( , )kd x z  2 1 0( , ) kmd x z+  2 2 0( , ) (1 ) ( , ). k km md a z d a z− − 24 ISSN 0572-2691 Таким образом, 2 0lim ( , )k k d x z →  2 2 0lim ( ( , ) (1 ) ( , )) 0. k km m k d a z d a z → − −  Следовательно, 0lim ( , ) 0n n d x z → = и, в свою очередь, 0lim ( , )n n d y z → = 0lim ( , ) 0.n n d z z → = = ■ Замечание 4. Если бифункция :F C C → обладает более сильным свой- ством липшицевого типа: 0 :с  ( , ) ( , ) ( , ) ( , ) ( , )F x y F x z F z y сd x z d z y + + , , ,x y z C  то вместо (9) в алгоритме 1 можно использовать правило 1 , если ( , ) ( , ) ( , ) 0, ( , ) ( , ) min , , иначе. ( ( , ) ( , ) ( , )) n n n n n n n n n n n n n n n n n n n F x z F x y F y z d x y d z y F x z F x y F y z +  − −    =      − −  Для полученного такой модификацией алгоритма будет справедлив анало- гичный теореме 1 результат о сходимости. Вариант алгоритма для вариационных неравенств Рассмотрим частный случай задачи о равновесии: вариационное неравенство в гильбертовом пространстве :H найти :x С ( , ) 0Ax y x−  .y С  (26) Предположим, что выполнены следующие условия: множество C H выпук- лое и замкнутое; оператор :A C H→ псевдомонотонный, липшицевый и секвен- циально слабо непрерывный; множество решений (26) не пусто. Пусть CP — оператор метрического проектирования на выпуклое замкнутое множество ,C т.е. CP x — единственный элемент множества C со свойством minC z C P x x z x  − = − . Для вариационных неравенств (26) алгоритм 1 принимает следующий вид. Алгоритм 2 Инициализация. Выбираем элементы ,a C 1 ,x С числа (0,1), 1  (0, ) + и последовательность ( ),n такую, что (0,1),n  lim 0,n n→  = 1 nn  =  = + . Полагаем 1.n = Шаг 1. Вычислить ( ).n C n n ny P x Ax= − Шаг 2. Вычислить ( ).n C n n nz P x Ay= − Шаг 3. Вычислить 1 (1 ) .n n n nx a z+ =  + − Шаг 4. Вычислить 2 2 1 , если ( , ) 0, min , , иначе. 2 ( , ) n n n n n n n n n n n n n n n Ax Ay z y x y z y Ax Ay z y +  − −     = − + −     − −    Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 25 Положить : 1n n= + и перейти на шаг 1. Из теоремы 1 вытекает следующий результат. Теорема 2. Пусть H — гильбертово пространство, C X — непустое вы- пуклое замкнутое множество, оператор :A C H→ псевдомонотонный, липшице- вый, секвенциально слабо непрерывный и существуют решения (26). Тогда по- рожденные алгоритмом 2 последовательности ( ),nx ( )ny и ( )nz сильно сходятся к проекции элемента a на множество решений вариационного неравенства (26). Замечание 5. Если оператор A монотонный, то результат теоремы 2 спра- ведлив без предположения о секвенциальной слабой непрерывности оператора .A Заключение В данной работе, продолжающей статью [13], рассматриваются общие задачи о равновесии в метрических пространствах Адамара. Для приближенного реше- ния задач предложен и изучен регуляризованный адаптивный экстрапроксималь- ный алгоритм. Алгоритм имеет следующую структуру 2 ( , ) 2 ( , ) 1 1 prox arg min ( , ) ( , ) , 2 1 prox arg min ( , ) ( , ) , 2 (1 ) , n n n n n F x n y C n n n n F y n y C n n n n n n n y x F x y d y x z x F y y d y x x a z       +    = = +        = = +     =   −  где (0,1),n  lim 0,n n→  = 1 nn  =  = + , а 0n  подбирается адаптивно. В отличие от применяемых ранее [5, 8, 17, 19] правил выбора величины шага, в пред- лагаемом алгоритме не производится вычислений значений бифункции в дополни- тельных точках и не требуется знаний о ее липшицевых константах. Для псевдомоно- тонных бифункций липшицевого типа доказана теорема о сходимости порожденных алгоритмом последовательностей ( ),nx ( )ny и ( )nz к проекции элемента a на мно- жество решений задачи о равновесии. Доказательство опирается на результаты и тех- нику работ [8, 13, 26, 28]. Показано, что предложенный алгоритм применим к псевдо- монотонным вариационным неравенствам в гильбертовых пространствах. В одной из ближайших работ авторы планируют рассмотреть более специ- альные варианты изученного регуляризованного адаптивного алгоритма для вари- ационных неравенств и минимаксных задач на многообразиях Адамара (напри- мер, на многообразии симметричных положительно определенных матриц). ABSTRACTS Я.І. Ведель, С.В. Денисов, В.В. Семенов РЕГУЛЯРИЗОВАНИЙ АДАПТИВНИЙ ЕКСТРАПРОКСИМАЛЬНИЙ АЛГОРИТМ ДЛЯ ЗАДАЧІ ПРО РІВНОВАГУ В ПРОСТОРАХ АДАМАРА Одним із напрямків сучасного прикладного нелінійного аналізу, що інтенсивно роз- вивається, є дослідження задач про рівновагу, відомих як нерівності Кі Фаня, задачі рівноважного програмування. У вигляді задачі про рівновагу можна сформулювати варіаційні нерівності, задачі математичного програмування, пошук рівноваги Неша. Останнім часом виник обумовлений проблемами математичної біології та машин- ного навчання інтерес до побудови теорії та алгоритмів розв’язання задач матема- тичного програмування в метричних просторах Адамара. У даній роботі розгляда- ються загальні задачі про рівновагу в метричних просторах Адамара. Для наближе- 26 ISSN 0572-2691 ного розв’язання задач запропоновано та досліджено новий ітераційний регуляри- зований адаптивний екстрапроксимальний алгоритм. На відміну від правил вибору величини кроку, що застосовувалися раніше, в запропонованому алгоритмі не про- водиться обчислень значень біфункції в додаткових точках та не потрібно знання про величину її ліпшіцевих констант. Для регуляризації базової екстрапроксимальної схеми використано класичну схему Гальперна. Для псевдомонотонних біфункцій лі- пшіцевого типу доведено теорему про збіжність породжених алгоритмом послідов- ностей. Доведення засновано на використанні фейєрівської властивості екстрапрок- симального алгоритму відносно множини розв’язків задачі та відомих результатів про збіжність схеми Гальперна. Показано, що запропонований алгоритм можна за- стосувати до псевдомонотонних варіаційних нерівностей в гільбертових просторах. Ключові слова: регуляризація, адаптивність, збіжність, екстрапроксимальний алгоритм, схема Гальперна, задача про рівновагу, псевдомонотонність, простір Адамара. Ya.I. Vedel, S.V. Denisov, V.V. Semenov REGULARIZED ADAPTIVE EXTRA-PROXIMAL ALGORITHM FOR EQUILIBRIUM PROBLEM IN HADAMARD SPACES One of the intensively developing areas of modern applied nonlinear analysis is the study of equilibrium problems, also known as Ky Fan inequalities, equilibrium programming problems. In the form of an equilibrium problem, one can formulate variational inequali- ties, mathematical programming problems, and many game theory problems (search of Nash equilibrium). Recently, interest has arisen due to the problems of mathematical biol- ogy and machine learning to construct the theory and algorithms for solving mathematical programming problems in Hadamard metric spaces. In this paper, we consider equilibrium problems in Hadamard metric spaces. For an approximate solution of problems, a new it- erative regularized adaptive extra-proximal algorithm is proposed and studied. 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 infor- mation on of bifunction’s Lipschitz constants. For regularization of basic extra-proximal scheme, the classic Halpern scheme is used. For pseudo-monotone bifunctions of Lip- schitz type, the theorem on convergence of sequences generated by the algorithm is proved. The proof is based on the use of the Fejer property of the extra-proximal algorithm with respect to the set of solutions of problem and known results on the convergence of the Halpern scheme. It is shown that the proposed algorithm is applicable to pseudo-monotone variational inequalities in Hilbert spaces. Keywords: regularization, adaptivity, convergence, extra-proximal algorithm, Hal- pern scheme, equilibrium problem, pseudo-monotonicity, Hadamard space. REFERENCES 1. Kassay G., Radulescu V.D. Equilibrium problems and applications. London : Academic Press, 2019. xx+419 p. 2. Antipin A.S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997. 37. P. 1285–1296. https://doi.org/10.1134/S0965542507120044 3. 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 4. Combettes P.L., Hirstoaga S.A. Equilibrium programming in Hilbert spaces. J. Nonlinear Convex Anal. 2005. 6. P. 117–136. 5. Quoc T.D., Muu L.D., Hien N.V. Extragradient algorithms extended to equilibrium problems. Optimization. 2008. 57. P. 749–776. https://doi.org/10.1080/02331930601122876 6. Semenov V.V. On the parallel proximal decomposition method for solving the problems of con- vex optimization. Journal of Automation and Information Sciences. 2010. 42, N 4. P. 13–18. https://doi.org/10.1615/JAutomatInfScien.v42.i4.20 7. Lyashko S.I., Semenov V.V., Voitova T.A. Low-cost modification of Korpelevich’s methods for monotone equilibrium problems. Cybernetics and Systems Analysis. 2011. 47, N 4. P. 631−639. https://doi.org/10.1007/s10559-011-9343-1 8. Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of solutions the equilibrium problems. In Zgurovsky M.Z. and Sadovnichiy V.A. (eds.). Continuous Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 5 27 and distributed systems. Solid Mechanics and Its Applications. 2014. 211. P. 131–146. https:// doi.org/10.1007/978-3-319-03146-0_10 9. Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of equi- librium programming. In Goldengorin B. (ed.). Optimization and its applications in control and data sciences. Springer Optimization and Its Applications. 2016. 115. P. 315−325. https:// doi.org/10.1007/978-3-319-42056-1_10 10. Colao V., Lopez G., Marino G., Martin-Marquez V. Equilibrium problems in Hadamard mani- folds. Journal of Mathematical Analysis and Applications. 2012. 388. P. 61–77. https://doi. org/10.1016/j.jmaa.2011.11.001 11. Khatibzadeh H., Mohebbi V. Monotone and pseudo-monotone equilibrium problems in Hada- mard spaces. Journal of the Australian Mathematical Society. 2019. P. 1–23. https://doi.org/ 10.1017/S1446788719000041 12. Khatibzadeh H., Mohebbi V. Approximating solutions of equilibrium problems in Hadamard spaces. Miskolc Mathematical Notes. 2019. 20, N 1. P. 281–297. https://doi.org/10.18514/ MMN.2019.2361 13. Ведель Я.И., Голубева Е.Н., Семенов В.В., Чабак Л.М. Адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах Адамара. Международный научно- технический журнал «Проблемы управления и информатики». 2020. № 4. С. 21–33. 14. Kinderlehrer D. Stampacchia G. An introduction to variational inequalities and their applications. New York : Academic Press, 1980; Russian transl., Moscow : Mir, 1983. 256 p. 15. Korpelevich G.M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. 12, N 4. P. 747–756. 16. Nadezhkina N., Takahashi W. Weak convergence theorem by an extragradient method for nonex- pansive mappings and monotone mappings. Journal of Optimization Theory and Applications. 2006. 128. P. 191–201. https://doi.org/10.1007/s10957-005-7564-z 17. Nemirovski A. Prox-method with rate of convergence O(1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point prob- lems. SIAM J. Optim. 2004. 15, N 1. P. 229–251. https://doi.org/10.1137/S1052623403425629 18. Denisov S.V., Semenov V.V., Stetsyuk P.I. Bregman extragradient method with monotone rule of step adjustment. Cybernetics and Systems Analysis. 2019. 55, N 3. P. 377–383. https://doi. org/10.1007/s10559-019-00144-5 19. Stonyakin F.S., Vorontsova E.A., Alkousa M.S. New version of mirror prox for variational inequalities with adaptation to inexactness. In Jaćimović M., Khachay M., Malkova V., Posypkin M. (eds.). Opti- mization and Applications. OPTIMA 2019. Communications in Computer and Information Science. Cham : Springer, 2020. 1145. P. 427–442. https://doi.org/10.1007/978-3-030-38603-0_31 20. Malitsky Yu.V., Semenov V.V. An extragradient algorithm for monotone variational inequalities. Cyber- netics and Systems Analysis. 2014. 50, N 2. P. 271–277. https://doi.org/10.1007/s10559-014-9614-8 21. Semenov V.V. A strongly convergent splitting method for systems of operator inclusions with monotone operators. Journal of Automation and Information Sciences. 2014. 46, N 5. P. 45–56. https://doi.org/10.1615/JAutomatInfScien.v46.i5.40 22. Semenov V.V. Hybrid splitting methods for the system of operator inclusions with monotone operators. Cybernetics and Systems Analysis. 2014. 50, N 5. P. 741–749. https://doi.org/10.1007/s10559-014-9664-y 23. Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators. Journal of Automation and Information Sciences. 2015. 47, N 7. P. 31–46. https://doi.org/10.1615/JAutomatInfScien.v47.i7.40 24. Semenov V.V. A version of the mirror descent method to solve variational inequalities. Cyberne- tics and Systems Analysis. 2017. 53, N 2. P. 234−243. https://doi.org/10.1007/s10559-017-9923-9 25. Bauschke H.H., Combettes P.L. Convex analysis and monotone operator theory in Hilbert spaces. Berlin; Heidelberg; New York : Springer, 2011. 408 p. 26. Bacak M. Convex analysis and optimization in Hadamard spaces. Berlin; Boston : De Gruyter, 2014. viii+185 p. 27. Halpern B. Fixed points of nonexpanding maps. Bull. Amer. Math. Soc. 1967. 73. P. 957–961. https://doi.org/10.1090/S0002-9904-1967-11864-0 28. Mainge P.-E. Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization. Set-Valued Analysis. 2008. 16. P. 899–912. https://doi.org/10.1007/s11228-008-0102-z. 29. Kirk W., Shahzad N. Fixed point theory in distance spaces. Cham : Springer, 2014. xii+173 p. https://doi.org/10.1007/978-3-319-10927-5 30. Burago D., Burago Yu., Ivanov S. A course in metric geometry. Graduate Studies in Mathemat- ics. 33. Providence : AMS, 2001. xiv+415 p. Получено 14.05.2020 Статья рекомендована к публикации чл.-корр. НАН Украины С.И. Ляшко. javascript:void(0) javascript:void(0)

Регуляризованный адаптивный экстрапроксимальный алгоритм для задачи о равновесии в пространствах адамара

Institution

Ähnliche Einträge