Метрическая проекция и функции расстояния и антирасстояния для сильно выпуклых множеств тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Голубев, Максим Олегович

• Голубев, Максим Олегович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Голубев, Максим Олегович

Оглавление

Введение

1 Свойства оператора метрического проектирования на

сильно выпуклые множества

1.1 Предварительные сведения

1.2 Связь константы Липшица метрической проекции на сильно выпуклое множество с радиусом сильной выпуклости

1.3 Связь сильной выпуклости множества с сильной выпуклостью функции расстояния и слабой вогнутостью функции антирасстояния

2 Приложение результатов главы 1 в задачах оптимизации и аппроксимации

2.1 Предварительные сведения

2.2 Метод проекции градиента для выпуклой функции и сильно выпуклого множества

2.3 Метод проекции градиента для сильно выпуклой функции и сильно выпуклого множества

2.4 Оценка константы Липшица метрической проекции на внешнюю многогранную аппроксимацию сильно выпуклого с радиусом В, множества в!"

Заключение Список литературы

Введение диссертации (часть автореферата) на тему «Метрическая проекция и функции расстояния и антирасстояния для сильно выпуклых множеств»

Введение

Темой представленной диссертации является изучение аппроксимативных свойств выпуклых множеств в гильбертовом пространстве. Диссертация состоит из введения, двух глав, заключения и списка литературы. В первой главе рассматриваются свойства оператора метрического проектирования на сильно выпуклое множество с радиусом Я > 0 в гильбертовом пространстве. Под сильно выпуклым множеством с радиусом Я подразумевается множество, которое может быть представлено в виде некоторого пересечения замкнутых шаров одного и того же радиуса Я > 0. Также в первой главе рассмотрены некоторые свойства функции антирасстояния до выпуклого замкнутого ограниченного множества в гильбертовом пространстве. Вторая глава посвящена приложениям результатов первой главы в задачах оптимизации и аппроксимации. Исследованы различные варианты алгоритма метода проекции градиента для выпуклой функции (в общем случае, не обязательно сильно выпуклой) и сильно выпуклого множества. Получены оценки сходимости этого алгоритма со скоростью геометрической прогрессии. Рассмотрены свойства внешних многогранных аппроксимаций сильно выпуклых множеств вГ.

Оператор метрического проектирования является классическим объектом исследования специалистами по теории функций и оптимизации. Поскольку значительная доля задач оптимизации рассматри-

вается и решается в гильбертовом пространстве, то для приложений важны свойства оператора метрического проектирования именно в гильбертовом пространстве. Классический результат состоит в том, что оператор метрического проектирования на выпуклое замкнутое множество в гильбертовом пространстве удовлетворяет условию Липшица с константой равной 1 по точке (в бесконечномерном гильбертовом пространстве результат, вероятно, впервые широко опубликован в работе [69], в конечномерном пространстве - известен много раньше). При этом, как следует из результатов Й. Линденштраусса [66], равномерная непрерывность оператора метрического проектирования в банаховом пространстве характеризует это пространство: в нем существует эквивалентная гильбертовой норма. Как доказал Дж. Даниэль [57], при фиксированной точке проектирования оператор является гёльдеровым по множеству с показателем \ в метрике Хаусдорфа. Указанные свойства и, в первую очередь условие Липшица с константой 1, являются важными во многих теоретических и прикладных вопросах. Однако во многих задачах условия Липшица с константой 1 недостаточно - нужна сжимаемость оператора метрического проектирования. Например в различных проекционных алгоритмах (в частности, в методе проекции градиента при отсутствии условия сильной выпуклости целевой функции хороших оценок для скорости сходимости обычно не получается [11, 12, 30, 34, 40]). Очевидно, что сжимаемость возможна лишь при условии, что точка проектирования достаточно удалена от множества, а также при некоторых ограничениях на геометрические свойства самого множества. Исследованием оператора проектирования занимались многие специалисты: Н. В. Ефимов [20, 21, 22], С. Б. Стечкин [20, 21, 22, 39], В. Кли [65], Д. Вулберт [74] (рассматривали оператор метрического проектирования на чебышевские множества в банаховых пространствах), Ф. Кларк [25, 56], Р. Штерн [56], П. Воленски [56] (иссле-

довали оператор метрического проектирования на слабо выпуклые множества в гильбертовом пространстве), Л. Тибо [53], Дж. Вулф [73], Т. Абацоглу [43, 44] (исследовал оператор метрического проектирования на множества с С2 -гладкой границей), М. Эделстейн [59], Ю. Г. Решетняк [37] (рассматривал слабо выпуклые множества), С. Фицпатрик [55, 60] (получил достаточные условия непрерывности оператора метрической проекции на замкнутые множества в банаховых пространствах с дифференцируемой по Фреше нормой), И. Г. Царьков [41], В. И. Бердышев [6, 7, 8, 9, 10] (получил классические результаты устойчивости для оператора метрического проектирования в различных подклассах банаховых пространств) и его школа (А. В. Маринов ([29]) и др. (ИММ УрО РАН)) (см. также [26, 27, 28, 30, 31, 36, 38, 42, 47, 54, 57, 68, 69, 70]). В некотором смысле окончательные результаты в гильбертовом пространстве для аппроксимативных компактов с С2 -гладкой границей (то есть граница множества является многообразием, которое в окрестности граничной точки т представляется таким отображением /, что выполнены следующие условия: (1) / - открытое отображение на своей области определения, то есть некотором открытом множестве в Мп, (2) / - С2, (3) ¡'{а) -Кп = Мп, где а = /(т)) были получены в работах Т. Абацоглу [43, 44]. При условии, что граница множества С2 -гладкая, Т. Абацоглу предложил обобщение понятия радиуса кривизны множества и при определенных условиях получил точную оценку константы Липшица меньше 1. При этом для множеств с негладкой границей точных результатов получено не было, кроме того, было не ясно на какой класс множеств не с С2 -гладкой границей могут быть обобщены результаты, полученные для множеств с С2 -гладкой границей.

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

симацию, с которой часто приходится иметь дело в приложениях.

Метрическая проекция на множество тесно связана со свойствами функции расстояния от точки до множества. Здесь классическим является результат о том, что выпуклость замкнутого множества эквивалентна выпуклости функции расстояния (см. например [25]). Исследованию функции расстояния посвящено огромное число работ (см. например [6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 25, 28, 29, 31, 33, 36, 38, 42, 46, 47, 48, 54, 57, 60, 61, 62, 69, 71, 75]).

Гораздо в меньшей степени известна и популярна функция, которую мы называем функцией антирасстояния. Для замкнутого ограниченного множества в банаховом пространстве функция антирасстояния - это супремум расстояния от заданной точки до точек из множества (см. [4, 23, 42, 45, 55, 58, 60, 75]). В отличие от функции расстояния, которая может не быть выпуклой, функция антирасстояния всегда выпукла. Конструкция аналогичная функции антирасстояния появляется в работе Мазура [67] и в цикле работ посвященных свойству пересечения Мазура [63, 64, 67]. Важный результат был получен Эделстейном [58], который доказал некоторые "антиаппроксимативные "свойства для множеств в гильбертовом пространстве. Существенным продвижением в исследовании функции антирасстояния и единственности и непрерывности антипроекции (точки множества, на которой реализуется функция антирасстояния) содержатся в работе М. В. Балашова и Г. Е. Иванова [4] и работе Г. Е. Иванова [23]. Из результатов работы [4] следует, что в гильбертовом пространстве совокупность условий существования, единственности и липшицевой зависимости от х метрической антипроекции х на множество А для точек х, достаточно удаленных от множества А, эквивалентна сильной выпуклости множества А.

Одно из важных приложений оператора метрического проектирования в оптимизации - это построение проекционных алгорит-

мов для решения некоторого класса экстремальных задач. В первую очередь речь идет о поиске минимума выпуклой функции на выпуклом множестве. Одним из классических алгоритмов здесь является метод проеции градиента (метод детально изложен в работах [11, 12, 30, 34, 40]). Последовательность генерируется по правилу

хк+1 = Рл{хк - ак/'(хк)), хг в Ьс1 А, ак > 0,

где через Ьс1 А будем обозначать границу множества А. При этом (см. [11, 12, 30, 34, 40]) для выпуклого множества и сильно выпуклой функции при условии липшицевой дифференцируемости при определенном выборе параметра шага ак доказывается сходимость данного метода к единственному решению со скоростью геометрической проекции. Однако при отсутствии условия сильной выпуклости функции хороших оценок для скорости сходимости обычно не получается.

В первой главе предлагаемой диссертационной работы рассматривается вопрос о свойствах оператора метрического проектирования в гильбертовом пространстве на класс сильно выпуклых множеств. Как было показано М. В. Балашовым (предложение 1.2.1) если для точек удаленных от выпуклого замкнутого множества на расстояние больше, чем д > 0, оператор метрического проектирования удовлетворяет условию Липшица с константой С < 1, то множество является сильно выпуклым с радиусом Заметим, что выпуклые множества с С2 -гладкой границей, рассмотренные Т. Абацоглу, попадают в этот класс. В данной главе получена неулучшаемая оценка для модуля равномерной непрерывности (теорема 1.2.1), а именно:

Теорема 1.2.1 Пусть множество А С Н является сильно выпуклым множеством с радиусом Я. Тогда для любых точек

е Н\Л выполнено неравенство

' у/\\хо -Х\\\2 - (бо - 01)

2

где {а*} = Ра{х{),91 = ||ж» - сц||,г € {0,1}.

Из результата данной теоремы и теоремы М. В. Балашова (предложение 1.2.1) следует критерий сильной выпуклости замкнутого множества в гильбертовом пространстве (следствие 1.2.1): замкнутое множество в гильбертовом пространстве является сильно выпуклым с радиусом Я тогда и только тогда, когда для точек из дополнения к открытой д > 0 окрестности данного множества оператор метрического проектирования удовлетворяет условию Липшица с константой я

Нередка ситуация, когда часть границы множества устроена как часть границы некоторого сильно выпуклого множества, а само множество при этом не является сильно выпуклым и может быть даже неограниченным, например, надграфик функции /: М —» К.

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

Определение 1.2.1 Пусть Е банахово пространство. А С Е замкнутое выпуклое множество. Модулем выпуклости называется

я+в'

<Х 2 ' Х — Т

функция 6а [0, сИатА) —> [О, +оо) определяемая формулой 6А[Ь) = вир > 0 | В6 + с А,Ухо,яя € А : ||ж0 - хх\\ =

Отметим, что преимуществом модуля выпуклости по сравнению с радиусом кривизны границы множества является то, что от границы не требуют гладкости, а понятие модуля выпуклости достаточно хорошо изучено и показало свою эффективность в теории приближений и функциональном анализе (см. [2, 3, 49, 50, 51, 52]). На основе определения модуля сильной выпуклости доказан локальный вариант теоремы 1.2.1 и результата М. В. Балашова (предложение 1.2.1). Определим множество

Ф = Ф(А,5,Й= + ) \иА(д),

ХхеБ )

где ил(д) = {х £ Н : т£ ||х — а|| < £>} - шаровая д -окрестность

аеА

множества А, а N (А; х) - нормальный конус ко множеству А в точке х.

Теорема 1.2.2 Пусть А С Н замкнутое выпуклое множество, Б С Ьс1 А и для любой точки а € 5 найдется число и (а) > 0, такое что множество В = (а) Р| А равномерно выпукло с модулем выпуклости 8в(£) > где С > 0, р > 2. Пусть д > 0, а множество Ф определено выше.

Тогда Уе > 0 Уха е Ф 36 = 6(е, ха) > 0 Ухь е Ф : \\ха - хь\\ < 5, [ха,хь] 6 Ф, выполнена оценка

II®. - Zi.ll2 > 11« - Ъ\\2 + (з-^Ь - е) На - 61Р+

, ( 16СУ \и ,||2р-2

где {а} = Рл(ха), {Ь} = РА{хъ)

Отметим, что теорема 1.2.2 является в некотором смысле локальным аналогом теоремы 1.2.1. При р = 2 на константу Липшица метрической проекции получена оценка аналогичная оценке в пункте 2 следствия 1.2.1

Следствие 1.2.2 Пусть выполнены условия теоремы 1.2.2, р = 2. Тогда для любых точек хо, х\ Е Ф таких, что [жо,^] С Ф выполнено неравенство

IIао ~ ахИ < 1+\Сд\\х° ~ ^И'

где {аг} = Ра (ж»), г 6 {0,1}.

Теорема 1.2.3 Пусть Лс1 выпуклое замкнутое множество. Пусть в С Ьс1 А, множество Ф определено выше. Предположим, что существует число С Е (0; 1), такое что для любых Х0,Х\ Е Ф верна следующая формула:

||«о — «1|| < СЦто-ЯхН, {а{} = РА{х{), г€{0,1}.

Пусть а£ в и Я =

Тогда для всех £ Е (0, Я) со свойством Д-(а)Р)Ьс1 А С в множество А р)Ре(а) является сильно выпуклым с радиусом Я.

Теорема 1.2.3 обобщает предложение 1.2.1 на более широкий класс множеств. Отметим, что свести доказательство теоремы 1.2.3 к идее доказательства предложения 1.2.1 не удалось. В пункте 1.3 немного уточняется результат А. С. Дудовой (см. [18, Теорема 4.9]), а именно: если множество А является сильно выпуклым с радиусом Я > 0, то для любого числа Л Е [0,1] и для любой пары точек хо, х\ равноудаленных от множества на расстояние д > 0 и таких, что отрезок [жо, £1] не имеет со множеством общих точек, выполнено

неравенство

дА(( 1 - Л)ж0 + Xxi) < (1 - X)qa(xq) + \QA(XI)-

Определение 1.2.1 [4] Пусть А С И выпуклое замкнутое ограниченное множество. Тогда функция /д: Н —> [0, +оо),

/д(х) = sup ||гс - а\\

а&А

называется антирасстоянием от точки х до множества А.

Теорема 1.3.3 Пусть Ас Н сильно выпуклое мнооюество с радиусом R. Пусть г > R. Тогда функция антирасстояния fA(x) слабо вогнута на множестве (Н \ Д.(0)) + А с константой С —

г—Я'

Вместе с результатом М. В. Балашова (предложение 1.3.3) о том, что замкнутое выпуклое ограниченное множество в гильбертовом пространстве, функция антирасстояния на которое слабо вогнута на некотором открытом множестве, является сильно выпуклым, это дает критерий слабой вогнутости функции антирасстояния для сильно выпуклого множества и дает связь С = где С - константа слабой вогнутости, Я - радиус сильной выпуклости множества, г -параметр характеризующий открытое множество, на котором слабо вогнута функция антирасстояния. В указанном результате особенно важна неулучшаемая связь между константами в том смысле, что если Д - наименьший радиус сильной выпуклости множества А, то С -наименьшая константа слабой вогнутости функции антирасстояния /а, и наоборот, если С - наименьшая константа слабой вогнутости функции антирасстояния /д, то Л - наименьший радиус сильной выпуклости множества А.

Во 2 главе работы рассмотрен классический метод проекции градиента с отсутствием сильной выпуклости функции, но с сильно выпуклым множеством. Также, если функция является сильно выпуклой, то сильная выпуклость множества обеспечивает (при прочих равных условиях) более высокую скорость сходимости. Определим следующие условия:

(1) Множество А С Н сильно выпукло с радиусом Я,

(2) Функция /: Н —> R является выпуклой, дифференцируемой и

градиент f{x) удовлетворяет условию Липшица с константой М> О,

(3) Для всех к € N существует вектор п(хк) € N(A\xk), такой что

выполняется неравенство (п(хк), f'{%k)) < О,

(4) Решение х* € bd А задачи min f(x) единственно,

хеА

(5) t= min \\f'(x)\\ > 0.

a;ebd А

Теорема 2.2.1 1. Пусть выполнены условия (1)-(5). Пусть

ак = ае (0, -§р].

Тогда последовательность хк, генерируемая по правилу хк+\ =

Ра(хь — &кГ{хк)), £ bd А, сходится к решению задачи min f(x)

хеА

со скоростью геометрической прогрессии: \\xk+i — х*\\ < q\\xk — где о = — — •

4 l/(R2+a42)(R+at)* >

2. Пусть выполнены условия (1)-(4)• Пусть ак = ос £ (0, . Тогда последовательность хк, генерируемая по правилу xk+i — РА{хк — ®kf(xk)), £ bd А, сходится к решению задачи min f(x)

х^А.

и верна формула: \\xk+i-х*\\ < qk\\xk-x*\\, где qk = удг+^щ^р •

Теорема 2.2.2 Пусть выполнены условия (1)-(2). Пусть <

1, где t = min И/'Ос)!! > 0. Последовательность Хк генерируется x^bd А

по правилу Xk+i = Рл(%к — oikff(xk)), £ bd А с а^ = а > 0 для всех к. Тогда:

1) при выборе а £ последовательность Хк сходится к решению задачи min f(x) со скоростью геометрической прогрессии:

lkfc+1 - я*|| < я\W - Ж*II, где q = ^д/

2) при выборе а > ^ последовательность Хк сходится к решению задачи min f(x) со скоростью геометрической прогрессии:

хеА

\\xk+i - х*\\ < q\\xk - х*\\, где q = •

Теорема 2.3.1 1. Пусть выполнены условия (1)-(5). Более того, пусть функция f является сильно выпуклой с константой 7 > 0. Пусть ак = а£ (0, jfe), М > 7.

Тогда последовательность Хк, генерируемая по правилу Xk+i — Рл(хк — ®kf'{%k)), £ bd А, сходится к решению задачи min f(x)

xۀ

со скоростью геометрической прогрессии: \\хк+\ — ж*|| < q\\xk — х*\\, где q = R Jl- 2а<у + а2М2;

2. Пусть выполнены условия (1)-(4) раздела 2.3. Пусть с*к =

Тогда последовательность генерируемая по правилу Xk+i = Рл(%к — &kf(%k))i £ bd А, сходится к решению задачи min f(x)

х£А

и верна формула: \\xk+i — ж*|| < qk\\xk ~ где

К = </я^Л'ЫII2 V1 ~ + а"м2-

Завершает работу короткий раздел об операторе метрической проекции на внешнюю многогранную аппроксимацию сильно выпуклого множества. Напомним следующее определение.

Определение 2.4.1 [33, Определение 2.6.1], [50] Сеткой (Б мел-

кости А £ (0, называется такой конечный набор единичных векторов Р1 £ Кп, г £ 1, /, что для любого вектора р ^ 0, р £ Мп такого, что и^ц- ^ С, существует подмножество индексов 1р С 1,1 и числа аг- > 0, г £ 1р, такие, что

\fijeip, рир^е^,

Теорема 2.4.1 Пусть задана сетка С мелкости А € (0, Пусть множество А С является сильно выпуклым множеством с радиусом Я > 0. Множество А определено формулой

I

А = (~){хетп:{р1,х)<з(рг,А)},

г=1

где I £ Щ, а векторы рг £ С. Пусть заданы числа I > 0, д > 0. Множество ил(д) является д-окрестностью множества А. Пусть хо,х\ 6 Г\ ил(б), — > I- Определим множество В = со {А и {^0,^1}} и точки {а^} — Р^{хг), г £ {0,1}. Тогда верно следующее неравенство:

||ао - о!|| < |4 (>/211 • сНатБ А + ДА2) у + д^} ~

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

Автор благодарен д.ф.-м.н., профессору Г. Е. Иванову за обсуждение результатов работы.

Автор благодарен д.ф.-м.н., профессору, заведующему кафедрой высшей математики МФТИ Е. С. Половинкину за полезные замеча-

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

Глава 1

Свойства оператора метрического проектирования на сильно выпуклые множества

1.1 Предварительные сведения

Всюду ниже (если не указанно иное) мы работаем с гильбертовым пространством над вещественным полем скаляров, которое будем обозначать EL Символом R будем обозначать вещественную прямую, через R будем обозначать вещественную прямую, пополненную плюс бесконечностью, то есть R = R|J{+oo}. Через {р, х) будем обозначать скалярное произведение векторов р,х £ EL Для множества А с Н через bd А, int А и cl А будем обозначать грани-

цу, внутренность и замыкание данного множества соответственно. Замкнутый шар радиуса R > 0 с центром в точке х £ Ш будем обозначать через Вц(х) = {у £ И : \\у — х\\ < R}. Диаметр множества А определяется следующим образом diam А = sup — у\\.

х,уеА

Опорная функция ко множеству А определяется следующей формулой s(p,A) = sup(р,х), Ур £ EL Нормальным конусом к выпукло-

х еА

му замкнутому множеству А в точке а £ А называется множество N(A\a) = {р £ Н : {р, а) > s(p, Л)}. Напомним, что для множества А выпуклой оболочкой множества со А называется пересечение всех выпуклых множеств, содержащих А.

Определение 1.1.1 Пусть множество Лей. Расстоянием от точки х £ И до множества А называется функция

дА(х) = inf \\х - а\\. аеА

Метрической проекцией точки х £ Н на множество А С Н называется множество Ра{х) = {а £ А : ||ж — а|| = Для множества AgI определим открытую ¿»-окрестность множества А следующим образом Ua(q) — {х £ EI: Qa{x) < q}.

Сумму и разность по Минковскому двух множеств А, В С Е определим следующим образом:

А + В= \J(A + b), А*-В = (\{А-Ъ) = {х еШ: х + В С А}.

ъ&в

Эффективное множество функции /: И —> М будем обозначать dorn/ = {х £ Н : f{x) < +00}. Напомним, что функция /: Ы —>• R называется собственной, если dorn/ Ф 0. Надграфик функции /: Н —> R определяется следующим образом epi / = {(ж, /л) G IxR : х £ dorn /, f(x) < ß}.

Определение 1.1.2 [33, Определение 1.16.1] Вектор р € Н называется субградиентом собственной выпуклой функции /:1->Кв точке хо, если справедливо неравенство /(х) — /(хо) > (р, х — жо), для всех х € Н.

Определение 1.1.3 [33, Определение 1.16.2] Субдифференциалом собственной выпуклой функции /: Н —> К в точке хо называется множество (обозначаемое д/(хо)), состоящее из всех субградиентов функции / в точке хо, то есть

¿>/Ы = {р£ И : /(х) - Д.х0) >(р,х-х0,)Ухе И}.

Определение 1.1.4 [33, Определение 1.11.1] Преобразованием Лежандра-Юнга-Фенхеля собственной функции /: Н —» М или сопряженной с / функцией называется функция /*: Н —»• М, определяемая равенством

Г{р) = вир((р,ж) - /(ж))

хеН

Для точек Хо,Хх бНи числа Л € [0,1] введем следующие обозначения

хх = (1 - Л)гг0 + \хъ [а;0, хх] = {х\ : Л € [0,1]}.

Определение 1.1.5 [33, Определение 4.3.1] Непустое множество А с Н называется сильно выпуклым множеством с радиусом Я, если оно может быть представлено в виде пересечения замкнутых шаров радиуса Я > 0, то есть А = р) В^х) для некоторого множе-

хех

ства X С И.

Стоит отметить, что если множество А является сильно выпуклым с радиусом Я, то оно является сильно выпуклым с радиусом г,

для всех г > R. В дальнейшем, говоря о сильной выпуклости множества, мы будем иметь в виду (если не сказано иное) наименьший радиус сильной выпуклости.

Определение 1.1.6 [81] Пусть Е банахово пространство. Будем говорить, что выпуклое замкнутое множество А С Е является слагаемым шара Br(0) С Е радиуса R > 0 если существует такое выпуклое замкнутое множество В С Е, что А + В = Br{0).

Определение 1.1.7 [33, Определение 4.1.1] Выпуклое замкнутое множество М в банаховом пространстве Е называется порождающим множеством, если для любого множества X такого, что множество

A=f)(M + x) (1.1.1)

хеХ

непусто, найдется выпуклое замкнутое множество В С Е такое, что

А-\- В = М.

Определение 1.1.8 [33, Определение 4.1.2] Для выбранного порождающего множества М всякое непустое множество вида (1.1.1) называется М-сильно выпуклым множеством.

Определение 1.1.9 [4] Пусть А с Н выпуклое замкнутое ограниченное множество. Тогда функция /д: Н —> [0, +оо),

fA(x) = sup ||ж - а||

а€А

называется антирасстоянием от точки х до множества А.

Заметим, что функция антирасстояния /д (ж) выпукла на Н как супремум выпуклых функций.

Определение 1.1.10 [4] Для множества А С Н и точки х £ Н определим антипроекцию следующим образом

АРах = {аеА : ||х - а\\ = fA(x)}.

Определение 1.1.11 [4] Пусть А С Н выпуклое замкнутое ограниченное множество, г > 0. Тогда множество

ТА(г) = {х е И : fA(x) > г}

называется антиокрестностью радиуса г множества А.

Определение 1.1.12 [24, Определение 2.1.2] Пусть U С Н выпуклое множество. Функция f:U —> М называется сильно выпуклой с константой С > 0 на множестве С/, если функция f(x) — выпукла на U.

Сильную выпуклость функции можно определять и иначе

Определение 1.1.13 [33, Определение 1.19.2] Собственная функция /: Н —> R называется сильно выпуклой с константой сильной выпуклости С > 0, если для любых xq,xi G dorn/ и для любого Л £ (0,1) справедливо неравенство

ДяЛ) < (1 - А)/Ы + A/On) - |Л(1 - Л)||аг0 - *i||2. (1.1.2)

Эквивалентность этих определений показана, например, в работе [24, Лемма 2.1.2]. В дальнейшем мы будем пользоваться как определением 1.1.12, так и неравенством (1.1.2).

Определение 1.1.14 [24, Определение 2.1.2] Пусть U С Н выпуклое множество. Функция /: С/ —> М называется слабо вогнутой с константой С > 0 на множестве U, если функция f(x) — вогнута на U.

Например, в работе [24, Лемма 2.1.2] показано, что условие вогнутости в определении 1.1.14 эквивалентно следующему условию: для любой пары точек хо,х\ Е II, таких что [жсьяп.] С С/, и для любого числа Л Е [0,1], имеем

/Ы > (1 - А)/Ы + А/Оп) - |А(1 - А)||*0 - Х1\\2. (1.1.3)

В дальнейшем мы будем пользоваться как определением 1.1.14, так и неравенством (1.1.3). Также заметим, что если функция / является слабо вогнутой на множестве II с константой С, то она является слабо вогнутой с константой 7, для всех 7 > С.

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

Предложение 1.1.1 (Опорный принцип) [33] Замкнутое выпуклое множество А С Н является сильно выпуклым множеством с радиусом Я тогда и только тогда, когда оно представимо в виде

А = р) Вц(хр — Яр), где для любого вектора р Е И, ||р|| = 1

1ИИ

точка хр Е А однозначно определена из равенства (р,хр) = в(р, А).

1.2 Связь константы Липшица метрической проекции на сильно выпуклое множество с радиусом сильной выпуклости

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

ми функций расстояния и антирасстояния до некоторого множества с характеристиками этого множества.

Хорошо известно, что для выпуклого и замкнутого множества А с Н множество Ра(х) одноточечно, т.е. Ра(х) = и для

любых точек хц,х\ € Н выполняется оценка ||а(хо) — a(a;i)|| < 1 • Цяго — где {aj = Ра(х(),1 G {0,1} (см. например [69]). В общем случае, (речь идет исключительно о выпуклых множествах) 1 - наилучшая возможная константа Липшица. Достигается она в случае, когда граница выпуклого множества содержит нетривиальный отрезок.

Рассмотрим пример, когда константа Липшица 1 может быть уменьшена. Рассмотрим шар А — Вл(а), где a £ Ни пару точек XQ,Xi G И, таких что 0а(х{) = Qi > 0, {аг} = PaXi, i £ {0,1}. Заметим, что точки а, хо, х\, ао, а\ лежат в одной плоскости. По теореме косинусов из треугольника xoaxi имеем:

\\xQ - a||2 + ||a?i -a||2- \\х0 - хг\\2 cos Zxoaxi =-LiTTT1—LJ-ггп-п-•

2||ж0 ~ fllllFi ~ a||

По теореме косинусов из треугольника aoaai имеем:

||«о - a||2 + ||ai ~ а\\2 ~ |К - «i"2

соэ/^о ах\— .. . .

2||а0 -а||||а1 ~ а\

Отметим, что ||ао — а|| = Цах — а|| = Д, Ц^о — а|| = Я д0, Ця^ — а|| = Я + д\. Таким образом, получаем следующее равенство:

(Д + бо? + (Д + 91)2 - \\хо - II2 = Я2 + Я2 - ||ар - а!II2 2(Д + 0О)(Д + £?1) 2Я2

Я2(2Я2 + 2Я(д0 + 01) + & + ||я;о - ая||2) =

= (Я2 + (д0 + дг)Я + еоп) (2Д2 + ||а0 - сц\\2). 23

^/\\Xo-Xl\\2-(ßQ-Ql)2. (1.2.1)

Покажем, что подкоренное выражение неотрицательно, то есть \\xo—%i\\2—{qq—Qi)2 > 0. При доказательстве мы будем пользоваться неравенством треугольника и тем фактом, что проекция точки х на множество А есть наилучшая аппроксимация точки х элементами множества, то есть в данном случае Цжх —ai|| < \\х\ — ао||, ||жо_ао|| < ||яг0 ~ai\\.

||ж0 -xi\\ = Ц(а?! - о0) - (х0 - а0)|| >

> \\%i ~ ао|| - Iko - aoll >

> ||a;i - ai|| - ||жо - ао|| = ßi ~ Qo-

Таким образом, мы показали, что ||ж0 — :ei||2 > (до — gi)2. Возвращаясь к равенству (1.2.1) заметим, что если существует число д > 0, такое что до > д и д\ > д, то верно следующее неравенство:

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

Список литературы диссертационного исследования кандидат наук Голубев, Максим Олегович, 2014 год

Литература

[1] М. В. Балашов. О непрерывности пересечения многозначных отображений с сильно выпуклыми значениями // Электронный журнал "Исследовано в России". 2002. С. 534-539. zhurnal.ape.relarn.ru/articles/2002/049.pdf

[2] М. В. Балашов. О модулях выпуклости функции и множества // Труды МФТИ. 2011. Т. 3, №1. С. 10-13.

[3] М. В. Балашов. О множествах с положительным модулем выпуклости // Современные проблемы фундаметальной и прикладной математики: Сборник научных трудов / Моск. физ.-тех. инст. - М., 2009. - С. 8-28.

[4] М. В. Балашов, Г. Е. Иванов. Об удаленных точках множеств // Матем. заметки. 2006. Т. 80, №2. С. 163-170.

[5] М. В. Балашов, Е. С. Половинкин. М-сильно выпуклые подмножества и их порождающие множества // Матем. сборник. 2000. Т. 191, №1 С. 27-64.

[6] В. И. Бердышев. Непрерывность многозначного отображения, связанного с задачей минимизации функционала // Изв. АН СССР. Сер. матем. 1980. Т. 44, В. 3. С. 483-509.

В. И. Бердышев. Эквивалентность равномерной непрерывности метрической проекции и ¿'-проекции // Матем. заметки. 1980. Т. 28, В. 4. С. 571-582.

В. И. Бердышев. О модуле непрерывности оператора наилучшего приближения // Матем. заметки. 1974. Т. 15, В. 5. С. 797-808.

В. И. Бердышев. Пространства с равномерно непрерывной метрической проекцией // Матем. заметки. 1975. Т. 17, В. 1. С. 3-12.

B. И. Бердышев. Непрерывная зависимость элемента, реализующего минимум выпуклого функционала, от множества допустимых элементов // Матем. заметки. 1976. Т. 19, В. 4. С. 501-512.

Ф. П. Васильев. Численные методы решения экстремальных задач. — М.: Наука, 1980. — 520с.

Ф. П. Васильев. Методы оптимизации. М.: Факториал Пресс, 2002.

C. И. Дудов. Дифференцируемость по направлениям функции расстояния // Матем. сб., 186:3 (1995) С. 29-52.

С. И. Дудов. Субдифференцируемость и супердифференцире-умость функции расстояния // Матем. заметки, 61:4 (1997) С. 530-542.

С. И. Дудов. Формула субдифференциала Пено функции расстояния // Вестник МГУ, сер. 15, Вычисл. матем. и киберн. 1997, №3, С. 46-47.

С. И. Дудов. Выпуклые и вогнутые аппроксимации функции расстояния // Кибернетика и системный анализ. 1998, №3, С. 104-116.

[17] С. И. Дудов. Об обобщенном градиенте функции расстояния // Итоги науки и техники. Совр. мат-ка и ее прилож. Тем. обзоры. Т. 61. 1999. Тр. межд. конф., посвящ. 90-летию со дня рождения JI. С. Понтрягина. Т. 2. Негладки анализ и оптимизация, С. 514.

[18] А. С. Дудова. Характеризация устойчивости решения задач о внешней равномерной оценке выпуклого компакта шаром. Диссертация на соискание ученой степени кандидата физико-математических наук. Саратов. 2006.

[19] А. С. Дудова. Об устойчивости решения задачи наилучшего приближения выпуклого компакта шаром // Изв. вузов. Матем., 2006, № 7, С. 25-33.

[20] Н. В. Ефимов, С. Б. Стечкин. Некоторые свойства чебышевских множеств // Докл. АН СССР. 1958. Т. 118, №1. С. 17-59.

[21] Н. В. Ефимов, С. Б. Стечкин. Чебышевские множества в банаховых пространствах // Докл. АН СССР. 1958. Т. 121, №4. С. 582-585.

[22] Н. В. Ефимов, С. Б. Стечкин. Опорные свойства множеств в банаховых пространствах и чебышевские множества, ДАН СССР, 127:2 (1959), С. 254-257.

[23] Г. Е. Иванов. Наиболее удаленные точки и сильная выпуклость множеств // Матем. заметки. 2010. Т. 87, №3. С. 355-366.

[24] Г. Е. Иванов. Слабо выпуклые множества и функции. — М.:Физматлит, 2006. — 352 с.

[25] Ф. Кларк. Оптимизация и негладкий анализ. М.: Наука, 1988.

[27

[28

[29

[30

[31

[32

[33

[34 [35

С. В. Конягин. Аппроксимативные свойства произвольных множеств в банаховых пространствах. Докл. АН СССР 239:2. (1978). 261-264.

C.B. Конягин. О множествах точек непустоты и непрерывности метрической проекции. Матем. заметки, 33:5 (1983), 641-655.

Г. Г. Магарил -Ильяев, В. М. Тихомиров. Выпуклый анализ и приложения, М.: 2000.

А. В. Маринов. Константы Липшица оператора метрического ^-проектирования в пространствах с заданными модулями выпуклости и гладкости // Изв. РАН. Сер. матем. 1998. Т. 62. В. 2. С. 103-130.

Ю. Е. Нестеров. Введение в выпуклую оптимизацию. — М.:МЦНМО, 2010. - 279с.

Ж. -П. Обэн, И. Экланд. Прикладной нелинейный анализ. — М.: Мир. 1984.

Е. С. Половинкин. Сильно выпуклый анализ // Матем. сб. — 1996. - Т. 187. № 2. С. 103-130.

Е. С. Половинкин, М. В. Балашов. Элементы выпуклого и сильно выпуклого анализа. — М.:Физматлит, 2007. — 440с.

Б. Т. Поляк. Введение в оптимизацию. — М.:Наука, 1983. — 384с.

Б. Т. Поляк. Теоремы существования и сходимость минимизирующих последовательностей в задачах на экстремум при наличии ограничений // ДАН СССР. - 1966. - Т. 166, №2. - С. 287-290.

[36] Б. Н. Пшеничный. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.

[37] Ю. Г. Решетняк. Об одном обобщении выпуклых поверхностей. Матем. сб. 40(82):3 (1956), С. 381-398.

[38 [39

[40

[41

[42

[43

[44

[45

[46

Р. Т. Рокафеллар. Выпуклый анализ. — М.:Мир, 1973.

С. Б. Стечкин. Наилучшее приближение линейных операторов // Матем. заметки. 1967. Т. 1. В. 2. С. 137-148.

А. Г. Сухарев, А. В. Тимохов, В. В. Федоров. Курс методов оптимизации. — М.:ФИЗМАТЛИТ, 2005. — 368 с.

И. Г. Царьков. Непрерывность метрической проекции, структурные и аппроксимативные свойства множеств // Матем. заметки. 1990. Т. 47, В. 2. С. 137-148.

И. Экланд, Р. Темам. Выпуклый анализ и вариационные проблемы. — М.:Мир, 1979.

Т. J. Abatzoglou. The minimum norm projection on C2-manifolds in Mn // Trans, of AMS. 1978. V. 243. - P. 115-122.

T. J. Abatzoglou. The Lipschitz continuity of the metric projection // Journal of Approximation theory 1979. V. 26. P. 212-218.

E. Asplund. Farthest points in reflexive locally uniformly rotund Banach spaces, Isr. J. of Math., 4 (1966), P. 213-216.

J. -P. Aubin, A. Cellina. Differential Inclusions. Set-Valued Maps and Viability Theory. Berlin-Heidelberg-New York-Tokyo, SpringerVerlag 1984.

J. -P. Aubin, H. Frankowska. Set-Valued Analysis. — Boston-BaselBerlin: Birkhauser. 1990.

[48] M. V. Balashov. Weak convexity of the distance function, J. Convex Anal. 20:1 (2013), P. 93-106.

[49] M. V. Balashov, D. Repovs. Uniform convexity and the splitting problem for selections, J. Math. Anal. Appl. 360:1 (2009), P. 307316.

[50] M. V. Balashov, D. Repovs. Polyhedral approximations of strictly convex compacta, J. Math. Anal. Appl. 374:2 (2011), P. 529-537.

[51] M. V. Balashov, D. Repovs. Uniformly convex subsets of the Hilbert space with modulus of convexity of the second order, J. Math. Anal. Appl. 377:2 (2011), P. 754-761.

[52] M. V. Balashov, D. Repovs. On Plis metric on the space of strictly convex compacta, J. Convex Anal. 19:1 (2012), P. 171-183.

[53] F. Bernard, L. Thibault, N. Zlateva. Characterization of proximal regular sets in super reflexive Banach spaces, J. Convex Anal. 13:3,4 (2006), P. 525-559.

[54] B. O. Bjornestal. Local Lipschitz continuity of the metric projection operator // Banach Center Publications. 1979. V. 4. P. 43-54.

[55] J. M. Borwein, S. P. Fitzpatrick. Existence of nearest points in Banach spaces, Canad. J. Math., Vol. XLI, No. 4,1989, PP. 702-720.

[56] F. H. Clarke, Yu. S. Ledyaev, R. J. Stern, P. R. Wolenski. Nonsmooth analysis and Control Theory. Springer-Verlag, New-York Inc., 1998. 276 p.

[57] J. W. Daniel. The continuity of metric projection as function of data // J. Approxim. Theory 12:3 (1974), P. 234-240.

[58] M. Edelstein. Farthest points of sets in uniformly convex Banach spaces // Israel J. Math. - 1966. - V. 4, №3. - P. 171-176.

[59] M. Edelstein. On nearest points of sets in uniformly convex Banach spaces. J. Lond. Math. Soc., 43 (1968), P. 375-377.

[60] S. P. Fitzpatrick. Metric projections and the differentiability of distance function. Bull. Austral. Math. Soc. 22 (1984) P. 291-312.

[61] S. P. Fitzpatrick. Differentiation of real-valued functions and continuity of metric projections. Poc. Amer. Math. Soc. V. 91. No. 4. 1984. P. 544-548.

[62] H. Frankowska, Ch. Olech. r-convexity of the integral of the set-valued functions, Contributions to Analysis and Geometry, John Hopkins Univ. Press, Baltimore, Md., 1981, pp. 117-129.

[63] J. R. Giles, D. A. Gregory, B. Sims. Characterization of normed linear spaces with Mazur's intersection property // Bull. Austral. Math. Soc., 18 (1978), P. 105-123.

[64] A. S. Granero, M. Jiménez-Sevilla, J. P. Moreno. Intersection of closed balls and geometry of Banach spaces // Extracta Math., 19:1 (2004), P. 55-92.

[65] V. Klee. Remarks on nearest points in normed linear spaces. Proc. Colloquium on Convexity (Copenhagen, 1965) Kobenhavns Univ. Mat. Inst., Copenhagen, 1967, pp. 168-176.

[66] J. Lindenstrauss, L. Tfeafiri. Classical Banach Spaces I: Sequence Spaces. New York: Springer-Verlag. — 1977.

[67] S. Mazur. Uber schwache Konvergenz in den Raiimen {lp) // Studia Math., (1933), P. 128-133.

[68] J. -P. Penot. Continuity properties of projection operators. Journal of Inequalities and Applications, 2005:5 (2005), pp. 509-521.

[69] R. R. Phelps. Convex sets and nearest points // Proc. Amer. Math. Soc. 8 (1957), P. 790-797.

[70] R. R. Phelps. Convex sets and nearest points II // Proc. Amer. Math. Soc. 9 (1958), P. 867-873.

[71] R. A. Poliquin, R. T. Rockafellar, L. Thibault. Local differentiability of distance functions, Trans. Amer. Math. Soc. 352 (2000), P. 52315249.

[72] A. Weber, G. Reifiig. Local characterization of strongly convex sets, J. Math. Anal. Appl. 400:2 (2012), P. 743-750.

[73] J. M. Wolfe. Differentiability of nonlinear best approximation operators in a real inner product space. J. Approximation Theory 16 (1976), P. 341-346.

[74] D. E. Wulbert. Continuity of metric projection. Trans, of AMS. 1968. V. 134, N. 2. P. 335-341.

[75] N. V. Zhivkov. Metric projections and antiprojections in strictly convex normed spaces, C. R. Acad. Bulgare Sci., 31:4 (1978), P. 369372.

Публикации автора по теме диссертации

[76] М. В. Балашов, М. О. Голубев. Об условии Липшица для метрической проекции в гильбертовом пространстве. // Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном сообществе. - Т.1: Труды

54-й научной конференции МФТИ. /Моск. физ, - техн. ин-т. -М. - Долгопрудный, 2011. - С . 34-34.

[77] М. О. Голубев. Метрическая проекция в гильбертовом пространстве и сильная выпуклость. // материалы 16-й международной Саратовской зимней школы «Современные проблемы теории функций и их приложения» - Саратов: ООО Издательство «Научная книга», 2012. - С . 55-56.

[78] М. О. Голубев. Метод проекции градиента для сильно выпуклого множества // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 13:1(2) (2013), С. 33-38.

[79] М. О. Голубев. Связь сильно выпуклых множеств с сильной выпуклостью функции расстояния и слабой вогнутостью функции антирасстояния. // материалы 17-й международной Саратовской зимней школы «Современные проблемы теории функций и их приложения» - Саратов: ООО Издательство «Научная книга», 2014. - С . 76-78.

[80] М. V. Balashov, М. О. Golubev. About the Lipschitz property of the metric projection in the Hilbert space, J. Math. Anal. Appl. 394:2 (2012), P. 545-551.

[81] M. V. Balashov, M. O. Golubev. Weak concavity of the antidistance function // J. Convex Anal. 2014. №4, P. 951-964. on-line с октября 2013 года по адресу http://www.heldermann.de/JCA/JCA21/JCA214/jca21051.htm

[82] М. О. Golubev. Local strong convexity in the Hilbert space. // proceedings of IV Internatioanl Conference on Optimization Methods and Applications «Optimization and applications» (OPTIMA-2013). - Petrovac, 2013. - P . 68-69.