Геометрические и аппроксимативные свойства слабо выпуклых множеств в пространствах с несимметричной полунормой Лопушански Мариана Сергеевна

Введение к работе

Актуальность темы исследования и степень ее разработанности. Выпуклый анализ играет важную роль при решении задач оптимизации и аппроксимации. Для задач выпуклой оптимизации разработаны гораздо более эффективные алгоритмы решения, чем для задач невыпуклой оптимизации. Тем не менее, для многих практических задач классическое понятие выпуклости недостаточно информативно, оно носит лишь качественный характер. Более информативное описание свойств выпуклости функций и множеств дает интенсивно развивающийся в последние годы параметрически выпуклый анализ, рассматривающий количественные параметры, показывающие, насколько множество или функция сильно выпуклы или насколько они отличаются от выпуклых.

Понятие сильно выпуклой функции было введено Б.Т. Поляком. Он доказал сходимость алгоритмов решения задач условной оптимизации. Позже было показано, что алгоритмы минимизации сильно выпуклых функций сходятся значительно быстрее алгоритмов минимизации выпуклых функций (см., например, монографию Ю.Е. Нестерова). В 1975 году А. Плиш ввел понятие сильно выпуклых множеств (А. Плиш называл эти множества -регулярными) и использовал их для исследования множеств достижимости нелинейных управляемых систем. Множество называется -сильно выпуклым, если оно представимо в виде пересечения замкнутых шаров радиуса . В работах Г.Е. Иванова и Е.С. Половинкина теория сильно выпуклых множеств была применена для построения высокоэффективных алгоритмов поиска оптимальных стратегий в дифференциальных играх. Другие приложения сильно выпуклых множеств описаны в работах С. Лоджасевича, Х. Франковской и Ч. Олеха, М.А. Красносельского и А.В. Покровского. Подробно свойства сильно выпуклых множеств изучены в статьях Е.С. Половинкина и в

его книге в соавторстве с М.В. Балашовым.

Задача минимизации сильно выпуклой функции на выпуклом множестве подробно рассмотрена в монографии Ю.Е. Нестерова. Задача минимизации выпуклой функции на сильно выпуклом множестве рассмотрена в работах М.В. Балашовым и М.О. Голубевым, а также в диссертации М.О. Голубева, где доказана сходимость метода проекции градиента со скоростью геометрической прогрессии. М.В. Балашов доказал сходимость этого метода с такой же по порядку скоростью для задач оптимизации невыпуклых, но гладких функций на сильно выпуклом множестве. Таким образом, условия сильной выпуклости (по сравнению с классическими условиями выпуклости) дают возможность строить более эффективные алгоритмы решения оптимизационных задач.

Другая часть параметрически выпуклого анализа – теория слабо выпуклых множеств и функций, – позволяет применять методы выпуклого анализа к невыпуклым объектам, обладающим некоторыми ослабленными свойствами выпуклости. К таким объектам относятся гладкие (в определенном смысле) множества и функции. Одним из важнейших вопросов теории оптимизации является вопрос о применимости алгоритмов для численного решения той или иной задачи (например, для того, чтобы использовать метод проекции градиента, необходимо доказать существование проекции точки на множество, но, как известно, в случае произвольного множества проекции может не существовать). На практике возникают невыпуклые объекты, для которых классические методы и теоремы выпуклого анализа неприменимы. Теория слабо выпуклых множеств и функций позволяет применить методы выпуклого анализа и известные численные методы для решения задач оптимизации к невыпуклым объектам.

Различные понятия слабо выпуклых множества в конечномерных пространствах рассматривали Н.В. Ефимов и С.Б. Стечкин (множества,

слабо выпуклые по Ефимову-Стечкину), Г. Федерер (множества положительной достижимости) и Ж.-Ф. Виаль (слабо выпуклые множества). Позже было доказано, что в конечномерном пространстве класс множеств, введенный Г. Федерером эквивалентен классу множеств, введеному Ж.-Ф. Виалем.

Ф. Кларк, Р. Штерн и П. Воленски обобщили понятие множества положительной достижимости на гильбертовы пространства, введя понятие проксимально гладкого множества - т.е. множества А, для которого существует такое число R > 0, что функция расстояния р(-,А) непрерывно дифференцируема в U(R,A), где р(х,А) = іпї_аЄА \\х — а\\ - расстояние от точки х є Е до множества А с Е, а U(R,A) = {х є Е : 0 < р(х,А) < R] - Л-окрестность множества А.

Р. Поликвин и Р. Рокафеллар рассматривали прокс-регулярные множества в гильбертовом пространстве. Р. Поликвин, Р. Рокафеллар и Л. Тибо доказали, что класс равномерно прокс-регулярных множеств совпадает с классом проксимально гладких множеств. Ф. Бернард, Л. Тибо и Н. Златева рассматривали прокс-регулярные и проксимально гладкие множества в равномерно выпуклых и равномерно гладких банаховых пространствах.

В монографии Г.Е. Иванова 2006 года подробно исследуются слабо выпуклые по Виалю множества в гильбертовом пространстве. Г.Е. Иванова доказал, что в гильбертовом пространстве из слабой выпуклости по Виалю следует слабая выпуклость по Ефимову-Стечкину, и приведен пример, что обратное неверно. Балашова и Г.Е. Иванова доказали, что метрическая проекция точки на слабо выпуклое множество липши-цева относительно точки и гелдерова с коэффициентом ^ относительно множества.

М.В. Балашов и Г.Е. Иванов исследовали различные понятия сла-

бой выпуклости в равномерно гладких и равномерно выпуклых банаховых пространствах.

В работах А.Р. Алимова и И. Г. Царькова, а так же в докторской диссертации А.Р. Алимова были изучены свойства множеств, слабо выпуклых по Виалю с константой R в пространствах, которые не являются ни равномерно выпуклыми, ни равномерно гладкими.

Как было сказано выше, класс слабо выпуклых множеств шире класса выпуклых множеств, но слабо выпуклые множества обладают многими полезными свойствами выпуклых множеств и часто используются при решении задач, имеющих практическое значение - например, в теории дифференциальных включений, в теории дифференциальных игр, в теории многозначных отображений, при исследовании алгоритма метода проекции градиента.

Параллельно с теорией слабо выпуклых множеств в последние годы интенсивно развивается теория слабо выпуклых функций. Различные авторы давали различные определения и названия для слабо выпуклых функций. Р. Джанин рассматривал в Ш^п класс PC2 функций, локально разложимых в сумму выпуклой функции и положительно определенной квадратичной функции. Р.-Т. Рокафеллар ввел и изучал класс lower — С² функций, представимых как максимум семейства квадратичных функций. Р.-Т. Рокафеллар продемонстрировал удобство применения введенных им функций в субградиентной оптимизации. Функция / : Е —> Ш U {+оо} называется слабо выпуклой c константой С > 0, если функция f(x) + ^\\x\\² является выпуклой функцией. Это определение

предложил Ж.-Ф. Виаль. Он исследовал свойства таких функций в W¹ и показал совпадение этого класса с классами PC2 и lower — С² функций. В гильбертовом пространстве слабо выпуклые функции подробно исследованы в монографии Г.Е. Иванова. В банаховом пространстве различные авторы рассматривали другие классы функций, совпадающие с

классом слабо выпуклых функций в случае гильбертова пространства. Ф. Бернард, Л. Тибо и Н. Златева рассматривали класс - функций в банаховом пространстве. Они установили некоторую связь между свойством - и равномерной прокс-регулярностью надграфика этой функции. В R классы - , - ² и 2 функций совпадают с классом слабо выпуклых функций, но в неевклидовом пространстве эти классы различны.

На практике часто возникают задачи наилучшего приближения, в которых роль нормы играет несимметричная норма, т.е. выпуклая положительно однородная и положительно определенная (т.е. положительная везде, кроме нуля) функция, но, в отличие от нормы, не обязательно симметричная. Иначе говоря, несимметричная норма - это функционал Минковского некоторого выпуклого замкнутого ограниченного и поглощающего множества. Несимметричная норма (как функционал Минковского) впервые возникла в работах Г. Минковского, где исследовались ее свойства в конечномерных пространствах. Пространства с несимметричной нормой подробно исследовались в работах Ш. Кобза-ша, К. Алегре, С. Ромагуера, П.А. Бородина, А.Р. Алимова и др. Задачи наилучшей аппроксимации в пространствах с несимметричной нормой рассматривались в работах Ч. Дунхама, Р. Даффина и Л. Карловитца, Ф. Де Блази и Дж. Мижака. Использование несимметричной нормы для анализа сложности программ подробно описано в совместных работах С. Ромагуеры и М. Шеллекенса.

Ослабляя в определении несимметричной нормы условие положительной определенности до условия неотрицательности, приходим к более общему определению несимметричной полунормы. Иначе говоря, несимметричная полунорма - это функционал Минковского некоторого выпуклого замкнутого и поглощающего, но не обязательно ограниченного множества, которое будем называть квазишаром. Квазишар играет

роль единичного шара в пространствах с несимметричной полунормой. Такие пространства исследовались в работах Ш. Кобзаша.

В теории методов оптимизации огромное значение играет понятие корректности задачи, в частности, корректности по Тихонову. Корректность задач оптимизации позволяет строить устойчивые алгоритмы решения этих задач. Задача mm_xeEf(x) называется корректной по Тихонову (где / : Е —> Ш U {+оо}), если любая минимизирующая последовательность сходится к точке минимума этой задачи. Г. Е. Ивановым получена характеризация свойства слабой выпуклости множества А в терминах корректности по Тихонову задачи наилучшего приближения точки из чебышевского слоя.

Г.Е. Иванов ввел понятие сильно выпуклой функции в банаховом пространстве и доказал, что задача поиска минимума инфимальной кон-волюции сильно выпуклой и слабо выпуклой функции корректна по Тихонову.

В 1920-х годах С. Банах и Г. Хан независимо доказали классическую теорему об отделимости двух выпуклых непересекающихся множеств гиперплоскостью. Однако два невыпуклых непересекающихся множества в общем случае неотделимы гиперплоскостью. Но если одно множество сильно выпукло, а другое слабо выпукло, то при определенном соотношение параметров выпуклости их можно отделить границей шара. Для гильбертова пространства это доказано в книге Г. Е. Иванова. В равномерно выпуклого и равномерно гладкого банахова пространства этот результат получен в работе М. В. Балашова и Г. Е. Иванова.

Теория многозначных отображений подробно изложена в монографии Е.С. Половинкина. Исследования непрерывности пересечения многозначных отображений велись, например, в работах Ж.-Ж. Моро, Дж. Де Блази и Дж. Пьяниджани, Ж.-П. Пено. Известно, что пересечение двух выпуклозначных, компактнозначных и непрерывных многозначных

отображений может не быть непрерывным. М.В. Балашов и Д. Реповш показали, что если два многозначных отображения непрерывны и значения одного из них выпуклы и замкнуты, а значения другого равномерно выпуклы, то многозначное отображение, заданное как пересечение их значений будет непрерывным. Г.Е. Иванов доказал непрерывность многозначного отображения, заданного как пересечение значений двух непрерывных многозначных отображений, значения одного из которых замкнуты и слабо выпуклы, а значения другого замкнуты и равномерно выпуклы.

В связи с тем, что в задачах оптимизации естественным образом возникают недифференцируемые функции, для исследования таких функций потребовалось разработать аналог дифференциального исчисления. В. Фенхель в начале 50-х годов двадцатого века ввел понятие субдифференциала выпуклой функции, что позволило сформулировать аналог теоремы Ферма о необходимом условии минимума. Для невыпуклых функций субдифференциал Фенхеля может быть пустым, что существенно ограничивает его применение. В работах начала 70-х годов двадцатого века Ф. Кларк предложил ввести обобщенный градиент (позже названный субдифференциалом Кларка) для негладких невыпуклых функций и заложил основы негладкого анализа. С этого времени негладкий анализ довольно активно развивался, в том числе в работах Ф.Кларка, Р.-Т. Рокафеллара, Б.Ш. Мордуховича, Б.Н. Пшеничного, А.Д. Иофе, В.М. Тихомирова, В.Ф. Демьянова, А.М. Рубинова, их коллег и учеников.

Субдифференциал Кларка во многих задачах оказывается слишком широким, что делает его применение малоэффективным. С другой стороны, было доказано что субдифференциал Кларка является минимальным по включению среди всех выпуклозначных и робастных (т.е. устойчивых по отклонению аргумента) субдифференциалов.

Независимо от Ф. Кларка Б.Ш. Мордухович ввел понятие предельного субдифференциала, обладающего некоторыми свойствами робаст-ности, но значения которого не обязательно выпуклые. Предельный субдифференциал Мордуховича содержится в субдифференциале Кларка, поэтому дает более точные необходимые условия оптимальности. Известно, что индикаторная функция множества (равная нулю в точках этого множества и + вне множества) однозначно определяет само множество. Рассматривая субдифференциал (в том или другом смысле) индикаторной функции множества, приходим к определению нормального конуса (в соответствующем смысле) этого множества. Таким образом, были введены и изучались нормальные конусы множеств в смысле Кларка, Мордуховича, Фреше, конус проксимальных нормалей и др.

Хорошо известно, что для выпуклой функции субдифференциалы во всех перечисленных выше смысле совпадают. Также совпадают и нормальные конусы во всех выше перечисленных смыслах, если множество выпукло. В связи с тем, что различные типы субдифференциалов и нормальных конусов обладают различными свойствами, важными в приложениях, весьма актуальным является вопрос об описании достаточно широкого класса функций, для которых субдифференциалы различных типов совпадают и тем самым сочетают в себе свойства субдифференциалов того и другого типов. Эту задачу подробно исследовали Ф. Кларк, Б.Ш. Мордухович, Р. Поликвин, Р. Рокафелар, Л. Тибо, Ф. Бернард, Н. Златева и другие.

Цели и задачи работы. Разработать единый подход к исследованию слабо выпуклых множеств и функций. Исследовать геометрические и аппроксимативные свойства слабо выпуклых множеств в пространствах с несимметричной полунормой.

Научная новизна. Все результаты, полученные в работе, являются новыми.

Теоретическая и практическая ценность. Теоремы о корректности по Тихонову задач поиска ближайших точек дают основу для построения устойчивых алгоритмов решения задач условной оптимизации. Остальные результаты работы носят теоретический характер.

Методология и методы исследования. В работе используются различные методы функционального анализа, выпуклого анализа, многозначного анализа и геометрии банаховых пространств.

Положения, выносимые на защиту.

1. Теорема о чебышевском слое для слабо выпуклых множеств в пространствах с несимметричной полунормой.

2. Теорема о корректности по Тихонову задачи поиска ближайших точек между слабо выпуклым и сильно выпуклым множествами в пространствах с несимметричной полунормой.

3. Теоремы об исчислении параметров выпуклости и о замкнутости суммы Минковского в пространствах с несимметричной полунормой.

4. Теорема об отделимости границей квазишара двух непересекающихся или касающихся множеств, одно из которых слабо выпукло, а другое - сильно выпукло.

5. Теорема о нормальной регулярности слабо выпуклых множеств в пространствах с несимметричной полунормой.

Степень достоверности и апробация результатов. Все результаты строго доказаны. Результаты, изложенные в диссертации, в разное время докладывались и обсуждались на

54-й, 55-й, 56-й и 60-й научных конференциях МФТИ – Всероссийских научных конференциях «Современные проблемы фунда-11

ментальных и прикладных, естественных и технических наук в современном информационном обществе», Москва – Долгопрудный, 2011, 2012, 2013, 2017.

VI международной конференции «Динамические системы: устойчивость, управление, оптимизация», Минск, 2013.

международной конференции «27-th IFIP TC7 Conference on System Modelling and Optimization», Sophia Antipolis, France, 2015.

научных семинарах кафедры высшей математики МФТИ, Москва – Долгопрудный, 2011 – 2017.

научном семинаре «Геометрическая теория приближений» кафедры теории функций и функционального анализа механико-математического факультета МГУ, Москва, 2017.

международной конференции «Constructive Nonsmooth Analysis and Related Topics», Санкт-Петербург, 2017.

международной конференции «Quasilinear Equations, Inverse Problems and Their Applications», Долгопрудный, 2017.

Основные результаты работы опубликованы в десяти работах [1-10], пять из которых [2], [6], [7], [8], [9] – в изданиях, рекомендованных ВАК. Основные результаты диссертации и положения, выносимые на защиту, отражают личный вклад соискателя в работах с соавторами, в частности, в [2] – доказательство теоремы о диаметре эпсилон-проекции и теоремы о чебышевском слое в пространстве с несимметричной полунормой, в [6] – доказательство корректности по Тихонову задачи поиска ближайших точек для множеств, одно из которых сильно выпукло, а другое слабо выпукло относительно квазишара, в [7] – доказательство теоремы об исчислении параметров выпуклости

суммы Минковского и теоремы о замкнутости суммы Минковского двух множеств, в [8] – доказательство выпуклости контингентного конуса к слабо выпуклому относительно квазишара множества и доказательство теоремы об отделимости в пространствах с несимметричной полунормой.

Структура работы. Работа состоит из введения, четырех глав глав, заключения и списка литературы, насчитывающего 100 наименований. Общий объем диссертации равен 135 страницам.