Некоторые вопросы сильно выпуклого анализа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Л г О Л П пРавах рукописи

г Г О Ш1

1 1 СЕН 1Ь9Ь

Балашов Максим Викторович

НЕКОТОРЫЕ ВОПРОСЫ СИЛЬНО ВЫПУКЛОГО АНАЛИЗА

01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Долгопрудный • 1998

Работа выполнена на кафедре высшей математики Московского физико-технического института

Научный руководитель:

доктор физико-математических наук,

профессор Половинкин,Е. С.

Официальные оппоненты:

доктор физико-математических наук,

профессор Арутюнов А. В.

доктор физико-математических наук,

доцент Асеев ¡С. М.

Ведущая организация:

Институт математики и механики УрО РАН

Защита состоится "_"__ 1998 г. в__ч. на заседании

Диссертационного совета К 063.91.03 при МФТИ в Московском физико-техническом институте по адресу: 141700, г. Долгопрудный, Моск. обл., Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ.

Автореферат разослан 1998г.

Ученый секретарь специализированного совета

доктор физико-математических наук Самыловский А. И.

Ак-уальность проблемы.

Сильно выпуклый анализ возник как раздел выпуклого анализа, в котором исследовались сильно выпуклые множества с радиусом R, т.е. мной ?ства, образованные пересечением замкнутых шаров одного радиуса R из R".

Впервые, по-видимому, термин "сильная выпуклость" в отношении множеств введен в обиход Б.Т. Поляком. Он использовал понятие сильно выпуклого множества (несколько отличающееся от нашего) в задачах оптимизации, получив новые результаты о сходимости минимизирующих последовательностей.

A. Plis использовал свойства сильно выпуклых множеств для исследования свойств решений дифференциальных вкл: чений.

В монографии М.А. Красносельского и А.З. Покровского "Системы с гистерезисом" показано, что свойства сильно выпуклых множеств обеспечивают хорошие свойства систем с гистерезисом.

Впервые серьезное внимание собственно проблемам сильной выпуклости было уделено в работах H. Frankowska, Ch. Olee'-, и Е.С. Половин-кнна.

H. FVankowska и Ch. Olech изучали условия, при которых интеграл от многозначного отображения является сильно выпуклым множеством. При этом существенное внимание было уделено исследованию свойств сильно выпуклых множеств из R". Так, было доказано, что градиент опорной функции аыпуклого компакта удовлетворяет условию Липшица на поверхности единичного шар_ из R" тогда и только тогда, когда компакт сильно выпуклый. Таким образом, было показано, что "гладкость" для сильно выпуклых множеств имеет местп для двойственных объектов — опорных функций, в то время, как сами множества могут иметь "плохую", "негладкую" границу. Кроме того, были доказаны некоторые новые критерии сильной выпуклости, например, что выпуклый компакт из В." является пересечением шаров радиуса R тогда и только тогда, когда любая дуга окружности радиуса R длины не более 7гR с концами из компакта целиком лежит в этом компакте. Были также установлены некоторые метрические соотношения, имеющие место для граничных точек сильно выпуклых множеств.

В работах Е.С. Половинкина были установлены важные свойства сильно выпуклых множеств. Впервые бып получен новый опорный принцип для множеств, являющихся пересечением замкнутых шаров из R". Было показано, что этот опорный принцип эквивалентен новому тину двойственности, когда полярным к сильно выпуклому с радиусом R множеству Л мы называем такой выпуклый компакт В (который,

К8ь доказано, всегда существует), что сумма множеств А 4 В есть шар радиуса R с центром в нуле. На основе hodc.i двойственности была построена теория сильно выпуклых множеств из R", доказаны обобщения теорем Каратеодори и Крейна-Мильмана для сильно выпуклых множеств в конечномерном евклидовом пространстве, исследованы сильно выпуклые аппроксимации множеств и функций.

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

В связи с важными для приложений свойствами сильно выпуклых множеств встал вопрос о нахождении классов порождающих множеств (т.е. таких множеств М, что для любого непустого пересечения сдвигов множества М А = Л(А/ + лЛ найдется множество В, такое, что А+ В = М), обобщающих понятие сильно выпуклых множеств, и исследовании их свойств. Параллельно с этим встал естественный вопрос об обобщении понятий сильной выпуклости и порождаемости на случай бесконечномерных пространств. При этом термин "сильно выпуклый анализ" получил новое наполнение.

Настоящая работа посвящена исследованию свойств порождающих множеств и свойств сильно выпуклых > тожеств в банаховых пространствах и в R" и применению полученных результатов) к задачам многозначного анализа и оптимизации.

Целью настоящей работы пвл"ется:

1. Построение теории двойственности длп ограниченных порождающих множеств .в бесконечномерных пространствах, построение алгебры порождакн"их множеств, выявление классов порождающих множеств в бесконечномерных пространствах и в R".

2. Введение операции, обобщающей операцию взятия сильно выпуклой оболочки. Получение новых оценок многогранных аппроксимаций bR". Обобщение классических утверждений типа теорем Каратеодори и Крейна-Мильмана ни случай порождающих множеств.

3. Дальнейшее исследование сильно выпуклых множеств в R". Применение свойств порождающих и сильно выпуклых множеств к задачам выпуклого анализа и оптимизации.

Нэ} чнап новизна.

1. Получен усиленный опорный принцип для ограниченных порождающих множеств в рефлексивных банаховых (/ростраистцах. Доказано, что операция предельного перевода и линейный гомеоморфизм сохраняют свойство множества быть порождающим. Получены достаточные условия порождаемое™ для выпуклых компактов из Д". Доказано, что все выпуклые компакты в И2 порождающее. Указан способ построения порождающих множеств в К".

2. Введено понятие М-оболочки для выпуклого ограниченного множества М из рефлексивного банахова пространства. Исследованы свойства операции взятия М-оболочки суммы и геометрической разности множеств. Показано, что операция М-овыпукленш для порождающего множества М удовлетворяет условию Липшица в метрике Хаусдор-фа. Доказало обобщение теоремы Каратеодори на случай М-оболочки для порождающего множества М. Введенъ* внутренние и внешние многогранные аппроксимации М-выпуклых компактов, получены оценки погрешности этих аппроксимаций.

3. Доказано, что в полном гильбертовом пространстве шар является порождающим множеством. Введены понятия сильно Я-выступающей и сильно Я-крайней точек множества в гильбертовом пространстве, доказано обобщение теоремы Крейна-Мильмана: показано, что компакт содержится в Бд(0)-оболочке своих Я-крайних точек. Показано, что выпуклое замкнутое ограниченное множество в гильбертовом пространстве можно аппроксимировать с любоМ точностью в метрике Ха-усдорфа множеством, градиент опорной функции которого непрерывен по Липшицу на единичной сфере.

4. Для сильно выпуклых множеств из И" установлена связь между Я-крайними точками сильно выпуклой Я-оболочки компакта и самого компакта. Показано, что замыкания множеств сильно Я-выступающих и сильно Д-крайних точек совпадают. Получен новый критерий сильной выпуклости множества в 11".

5. Показано, что центр Штейнер« сильно выпуклой оболочки (и случае, когда оболочка непуста) выпуклого компактного множества из И" является чипшицевым селектором выпуклых компактных множестг. в метрике Хаусдорфа, отличным в общем случае от известного центра Штейнера. Получена формула, выражающа" новый селектор через интеграл Римана от опорной функции выпуклого компакта.

6. Показано, что лебеговы множества сильно выпуклой непрерывной по Липшицу функции являются сильно выпуклыми множествами в Я". Доказано, что сильно выпуклая непрерывная по Липшицу функция доо

тигает максимума на компакте из R" в Я-крайних точках выпуклого компакта, получена неулучшаемая оценка радиуса Я.

Предложен приближенный алгоритм максимизации выпуклой непрерывной по Липшицу функции на компакте, заданном системой линейных ограничений, "олучена оценка погрешности алгоритма.

Научно-практическое значение.

1. Опорный принцип для порождающих множеств является усилением известного опорного принцип,, и его обобщения на случай Ф-вы-пуклых множеств. При исследовании порождающих множеств получен ряд результатов, имеющих интерес для выпуклого анализа и приложений. Так, например, получены новые условия непрерывности и полунепрерывности геометрической разности многозначных отображений в банаховых пространствах и в R".

2. Полученные многогранные аппроксимации .¿/-выпуклых компактов из R" имеют меньшую погрешность, чем в общем случае, что показано на примерах.

3. Полученные обобщения теоремы Крейна-Мильмана в гильбертовом пространстве, теоремы Нарагеодорн для описания элементов М-оболочки компакта в R" и теорема о связи Я-крайних точек компакта и его Я-оболочки, помимо чисто теоретического интереса, оказались эффективным инструментом в задачах выпуклого анализа и оптимизации. Эти результаты позволили построить новый непрерывный не Липшицу селектор выпуклых компактов из R" в метрике Хаусдорфа и получить характеризацию точек, в которых липшнцева сильно выпуклая функция достигает максимума на компакте.

4. Разобраны примеры, показывающие, что свойство сильной выпуклости множеств дает в приложениях более сильные результаты, чем ( зойство выпуклости и строгой В' шуклости.

5. Приближенный алгоритм максимизации выпуклой липшицевой функции на компакте используется в пакете прикладных программ для решения линейных дифференциальных игр D1FGAM—1, созданном коллективом авторов, работающих на кафедре высшей математики М >ТИ (руководитель Е.С. Половецкий), при численном решении задачи нахождения выпуклой оболочки множества л во вспомогательных вычислениях.

Апробация работы, публикации. Полученные результаты докладывались на следующих конференциях и семинарах: на ЗУ и 40 научно-технических конференциях МФТИ в г. Долгопрудном в 1996 и 1997 годах, на научном семинаре института математики и механики УрО

РЛГ* в г. Екатеринбурге в феврале 1998г., на Воронежской весепней школе "Понтрягинские чтения — IX" в мае 1998г. Они опубликованы в работах [1], [2], [3], [4], [5].

Структура и объем работы: диссертационная работа состоит из введении, четырех глав и списка литературы из 52 наименований.

Краткое содержание работы

1. Ограниченные порождающие множества и их свойства.

Далее по тексту через Е, Е\, Еъ обозначим рефлексивное банахово пространство над вещественным полем скаляров, че^гз X будем обозначать замкнутое подмножество из Е.

Определение 1. Выпуклое замкнутое ограниченное множество М С Е назовем порождающим множество..I, если для любого множества А ф 0 вида А = П (М + х) найдется выпуклое замкнутое ограни-тех

ченное множество В С Е такое, что А + В = Л/.

Про последнее равенство в определении'1 говорят, что множество А полностью выметает множество Л/.

Определение 2. Для всякого порождающего множества М . тожество вида А = П (М + х) ф 0 будем называть Ы-выпуклым множеством. ХР"

В дальнейшем, говоря, что множество А А/-выпукло, мы всегда будем предполагать, что множество М — поро?кдающее множество.

Через Н(А, В) обозначим расстояние между множествами А н В в метрике Хаусдорфа. Пусть для р € Е" я(ргА) = зир(р,х)-, Вг(а) =

хел

{х € Е \ \\х — о|| < г}. Пусть для множества А С Е х* есть элемент множества А{р) = {х & А : {р,х) — ¿[р, Л)}, р 6 Е'. Для множеств А и В геометрической разностью называется множество А ± В = {а:: аг 4-ВС А).

Теорема 1. Пусть М С Е — порождающее множество. Тогда для любого М-выпуклого множества А имеет место двойственное описание: длп. любого р е 0В\(0) и для любого х* е А(р) сущестоус.п

4' е ЩрУ

л- п (¥ + *$-.«). (1)

Формулу (1) можно записать иначе

А— П П {М + х^-хУ^)). (2)

Ы.=1 **ел(Р)

В формуле (2) второе пересечение при фиксированном р берется по всем х* € Afp), Хр из М(р) зависит от х£.

Обратно, если выпуклое замкнутое ограниченное множество М таково, что любое множество А вида А — П (М + х) удовлетворяет (J),

их

то множество М — порождающее.

Следствие теоремы 1. Пусть А М-выпуклое множество. Тогда для любого р 6 Е', р ^ 0, и для любого х* 6 А{р) найдется х*' 6 Л/(р), что

АС\1+х$-

В работе рассматриваются основные свойства Л/-выпуклых множеств.

Приведем примеры конечномерных не порождающих и порождающих компактов.

Примеры.

1. со {(0,0,1), (1,1,0), (-1,1,0), (1,-1,0), (-1,-1,0)} не является порождающим множеством.

2. Множество, образованное вращением вокруг оси абсцисс малой дуги окружности радиуса 5 с центром кривизны в точке (3,-4,0) и концами в точках (0,0,0), (6,0,0), не является порождающим множеством.

3. Симплекс полной размерности а R" является порождающим множеством.

Будем понимать лолунепрерывиость многозначных отображений сверху (п.н. св.) и снизу (п.н. сн.) в смысле определений из монографии Д1.-П. Обена и И.Зкланда "Прикладной нелинейныГ анализ".

Следующая теорема является важным инструментом при доказательстве теорем 3 и 4.

Теорема 2. Пусть сепараОельиое пространство Е снабжено слабой топологией, Т полное метрическое пространство, Пусть F, G : Т Е многозначные отображения, такие, что образы F uG компактны в Е, F п.н. св., G п.н. ск. Пусть для всех t 6 Т H(t) = F(t)~G(f) / он замыкание выпуклой оболочки Н(Т) ограничено. Тогда И п.н. се.

Теорема 3. Пусть Е сепарабелъно, М С Е выпуклое замкнутое ограниченное множество с непустой внутренностью. Пусть для любого множества X, такого, что int (М — А') ф 0, найдется выпуклое множество В, для которого (М — Х) + В = А/. Тогда множество М — порождающее.

Теорема 4. Пусть в сегшрабелшом пространстве Е выпуклые множества порождающие и выполнено одно из двух условий: 1)

с

кЧ 'ь М) -у 0, ¡п(-,М Ф 0; 2) Мк Э М V* и Мк М слабо. Тогда М — порождающее множество.

Следствие теоремы 4. Пусть Л/* — последовательность порождающих множеств из И", -> 0 и М* С М для всех к. Тогда М — порождающее множество.

В работе разобран пример в пространстве К", показывающий, что условия теоремы 4 существенны.

Теорема 5. Пусть М — порождающее множество из Е. Тогда для любого р € сШ^О) множество М(р) будет порождающим в многообразии Нр — {а : (р, ее) = з(р, М)}.

Отметим, что в конечномерном пространстве, теорема 5 содержательна для нестрого выпуклых порождающих мяо ;еств.

Теорема 6. Пусть М С Е\ — порождающее множество и Т : Е\ Е2 — линейный гомеоморфизм. Тогда ТМ — порождающее множество в Е2.

Следствие теоремы 6. Любой эллипсоид в Л." есть порождающее множество.

В работе разобран пример в пространстве 11", показывающий, что условия теоремы 6 существенны.

В заключение отметим, что сумма Минковского порождающих множеств не является в общем случае порождающим множеством. Примером являются тетраэдры из И3

Е! = со {е0, -ей е2 |(е2 - 61) 4- ^е3}, Е2= со{е0,-е1,е2,1(е2-е1) - ^ез},

где е0 = 0, а {е;}?=1 ОНБ в И3.

Следующая теорема 7 дает достаточные условия порождаемости в И".

Теорема 7. Пусть М выпуклый компакт из К". Пусть р € сШ^О) произвольный вектор. Пусть для любых наборов векторов {р;}*=1 и чисел

{А*}*-!, таких, что |р,| = 1, А; > О, £ \р( = р, 2 < к < п и для любых

¡=1

Ху' £ М(р,) найдется х^' такой, что «=1

Тогда множество М — порождающее.

Теорема 8. Любой выпуклый компакт из

И2 является порождающим множеством. ^

Напомним, что прямой суммой множеств М\ С Е\ и Л/2 С Е% называется множество

Мх ф Мг = {(*ь г2) 6 Ех х Е2: 6 Мъ г2 6 ЛГ2}.

Теорема 9. Пг^ть С Е1 и Мг С £2 порождающие .множества. Тогда множество М\ ф М% порождающее в Е\ х

Теорема 10. Пусть У. — полное гильбертово пространство. Тогда шар в Л является порождающим множеством.

При доказательстве теоремы 10 проблема сводится к двумерному случаю и положительный ответ следует из теоремы 8.

Введем определение, обобщающее понятие выпуклой оболочки и сильно выпуклой оболочки.

Определение 3. Пусть М С Е — выл/, слое ограниченное замкнутое множество. М-оболочкой ограниченного множества Л, такого, что М — АфФ, называется множество со,\/Л — И - (М - А).

Теорема 11. Если М — порождающее множество и .4 такое множество, что М — А ф 0, то множество со и А есть наименьшее по включению М-выпуклое множесг■ во, содержащее А. При этом опорная функция этого множества задается формулой

*(р, сод/Л) = в(р,М) - со(л(р, М)-&(р,А)).

В работе рассматриваются основные свойства операции Л/-овыпук-1сния.

Приведем одну из теорем о липшнцевости операции Л/-овыпукления порождающим множеством в метрике Хаусдорфа.

Теорема 12. Пусть М С Е — порождающее множества, и Л2 множества из Е. Пусть существуют а — а(М, ЛьЛг) > 0 п х, С Е, что Ва(х^ С М~ Л;, 1 < г < 1. Пусть а > /¿(Ль А2). иусть П{М) = йттМ. Тогда ■

П(сомАисомА2) < —-Л(Ль Аг). я

Отметим, что константа Липшица в операции взятия Л/-об(!лочки в метрике Хаусдорфа больше 1 по существу (в отличии от константы Липшица операции взятия выпуклой оболочки множеств«, равной 1), что показано на примере.

Следующая теорема обобщает теорему Каратеодори на случай М-оболочки компактных порождающих множеств М из Я".

Теорема 13. Пусть М С К." порождающее множество. Пусть А — компактное множество из II", такое, что т1 (Л/ - Л) =/ 0. Тогда

л'оСid элемент множества со цА лежит в М-выпуклой оболочке не более чем п2 + 1 элемента из А. В случае, когда множество М строго выпукло, любой элемент со мА лежит в М-выпуклой оболочке не более чем 1 + 1 элемента из А.

Используя теорему

Теорема 14. Пусть выпуклый компакт F имеет eudF — PflQ, где Р С R" многогранник, a Q С R" строго выпуклый компакт (в частности, F может быть многогранником или строго выпуклым компактом). Пусть G(t) непрерывное многозначное отображение с компактными значениями, такое, что F — G(t) имеет непрерывный селектор. Тогда многозначное отображение H(t) = F — G(t) непрерывно.

и теорему 13, получаем следующий результат

Теорема 15. Пусть М С Rn порождающее множество, А компакт, М — Ау£ б. Тогда, если выполнено хотя бы одно из условий:

1) М строго выпуклый компакт;

2) М = Pf)Q, где Р многогранник, a Q строго выпуклое множество (может быть, М = Р);

Г

3) А мн 1 гогранник;

то для любого х £ со^Л найдется множество {и,}^ С А, что х € о a/{«t}f=i- Для случая 1) N <п + 1; для случаев 2), 3) N <п2 + 1.

Если М и А не удовлетворяет 1) - 3), то для любого х € псом А найдется множество {и;}^ С А, "то х 6 сом{«г}Цц N <п2 + 1.

Рассмотрим аппроксимации множеств в ft" и их погрешности.

Определение 4. Единичной сеткой мелкости Д с (0,1) называется такой конечный набор единичных-векторов {р,}'=1, что для любого вектора р ^ 0 найдётся подмножество индексов Ip = {jj,...,г'/J С {1,/} таких, что — Pj\ < А для всех i и j из 1Р и вектор р лежит в

конической оболочке векторов {р,},е/ , т.е. р = Е А,р,, А,- > 0.

ie/p

Напомним, что сеточным оператором С для сетки С называется оператор, действующий на положительно однородную функцию / : R" -> R по правилу

(С/)(Р) = '

+оо, fate.

Пусть М выпуклый компакт. Введем условия, которые мы будем накладывать на положительно однородную функцию /(р)

Условия на функцию /:

1) функция s(p, М) — /(р) выпукла;

2) существуют х € R" и г > 0, такие, что г|р| + (р, х) < /(р) Vp;

3) существует тсхое L > 0, что со/(р) - {р, х) < L|p| Vp.

Например, опорные функции М-выпуклых компактов с непустой внутренностью удовлетворяют условиям 1—3.

Определение 5. Невязкой выпу,лого компакта М на сетке С мы будем называть величину

i(C, М) = max(coC$(p, М) - s(p, Л/)).

W=>

Геометрический смысл невязки состоит в том, что она является расстоянием в метрике Хаусдорфа между множеством М и его многогранной аппроксимацией на сетке С вида {х : (р,, х) < s(p,, Л/), Vpj € С}.

Теорема 16. Пусть М С R" выпуклый компакт и f : R" R положительно однородная функция, удовлетворяющая условиям J—3. Тогда

cof(p)<coCf(p)<cof(p)+6(C,M)~\p\. (3)

Если функция / выпукла, то

f(p)<coCf(p)<f(p) + 6(C,M)\p\. (4)

Для положительно однородной функции введем понятие Л/-оболочки.

Определение 6. Для положительно однородной функции / : R" —> R и для выпуклого компакта М С R" М-оболочкой функции / называется функция

с°м1(р) =co(s(p,M) - co(s(p,.\f) - со/(;>))).

Заметим, что если М порождающее множество, то определение М-оболочки можно садать проще:

со л//(р) = s(p, М) ~ со (s(p, М) - со/(;;)).

Теорема 17. Пусть положительно однородная функция / : R" ч R удовлетворяет условиям 1—3 для выпуклого Компакта М — М0. Пусть компакт Mq порождающий и множество (1 -l-i(С, Мц)/г)Мц полностью выметает выпуклый компакт М\. Т 'да

,oC/(P)<coMlC/(p)<co/(j;)+5(C,A/0)-|p!. (5)

г

Если, же функция f выпукла, множество Mq порождающее и множество Afo -+■ i(C,A/o)5i(0) полностью выметает выпуклый компакт Мi, то

соCf(p) < со MlCf(P) < f(p) + <5(С, Л/о)|р|. (в)

Определение 7. Для данной сетки С и данного выпуклого компакта М оператор йд/, действующий на положительно однородную функцию f : R" -¥ R, определяется формулой

ЯиЯр) = s(p, А/) - сос(в(р, Л/) - /0»)). (7)

Теорема 18. Пусть Mq порождающее множество, f : R" R положительно однородная функция, удовлетворяющая условиям 1—S для множества М — Л/ц. Пусть задана сетка С мелкости Л € (0,1/2), такой, что <5(С, Л/и)/г < 1. Пусть множество Л /у,/ (1 - ¿(С, Л/о)/г) полностью выметают выпуклый компакт Л/j. ТогсЬ выполнены оценки

со«.м,/(р) < соf(j>) < соu,Cf(p) < со».v,/(p) +

(8)

Если / непрерывная по Липшицу с константой I положительно однородная функция, удовлетворяющая условиям 2, 3, то в силу результатов Е.С. Полоаинкина

соСУ(р)<со/(р) + —|р|. (9)

• г

Отметим, что всегда имеет место неравенство <5(С, XI) < 2/i(0, А/)Д, а в рчде случаев (например, когда множество М есть эллипсоид в R"), ¿(С, М) имеет порядок поэтому оценки теоррм 16, 17 и 18 сильнее, чем оценка для общего случая (9).

Пусть 'Н — полное гильбертово пространство.

Следуя работам Е.С. Половинкина, будем называть Вр(0)-выпуклые множества сильно выпуклыми множествами с радиусом R и />/?(()) оболочку сильно выпуклой /?-оболсчкой и обозчачать ее через strco«.

Определенно 8. Для множества А из 71 точка х е Н называется R-выстуг.ающей. если существует шар Br{z), г £ Н, такой, что А С Вц{г) и дВц{г)Г\А {х}. Множество таких точек будем обозначать через ехр ¡¡А.

Тсор< ш 19. Пусть Л С Н компакт, А С Bp(zi), р < R. Тогда А С strcojjexp пА. .

Определенно 9. Для множества А С Н тачка х ф А называется сильно крайней (с радиусам R), если дпя любых у и z из .4.- х ?= у,

х ф z х <£ strcoflfj/, г}. Обозначиг множество сильно крайних точек через extr цА.

Лемма I. Для любого множества А С H ехрцА С extr/¡А.

Теорема 20. Пусть Ас У. компакт, А С Bp(z{), р < R. Тогда

А С strcoiiextr дЛ.

Теорема 21. Пусть в пространстве НА — выпуклое замкнутое множество, содержащееся в шаре Вг(а), а€Н. Тогда для любого е > О найдется выпуклое замкнутое ограниченное множество В = strco^A, Я = max{r2/£,r}, такое, что А С В, Л(А, Л) < е-и опорная функция множества В имеет Липшицев градиент на dBi(0) с константой Липшица Л.

Следствие теоремы 21. Пусть в пространстве НАС. Вг(а) — выпуклое замкнутое множество и В > г. Тогда

г2

h(A,stTCOiiA) < —.

И.

2. Свойства сильно выпуклых множеств в R".

Лемма 2. Пусть множество А С R" сильно выпукло с радиусом R, содержится в шаре радиуса г < R, z € extr д А, В С А\{.с} и В компакт. Тогда z <р strcoцВ.

Непосредственным следствием леммы 2 является

Теорема 22. Пусть А С R" кол.пакт и для некоторого а 6 R" выполняется включение А С Br(a), г < Л. Тогда выполнено включение

extrfiA Э extrjjstrcoRA.

Теорема 23. Пусть множеЬтво А С R" сильно выпукло с радиусом R и отлично от шаре радиуса R. Тогда

extr rA = ёхр"дА.

Теорема 23 используется при исследовании многозначного отображения с сильно выпуклыми значениями.

Предположение 1. Пусть Т — полное метрическое пространство, F : Т -4 R" — непрерывное многозначное отображение с сильно выпуклыми значенняыи, функция R[t) есть минимальный радиус, с которым F(t\ сильно выпукло для t € Т. Будем также считать, что sup R(t) < со л для всех Г F(t) отлично от шара радиуса R(t).

<£Г

. Теорема 24. Пусть многозначное отображение F удовлетворяет предположению-1. Тогда многозначное отображение extr ji(i)F(t) полунепрерывно снизу.

Следствие теоремы 24. Пусть А С R" — компакт. Тогда многозначное отображение U cxXvn strco/j.4 полунепрерывно снизу.

Следующая теорема показывает, что локальное и глобилыше определение силыюй выпуклости совпадают. Скажем, что компакт А С R" является локально сильно выпуклым с радиусом R, если длп любого х 6 А найдется 6 > 0, такое, что множество Ла(а)ПЛ сильно выпукло с радиусом R.

Теорема 25. Пусть локально сильно выпуклый с радиусом R компакт А С П." является выпуклым, Тогда множество А сильно выпукло с радиусом R.

Условия компактности и выпуклости множества п теорем* 25 существенны, чго легко показать на прнмег-ix.

Напомним, что функция f[x) силыю выпукла с константой к, если функция f[x) - к|х|2 выпукла.

Теорема 20. Пусть функция f ; R" R сильно выпукла с константой сим шй выпуклости к и пусть на некотором фиксированном множестве уровня L, функция / удовлетворяем условию Липшица с константой о. Тогда множество L,: сильно выпукло с радиусом сильной выпуклости

■ (щ

Пример. Пример функции f(xitxi) ~ x}+xl показывает, что оценка теоремы 26 иеулучшаема.

Рассмотрим локальные свойства сильно выпуклых множеств.

Обозначим нормальный конус ко множеству А в точке х через N(A\ х), а конус, порожденный множеством А в точке х через Т(А; х).

Лемма 3. Пцстъ n.rj е R", ¡л, - х2| < 2R. Тогда

{• " I |2 1

V ■ {pa 1 ~ is) >

Г^ЬгсоИгьгг};*!) = |р; (р,гг ,. Xl) > ¡х, - asj||p|^ - j

Теорема 27. Пусть задан набор точек С R", причем все

точки лежат в некотором шаре радиуса II. Пусть у а нЬсо;;{;т,}[". Тогда

т

Лг(«»тсол{г,};'Л,;г/) =» П М{тхсоп{х1,уУ,у). (11)

т

Т^гсоя^,}™,;») =с.. и Т(в1гсод{ц,»};»). (12)

1=1

Лемма 3 и теорема 27 позволяют предложить конечношагоаый алгоритм сильного овыпукления конечного набора точек в IV.

3. Приложения в многозначном шшлнае.

Напомним, что функция /, действующая из множества выпуклых компактов П из Л." в К" называется селектором компактов из П, если для любого выпуклого компакта К € П /(К) € К-

Определение 10. Центром Штейнера, или штейнеровскоп точкой, называется отображение из множества выпуклых компактов из Л" в Л11: для выпуклого компакта К СИ" центр Шгцейнера определяется по формуле

/ ${р,К)р(15, где / ¿Б. (13)

' Й1 №, ОН,

Иэве гно, что це» .р Штейнера непрерывная по Липшицу функция в метрике Хауедорфа: для любых выпуклых компактов К\ и К^ выполнено неравенство

И*,) - в(К»)| < ЦпЩКиК3), Цп) = (")

Оценка (14) в общем случае неулучшаема. Кроме того, для любого выпуклого компакта К из Л" в(К) е К '

Центральным местом при исследовании свойств центра Штейнера сильно выпуклой оболочки является следующая теорема.

Теорема 28. Пусть В С Л" сильно выпуклое с радиусом Я множество, отличное от шара радиусу Н. Тогда выполнено включение

¿(В) € <ю(ехЬгцВ). (15)

Из теорем 22 и 28 получается следующая

Теорема 29. Пусть А компакт, и для некоторого а 6 Л" выполняется включение А С Вг(а), г < Я. Тогда

«(зГ.гсодА) 6 со Л. (16)

Из свойств Я-оболочки получаем, что для выпуклого компакта К, такого, что Вц(0) - К ф 0, имеет место формула

з^гсояА") = / со(Я|р| - з(р,Х))рс13. дв\

Определенно Ц, Скажем, что семейство П компактов из R" равномерно ограничено константой г, если для -,:обаго компакта К 6 П найдется геЯ", что К С Ц-М-

Поскольку операция взятия сильно выпуклой оболочки с радиусом II является липщицеиой функцией множества в метрике Хаусдорфв (ом, (1]), а центр Штейиера — липшнцеиым селоктороц выпуклых компактных множеств и метрике Хаусдорфа, то центр Штейнеро сильно выпуклой оболочки с радиусом Л от выпуклых множеств является липши« цевым селектором выпуклых равномерно ограниченных константой г (г < R) компактов в метрике Хвусдорфа. На примере показано, что в общем случае он отличен от известной штеПнеронской точки. Кроме того, приводится пример, показывающий, что для сильно выпуклых множеств с радиусом Л > 0 и Л" зависимость центра Штейнера от множествл лнпшииепа в метрике Хаусдорфа с такой же коиствнтой Лилшицп, что и в общем случае в форму.-*» (Н).

D заключение главы 3 приводятся примеры, в которых свойства сильно выпуклых множеств позволяют получить Солее сильные результаты, чем в случае выпуклых и строго выпуклых множеств.

В п< рвом П"и.мерс рассматривается нехаусдорфова метрика р не пространстве выпуклых компактов в R".

Определенно 12. Метрикойр[К\, на множестве выпуклых ком-пантов из ft" называется функция

Л-г) - sup

Интерес предстзнлпют некоторые ср.ойстнз этой метрики.

Теорема 30, Метрическое пространство выпуклых компактов из R" с метрикой р полное. Пространство строго выпуклых компактов из R" с метрикой р является метрическим подпространством.

Теорема 31- Пусть выпуклые компакты К,„ сходятся if выпуклому компакту &' в метрике Хаусдорфа. Ест К — строго выпуклый компакт, то последовательность Кт сходится it К и я метрике р.

Лемма 4. Операции суммы и геометрической разности множеств из пространства строго выпуклых компактов непрерывны в метрике Р-

Лемма б. Пусть С € R"1*" — матрица полного ранга, т < п. Тогда для любы строго выпуклых компактов К\ и Кj выполнено неравенство p{CKuQKV < \\С\\р{КиК2).

Леммы 4, 5 и теорема 30 показывают, что множество строго выпуклых компактов есть подпространство в метрическом пространстве выпуклых компактен с метрикой р, причем любая сходящаяся в метрике

р последовательность строго выпуклых компактов сходится в метрике Хаусдорфа и наоборот. Отметим, что множество строго выпуклых компактов не является метрическим подпространством пространства выпуклых компактов с метрикой Хаусдорфа.

Для сильно выпуклых множеств можно усилить оценку расстояния в метрике р через расстояние в хаусдорфовой метрике.

Лемма 6. Пусть К, и К? сильно выпуклые множества с радиусом Я > 0 и Н = Ь(К\, К-г). Тогда имеет место оценка

р(КI, К2) < у/НуЩ+К (17)

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

Опредилоние 13, Скажем, что лшогозначное отображение Р удовлетворяет услооию Гельдера с показателем а и константой Ьр в метрике Хаусдорфа, если для любых Ц и ¿2 из Т выполнено неравенство

При а = 1 многозначное отображение Г называется непрерывным по Липшицу.

Теорема 32. Пусть Р,С \ Т —у П." —многозначные отображения с выпуклыми и замкнутыми значениями. Пусть образы Г сильно выпуклы с радиусом Л и для всех I € Т //(£) = .Г(г) П С(') ф 0. Пусть, кроме того, Р и С удовлетворяют условию Гельдера с показателем а и константами Ьр и Ьд соответственно. Тогда И удовлетворяет на Т условию Гельдера с показателем а/2:

ЦН(Ь),Н(Ь)) < {ЬР + 2Хс)к ~ ыа + у/ЩЬр + Ьа)^ - <г|а/2 (18)

для всех ¿1, ¿2 6 Т.

Приводится примеры, показывающие, что результат теоремы 32 неулучшаем.

4. Максимизация выпуклых и сильно выпуклых функций.

Рассматривается задача

тах/(х), где А= {х: Ы,х) < /¿, г € Т7Щ (19)

тел

Здесь х 6 Л", / — выпуклая функция, непрерывная по Липшицу на А с кинсташоп ЛггйЕшца а. — набор единичных векторов, /, 6 Д.

Будем считать, что Л компакт. Через х обозначим некоторое решение задачи (19).

; Предположение 1. Будем считать, что набор векторов {р,},1, образует сетку С) мелкости Д1 6 (0,1). Будем также считать, что сущестиуют вектор а 6 П." и числа I > р > 0 такие, что для псех р, выполнено условие

<Р„ а) + />|р,| < 1 < ЦР.\ + (Р..в) (20)

Описание алгоритма.

0) В реальных задачах, как правило, неизвестны точка а и числа р, Ь. Поэтому возникает задача нахождения этих элементов но сеточному заданию множества .4.

Пусть Л = {г : (р,,ж) < /,}. Будем искать а € Л такое, чп ■ М это « являлось решением экстремалвноП задачи:

'ПШ_ 1а — у\ "* |,1лх • у € Н"\д " е -4

С.И. Дуловым показано, что эта задача сводится к задаче линейного программирования. Введём дополнительную переменную х € К. Пусть х € II". Тогда решение (г*, г") задачи

г -> т.гх при условии (р,, х) -/,-(- г < 0 1 < 1 < N

даёт точку (а,р) € Н."+1, т.е. а и р, причём величина р то-то верхняя грань радиусов всех шаров, вписанных в А. Это экннннлен пш тому, что полученное р является максимально возможным в условии (20). Ь определяется из условия

I = тах{/, - (р,, а)}

Если а Ф <, то заменяем) множестпо'Л на множество Л-а. а функции /(г) на /(-х 4- а). Далее, в пунктах 1) и 2) алгоритма, будем считать, что а ~ 0.

1) Введем сетку С2 = мелкости Дз 6 (0,1/2). Дли всех ^ определим

2) Для всех гц £ С2 определим

Л} - Ч]/$°(ъ)

Положим

л/

А = со у X)

>=1

Это и есть приближённый многогранник, вписанный в А. Теперь ищем х0 6 {х}}^ такой, что /(г0) = ^ах^/(ж;). Это и есть приближенное

решение задачи (19).

Теорема 33. Пусть выполнены условия предположения 1. Пусть Я — Ь/( 1 — Д?). Тогда в результате шагов 1) и 2) алгоритма мы получим множество А, для которого выполнены включения

АС Л С ВКО) ' (21)

Р

Для приближенного решения задачи справедлива оценка

+ (22)

Замечание. Условие предположения 1 о том, что мелкость сетки Gi Aj С (0,1) можно заменить на условие Л С Bl(q). Тогда описанный выше алгоритм дает ту же погрешность с R = L.

В случае, когда множество Л есть сеточное задание сильно выпуклого множества В с радиусом Но, можно уточнить оценку (21). Для этого введем дополнительное предположение о том, что нам известна предопорная функция В для всех p,-i.e. такая положительно однородная функция д{р), что сод(р) = s(p,B). В частности, g(j>i) = /,-.

Теорема 34. Пусть задана сетка С мелкости Д 6 (0; 1/2). Пусть д(р) — положительно однородная функция, непрерывная по Липшицу на R" с константой I, являющаяся предопорной для сильно выпуклого множества В с радиусом Rq. Пусть г > 0 — число, для которого выполнено условие "непустой внутренности" для д(р):

■31 6.R" г|р| + {р,Ь)< д{р) Vp 6 R\

Пусть А = {я : (jp, х) < д(р)Ур € С}. Тогда при Ci = Сг = С оценки (21) и (22) погрешности алгоритма приобретают вид

АСАСА+&А (2Яо - О (1 + Bi(0)> /Ы < № < /Ы + 8Д (2До - г) а (1 +

Если, потребовать, чтобы была выпуклой функция fio|p|—il(p)i т0 оценки (23) можно уточнить

AcAcA + 8A(2no-r)(l + iSf')'2Di(0), ^

/Ы < /(*) < /(го) + 8Д (2Ло - г) a (l + i-^)*

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

Теорема 35. Пусть f : R" Э U -4 II — сильно выпуклая функция с константой к, удовлетворяющая на U условию Липшица с константой

о. Пусть S С U компакт и М = шах fix}, L\/ — {z : f(x) < M) С U.

■'it!

Пусть П0 = а/2к. Тогда для любого Л > Я» существует уц t extr цЯ такое, что f{yn) = Л/.

Основные результаты работы.

1. Получен новый опорный принцип для порождающих множеств в рефлексивных банаховых пространствах. Доказано, что операция предельного перехода и линейный гомеоморфизм сохраняют свойство множества быть порождающим. При доказательстве этих теорем в качестве вспомогательного результата пол учены новые условия непрерывности геометрической разности многозначных отображений в банаховых пространствах и н R". Приведены примеры, когда операции умножения матрицы на порождающее множество и сумма Минковского порождающих множеств в R" не является порождающим множеством. Получены достаточные условия порождаемое™ для выпуклых компактов из R". С помошыо этого условия доказано, что псе-выпуклые ком па ■ ты и R2 порождающие. Указан способ построении порождающих мно?кеств bR".

2. Введено понятие Л/-о6олочки дли выпуклого ограниченного множества М и" рефлексивного банахова .пространства. Исследованы свойства операции впятил Л/-сСо.точки суммы и геометрической разности множеств. Показано, что операция ЛЛовыпуклсннн для порождающего множества М удовлетворяет условию Липшица в метрике Хаусдорфа.' Доказано обобщение теоремы Каратеодори на случай ^/-оболочки для порождающего множества М из R". Введены внутренние и внешние аппроксимации Л/-выпуклых компактов, получены оценки погрешности этих аппроксимаций. Покезано, что погрешность аппроксимаций меньше, чем для общего случая.

3. Доказано, что в полном гильбертовом пространстве тар является порождающим множеством. Введены понятия сильно Л-выетупаюшей

и сильно Я-крайней точек множества в гильбертовом пространстве, докапано обобщение теоремы Крсйна-Мильмана: показано, что компакт содержится в Вд(0)-оболочкс своих Я-крайних точек. Показано, что выпуклое замкнутое ограниченное множество в гильбертовом пространстве можно аппроксимировать с любой точностью в метрике Ха-усдорфи множеством, градиент опорной функции которого непрерывен по Липшицу на единичной сфере.

4. Для сильно выпуклых множеств из Л" установлена связь между Я-крайиими точками сильно выпуклой Я-оболочки компакта и самого компакта. Доказано обобщение теоремы Стражепича: показан , что замыкания множеств сильно Я-выступающих и сильно Я-крайних точек совпадаю!. Получен новый критерий сильной выпуклости множества е Ft". Для мн.-.кества, являющегося сильно выпуклой оболочкой конечного множества точек, выписаны явные формулы касательного и нормального конусов в любой точке этого множества. Предложен ко-нечношоговый алгоритм сильного овыпукления конечного набора точек.

5. Показано, что центр Штейнера сильно выпуклой оболочки (в случае, когда оболочка непуста) выпуклого компактного множества из R" является Липшицевым селектором выпуклых компактных множеств в метрике Хаусдорфа, отличным в общем случае от известного центра Штейнера. Получена формула, выражающая новый селектор через интеграл Римана от опорной функции выпуклого компакта. Получена неулучшаемая константа Липшица для зависимости центра Штейнера сильно выпуклых множеств радиуса'Я от этих множеств.

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

6. Показано, что лебеговы множества сильно выпуклой непрерывной по Липшицу функции являются сильно выпуклыми множествами в R". Доказано, что сильно выпуклая непрерывная по Липшицу функция достигает максимума на компакте из R" в Я-крайних точках выпуклого компакта, получена неулучшаемая оценка радиуса Я.

Предложен приближенный алгоритм максимизации выпуклой непрерывной по Липшицу функции на компакте, заданном системой линейных ограничений, получена оценка погрешности алгоритма.

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

Список литературы

1. Балашов М.В., Половинкин Е.С. Сильно выпуклая оболочка и её свойства. // Некоторые'проблемы современной математики и их приложения к задачам ^физики И механики./ Междувед. сборник.— М: Изд. Mocfi. физ.-техн.Инст., 1995, С.27-36. <"•

2. Балашов М.В. Центр-Штейнера сильно выпуклой оболочки. // Некоторые проблемы фундаментальной и прикладной математики. /Междувед. сборник. / — М.: Изд. Моск. физ.-техн. инст./ 1996, С. 35—45.

3. Балашов М.В., Иванов Г.Е. Сильная выпуклость множеств уровня ' сильно выпуклой функции. // Некоторые проблемы фундаментальной

и прикладной математики. /Междувед. сборник. / — М.: Изд. Моск. физ.-техн. инст / 1996, С. 46—53.

4. Балашов М.В. О максимизации выпуклой функции на компакте. // Некоторые проблемы фундаментальной и прикладной математики. /Междувед. сборник. / — М.: Изд. Моск. физ.-техн. инст./ 1997, С. 17—25.

5. Балашов М.В. Свойства сильно крайних точек сильно выпуклых лщо-жеств. // Некоторые проблемы фуйдаментальной й прикладной математики. /Междувед. сборник. / — М.: Изд. Моск. физ.-техн. инст./ 1997, С. 26—36.

МФТИ заказ // '/л? ТИР.50экь. .