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

На правах рукописи

ГОЛУБЕВ МАКСИМ ОЛЕГОВИЧ

МЕТРИЧЕСКАЯ ПРОЕКЦИЯ И ФУНКЦИИ

РАССТОЯНИЯ И АНТИРАССТОЯНИЯ ДЛЯ СИЛЬНО ВЫПУКЛЫХ МНОЖЕСТВ

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

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

Москва — 2014

2 3 0К Г 2014

005553628

005553628

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

Научный руководитель: Доктор физико-математических наук,

доцент

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

Официальные оппоненты: Доктор физико-математических наук,

профессор

Дудов Сергей Иванович,

Саратовский государственный университет имени Н. Г. Чернышевского кафедра математической экономики, заведующий кафедрой.

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

Алимов Алексей Ростиславович,

Московский государственный университет имени М. В. Ломоносова, кафедра теоретической информатики механико-математического факультета, научный сотрудник.

Ведущая организация: Институт проблем управления

имени В. А. Трапезникова РАН

Защита состоится У/ ^ 2014 г. в часов на

заседании диссертационного совета Д 212.156.05 на базе Московского физико-технического института (государственного университета) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета) и на сайте университ http://www.mipt.ru.

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

Ученый секретарь

диссертационного совета / Федько Ольга Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Оператор метрического проектирования яв-яется классическим объектом исследования специалистами по теории ункций и оптимизации. Понятие оператора метрического проектирова-"ия играет важную роль в оптимизации (см. 1'2'3>4)) негладком анализе в работах5*6'7'8), теории приближений (см. работы 9,io,n,i2^ Свойства ператора метрического проектирования представляют большой инте-ес именно в гильбертовом пространстве, поскольку понятие гильбертова ространства является важным для широкого круга приложений. Клас-ический результат состоит в том, что оператор метрического проекти-ования на выпуклое замкнутое множество в гильбертовом пространстве довлетворяет условию Липшица с константой равной 1 по точке (в бес-онечномерном гильбертовом пространстве результат, вероятно, впервые ироко опубликован в работе13, в конечномерном пространстве - изве-тен много раньше). При этом, как следует из результатов Й. Линден-1траусса14, равномерная непрерывность оператора метрического проек-ирования на любое замкнутое подпространство в банаховом простран-тве характеризует это пространство: в нем существует эквивалентная

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

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

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

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

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

6J. -P. Aubin, A. Cellina. Differential Inclusions. Set-Valued Maps and Viability Theory. Berlin-eidelberg-New York-Tokyo, Springer-Verlag 1984.

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

SF. H. Clarke, Yu. S. Ledyaev, R. J. Stern, P. R. Wolenski. Nonsmooth analysis and Control Theory.

ringer-Verlag, New-York Inc., 1998. 276p.

9Я. В. Ефимов, С. Б. Сте-чкин. Некоторые свойства чебышевских множеств // Докл. АН СССР, 8:1. (1958) С. 17-59.

10 К. Klee. Remarks on nearest points in normed linear spaccs. Proc. Colloquium on Convexity openhagen, 196-5) Kobenhavns Univ. Mat. Inst., Copenhagen, 1967, pp. 168-176.

nM. Edelstein. On nearest points of sets in uniformly convex Banach spaces. J. Lond. Math. Soc., 43 968), P. 375-377.

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

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

"7. Lindenstrauss, L. Tzafiri. Classical Banach Spaces I: Sequence Spaces. New York: Springer-Verlag. 1977.

гильбертовой норма. Как доказал Дж. Даниэль15, при фиксированно точке проектирования оператор метрического проектирования являете гёльдеровым по множеству с показателем | в метрике Хаусдорфа. Ука занные свойства и в первую очередь условие Липшица с константой 1 являются важными во многих теоретических и прикладных вопросах Однако во многих задачах условия Липшица с константой 1 недостаточ но - нужна сжимаемость оператора метрического проектирования. На пример, в различных проекционных алгоритмах (в частности, в метод проеции градиента при отсутствии условия сильиой выпуклости функ ции хороших оценок для скорости сходимости обычно не получается) i итеративных методах (см. 1'2'3=4»16'17'18). Очевидно, что сжимаемость one ратора метрического проектирования возможна лишь при условии, чт точка проектирования достаточно удалена от множества, а также пр некоторых ограничениях на геометрические свойства самого множеств Исследованием оператора проектирования занимались многие сп циалисты: Р. Фелпс13,19, Н. В. Ефимов9, С. Б. Стечкин9, В. Кли1 Дж. Даниэль15, В. И. Бердышев20'21'12 и его школа (А. В. Маринов2 и др. (ИММ УрО РАН)), Дж. Вулф23, Т. Абацоглу24'25, С. В. Кон

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

16D. Butnariu, Y. Censor. Strong convergence of almost simultaneous block-iterative projection metho in Hilbert spaces // Journal of Computational and Applied Mathematics 53 (1994), P. 33-42.

17H. H. Bauschke, J. Borwein. On projection algorithms for solving convex feasibility problems //' SIA Review, 38 (1996), P. 367-42G.

18 C. Byrne. Iterative oblique projection onto convex sets and the split feasibility problem // Inver Problems, 18 (2002), P. 441-453.

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

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

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

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

23 J. М. Wolfe. Differentiability of nonlinear best approximation operators in a real inner product spac J. Approximation Theory 16 (1976), P. 341-346.

24 T. J. Abatzoglou. The minimum norm projection on C2-manifolds in R". // Trans, of AMS. 197 V. 243. - P. 115-122.

25 T. J. Abatzoglou. The Lipschitz cont inuity of the metric projection // Journal of Approximation theor 1979. V. 26. P. 212-218.

ПН26'27, Б. Бьорнсталь28, С. Фицпатрик29'30, Ф. Кларк31'8, И. Г. Царь-ов32, Р. Штерн8, П. Воленски8, Л. Тибо33.

В некотором смысле окончательные результаты в гильбертовом про-трапстве для аппроксимативных компактов с С2 -гладкой границей (то сть граница множества является многообразием, которое в окрестности 'раничной точки m представляется таким отображением /, что выпол-гены следующие условия: (1) / - открытое отображение на своей области пределения, то есть некотором открытом множестве в R™, (2) / - С2, (3) '(а) ■ R71 = R", где а — /(га) ) были получены в работах Абацоглу24'25. ри условии, что граница множества С2 -гладкая, Абацоглу предложил бобщение понятия радиуса кривизны множества и при определенных словиях получил точную оценку константы Липшица меньше 1. При том для множеств с негладкой границей точных результатов получе-ю не было, кроме того, не было ясно, на какой класс множеств не с 2 -гладкой границей могут быть обобщены результаты, полученные для множеств с С2 -гладкой границей.

Метрическая проекция на множество тесно связана со свойствами ункции расстояния от точки до множества. Здесь классическим являет-я результат о том, что выпуклость замкнутого множества эквивалентна ыпуклости функции расстояния (см. например31). Исследованием функ-щи расстояния занималось огромное число математиков: Р. Т. Рокафел-

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

27 С. В. Конягин. О множествах точек непустоты и непрерывности метрическоГ1 проекции. Матсм. амсткп, 33:5 (1983), 641-655.

2SB. О. Bjornestál. Local Lipschitz continuity of the metric projection operator // Banach Center ublications. 1979. V. 4. P. 43-54.

29S. P. Fitzpatrick. Differentiation of real-valued functions and continuity of metric projections. Рос. mer. Math. Soc. V. 91. No. 4. 1984. P. 544-548.

30S. P. Fitzpatrick. Metric projections and the differentiability of distance function. Bull. Austral. Math, oc. 22 (1984) P. 291-312.

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

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

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

лар34-35, И. Экланд36'5, X. Франковска37'7, Ж. -П. Обэн5-6'7, А. Челлина6, С. Фицпатрик29,30,38, Ф. Кларк31,8, С. И. Дудов39'40, Е. С. Половинкин41'42, М. В. Балашов42,43.

Гораздо в меньшей степени известна и популярна функция, кото рую мы называем функцией антирасстояния. Для замкнутого ограни ченного- множества в банаховом пространстве функция антирасстояни - это супремум расстояния от заданной точки до точек из множества В отличие от функции расстояния, которая может не быть выпуклой функция антирасстояиия всегда выпукла. Важный результат был по лучен Эделстейном44, который доказал некоторые "антиаппроксиматив ные"свойства для множеств в гильбертовом пространстве. Существен ным продвижением в исследовании функции антирастояния и единствен ности и непрерывности антипроекции (точки множества, на которой ре ализуется функция антирасстояния) содержатся в работе М. В. Балашо ва и Г. Е. Иванова45 и работе Г. Е. Иванова46. Из результатов работы4 следует, что в гильбертовом пространстве совокупность условий суще ствования, единственности и липшицевой зависимости от х метрическо! антипроекции х на множество А для точек х. достаточно удаленных о множества А, эквивалентна сильной выпуклости множества А.

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

35Л. A. Poliquin, R. Т. Rockafellar, L. Thibault. Local differentiability of distance functions, Trant Amer. Math. Soc. 352 (2000), P. 5231-5249.

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

37Н. Frankowska, Ch. Olech. Д-convexity of the integral of the set-valued functions, Contributions t Analysis and Geometry, John Hopkins Univ. Press, Baltimore, Md., 1981, pp. 117-129.

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

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

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

пЕ. С. Половинкин. Сильно выпуклый анализ, Матем. сб., 187:2 (1996), С. 103-130.

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

43М. V. Balashov. Weak convexity of the distance function, J. Convex Anal. 20:1 (2013), P. 93-106.

44M. Edelstein. Farthest points of sets in uniformly convex Banach spaces /,/ Israel J. Math. — 1966. V. 4, No.3. — P. 171-176.

45M. В. Балашов, Г. E. Иванов. Об удаленных точках множеств /7 Матем. заметки. 80:2. (200 С. 163-170.

46Г. Е. Иванов. Наиболее удаленные точки и сильная выпуклость множеств // Матем. заметк! 87:3. (2010) С. 355-366.

Одно из важных приложений оператора метрического проектирования в оптимизации - это построение проекционных алгоритмов для ре-:ения некоторого класса экстремальных задач. В первую очередь речь дет о поиске минимума выпуклой функции на выпуклом множестве, дним из классических алгоритмов здесь является метод проекции гра-иента (метод детально изложен в работах1'2,3'4).-Последовательность ге-юрируется по правилу

Хк+1 = Рл(хк ~ ак/'(хк)), хх е Ьс1 А, ак > О,

де через Ьс1 А будем обозначать границу множества А. При этом в аботах1'2'3'4 для выпуклого множества и сильно выпуклой функции при словии липшицевой дифференцируемое™ функции при определенном ыборе параметра шага ак доказывается сходимость данного метода к динственному решению со скоростью геометрической прогрессии.

Цели работы.

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

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

. Доказать сходимость метода проекции градиента для выпуклой (в общем случае, не обязательно сильно выпуклой) функции и сильно выпуклого множества. Получить оценки скорости сходимости.

Получить оценку константы Липшица метрической проекции н внешнюю многогранную аппроксимацию сильно выпуклого множе ства в Е".

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

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

Теоретическая и практическая ценность. Работа носит теорети ческий характер. Результаты могут применяться в дальнейших исследо ваниях в области выпуклого и сильно выпуклого анализа, в оптимиза ции и теории приближений. В работе получены новые критерии сильно! выпуклости множества в гильбертовом пространстве связанные с уело вием Липшица с константой строго меньше 1 оператора метрическог проектирования и слабой вогнутостью функции антирасстояния. Такж получены новые результаты связанные с оценкой скорости сходимост1 метода проекции градиента для выпуклой функции, а также сильно вы пуклого множества. Работа поддержана грантами РФФИ 13-01-00295-а 10-01-00139-а.

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

• 54-й научной конференции МФТИ «Проблемы фундаментальны и прикладных естественных и технических наук в современно информационном сообществе» Москва-Долгопрудный-Жуковски" 2011;

• 16-й международной Саратовской зимней школе «Современные пр блемы теории функций и их приложения», Саратов, 2012;

• Научных семинарах кафедры высшей математики МФТИ, Долг прудный, 2011 - 2014;

• Научных семинарах «Негладкий анализ» под руководство Г. Е. Иванова, Долгопрудный, 2011 - 2014;

• Научном семинаре «Теория автоматического управления и оптим зация» лаборатории 7 ИПУ РАН, Москва, 2012;

• IV International Conference on Optimization Methods and Applications «Optimization and Applications (OPTIMA-2013)» Petrovac, 2013;

• 17-й международной Саратовской зимней школе «Современные проблемы теории функций и их приложения», Саратов, 2014;

• Специальном семинаре кафедры ОПУ мехмата МГУ «Теория приближений» под руководством И. Г. Царькова, Москва, 2014.

Публикации. Основные результаты опубликованы в семи работах, писок которых приведен в конце автореферата. Работы [2,4,7] входят в "писок изданий, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, вух глав, заключения и списка литературы. Общий объем диссертации ^оставляет 89 страниц. Список литературы содержит 82 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Нумерация определений, предложений, теорем, следствий в авторефе-ате совпадает с нумерацией определений, предложений, теорем, след-твий соответственно в диссертационной работе.

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

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

Все результаты первой главы получены для вещественнозначного

ильбертова пространства И. Через (р, х) будем обозначать скалярное

роизведение векторов р, х £ Н. Для множества А С Н через bd А

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

а R > 0 с центром в точке х £ Н будем обозначать через Вд(х) —

у € Н : — х|| < R}. Диаметр множества А определяется сле-

ующим образом diam^ = sup ||ж — у\\. Нормальным конусом к вых

пуклому замкнутому множеству А в точке а £ А называется множество АГ(А;а) = <р £ Н : (р, а) > sup(р,х) >. Напомним, что для мно-

I хеА J

жества А выпуклой оболочкой множества со А называется пересечение

всех выпуклых множеств, содержащих А. Расстояние от точки х £ Н

до множества А задается формулой qa{x) = inf IIa; — all. Метриче-

aeA

ской проекцией точки х £ Н на множество А С Н называется множество Ра{х) = {а £ А : \\х — а|| = ^(ж)}. Для множества А £ I определим открытую ^-окрестность множества А следующим образом UA(ß) = {х £ Н : дА(х) < р}.

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

Определение 1.1.5 [Определение 4.3.142] Непустое множество А С Н называется сильно выпуклым множеством с радиусом R, если он может быть представлено в виде пересечения замкнутых шаров радиус

R > 0, то есть Л = П Вц(х) для некоторого множества X С Н. хех

В части 2 первой главы упоминается результат М. В. Балашова. Предложение 1.2.147 Пусть Ас! замкнутое выпуклое ограничен ное множество, g > О, С £ (0,1). Пусть выполнено следующее условие для любой пары точек х0,х\ £ Н \ Ua(q), где {a¿} = Pa{xí), г £ {0,1 верно

IK - «ill < С • ||^о - Zill-Тогда А является сильно выпуклым множеством с радиусом R = ^^.

В связи с этим результатом возникает вопрос: как устроен модул равномерной непрерывности оператора метрического проектирования н сильно выпуклое с радиусом R > 0 подмножество гильбертова простран ства? Ответ на этот вопрос дает следующая теорема.

Теорема 1.2.147 Пусть множество ЛсН является сильно выпук лым множеством с радиусом R. Тогда для любых точек ,т0, Х\ £ Н\.

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

ыполнено неравенство

Я,

1К - а1|| < ,(Т> , • \/|ко-Ж1||2-(^о-^1)2,

у/(Я + во){Я + £1)

де {ец} = Рл{хг), йг = Цж,- - а/(|, г е {0,1}.

Из предложения 1.2.1 и теоремы 1.2.1 вытекает следующее утвержде-ие.

Следствие 1.2.147 Пусть непустое множество А С Н выпукло и амкнуто. Тогда следующие условия эквивалентны:

1) А сильно выпуклое множество с радиусом Я> О,

2) Уд > 0; £ Ш\ , где {а;} = Рд(х^, г € {0,1}, выполнено

||«о — сы|| < (К + ду 1ко-Ж1||.

В теореме 1.2.1 мы требовали сильной выпуклости множества, однако ередка ситуация, когда часть границы множества устроена как часть раницы некоторого сильно выпуклого множества, а само множество при том не является сильно выпуклым и может быть даже неограниченным, апример, надграфик функции /: К —> М

/(*) =

X I ^ э X 2 5

1- VI - ж2,

X I 2 ? ^ 2*

огда возникают определенные трудности в переносе результатов для ильно выпуклых множеств на этот случай. Пусть 5 С Ьс1 А Определим следущее множество

ЧхеЯ /

\иА{о). (1)

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

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

ция 5а'- [0,diamA) —» [0, +оо) определяемая формулой

5A(t) = sup [б > О I В5 (^р1) С A, Vx0, xi Е А : ||х0 - хх\\ = t} .

Отметим, что модуль выпуклости замкнутого выпуклого множества непустой внутренностью удовлетворяет условию Sy\(t) < Ct2 для некото poro С > О [Следствие 2.349].

Для части границы множества S С bd А мы рассмотрим аналог м дуля выпуклости

Ss(t) = sup [б > О I Bs С А, Ухо, х\ е S : ||х0 - хг\\ = t} .

Теорема 1.2.2 Пусть А С Н замкнутое выпуклое множество S С bd А, а множество Ф задано формулой (1). Пусть функция 5s{t удовлетворяет условию Ss(t) > Ctp, где С > 0, р > 2.

Тогда \/е > 0 35 > 0 Ужо,^ G Ф : ||ж0 - zi|| < 6, {а0} = Рл(х0) {ai} = Ра(хi), ||жо — ао|| > Q, H^i — ai|| > Q, выполнена оценка

Iko - > ||ао - «ill2 + - е) \\ао ~ ai||p+

} 16C2g2 \ .. ц2р—2 + ((l_2l-P)2-£j Hß0-«lH2P 2-

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

Следствие 1.2.2 Пусть выполнены условия теоремы 1.2.2, р = 2 Тогда для любых точек xq,X\ € Ф таких, что [ха,х-\\ С Ф выполнен неравенство

Ik - Olli < 1 + gC »SO - Zill,

49Ai. V. Balashov, D. Repovs. Uniform convexity and the splitting problem for selections, J. Math. Ana Appl. 360:1 (2009), P. 307-316.

де {щ} = PA(xi), i е {0,1}.

Теорема 1.2.3 Пусть А С Н выпуклое замкнутое множество, устъ S С bd А, а множество Ф задано формулой (1). Предположилi, то существует число С G (0; 1), такое что для любых xq, G Ф верна едующая формула:

||°о — ai|| < С\\хо — ^lll) '{ai} = PA{xi), i G {0,1}. (2)

Пусть а Е S, и R =

Тогда для всех £ G (О, R) со свойством В£(а) Q bd А С S множество Р| В£(а) является сильно выпуклым с радиусом R.

Теорема 1.2.3 обобщает предложение 1.2.1 на более широкий класс ножеств.

В части 3 первой главы немного уточняется результат о сильной ыпуклости (при определенных условиях) функции расстояния [Теорема ,950].

Рассматривается функция антирасстояния.

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

/д(ж) = sup ||ж — а||

аёЛ

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

Основным результатом 3 части является следующая теорема.

Теорема 1.3.351 Пусть А С Н сильно выпуклое множество с ра-иусом R. Пусть г > R. Тогда функция антирасстояния /л(ж) слабо огнута на множестве (Н \ 5Г(0)) + А с константой

Также упоминается результат М. В. Балашова.

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

51М. V. Balashov, М. О. Golubev. Weak concavity of the antidistance function /,/ J. Convex Anal. 2014. N4. P. 951-964

Предложение 1.3.351 Пусть А С Н замкнутое выпуклое ограниче ное множество и г > 0. Предположим, что функция антирасстояни /а слабо вогнута на множестве (Н\ Д-(О)) + А с константой С > Тогда множество А сильно выпуклое множество радиуса г —

Из теоремы 1.3.3 и предложения 1.3.3 вытекает следующее утвержд ние.

Следствие 1.3.251 Пусть А С Н замкнутое выпуклое ограниченн множество и R > 0. Тогда следующие условия эквивалентны:

1) А сильно выпуклое мнооюество с радиусом R

2) Для всех г > R функция антирасстояния /л слабо вогнута множестве (Н \ ßr(0)) + А с константой С = ^гд.

Оценки 1) и 2) следствия 1.3.2 точны в том смысле, что если R - на меньший радиус сильной выпуклости множества А, то С - наименьш константа слабой вогнутости функции антирасстояния /д, и наоборо если С - наименьшая константа слабой вогнутости функции антира стояния /д, то R - наименьший радиус сильной выпуклости множест А.

В части 1 второй главы описывается стандартный метод проекц градиента и приводятся известные оценки скорости сходимости мето для сильно выпуклой функции и выпуклого множества1'2'3.

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

Рассмотрим задачу минимизации

f(x) min, х е А Cl. (

Последовательность генерируется следующим образом:

xk+i = PA{xk - akf(xk)), х\ е bd А, ak > 0. (

(i) t = ¿иша\\Г(х)\\ > 0,

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

iii) Функция является выпуклой, дифференцируемой и градиент f'(x) удовлетворяет условию Липшица с константой М > О,

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

х<=Л

) Для всех к е N существует вектор п(хк) £ N(A]xk), такой что выполняется неравенство (п(хк), f'{%k)) < 0 (то есть хк — о>к/'(хк) ^ А для любого ак > 0).

В случае, когда условие (v) не выполняется, мы имеем де-

о с безусловной минимизацией и следует использовать один

з стандартных алгоритмов поиска безусловного минимума (см. апример4(те0рсма Теорема 2-1- Глава 5)^

Теорема 2.2.1 52 а) Пусть выполнены условия (i)-(v). Пусть ак =

Тогда последовательность хк, генерируемая по правилу (4), сходится

решению задачи (3) со скоростью геометрической прогрессии: ||a;fc+i —

R

< Ч\\хк - х*||, где д = ^^^

Ь) Пусть выполнены условия (гг)-(у). Пусть ак — а Е (0, . Тогда последовательность хк, генерируемая по правилу (4), сходится решению задачи (3) и верна формула: ||ж£+1 — ж*|| < дк\\хк — ж*||, где

_ 4

f.

R?

Теорема 2.2.2 ъ2Пусть выполнены условия (г)-(Ш). Пусть ™ < 1. Последовательность хк генерируется по правилу (4) с ак = а > 0 ■Я бсбх к. Тогда:

1) при выборе а £ (^тд] последовательность хк сходится к реше-ию задачи (3) со скоростью геометрической прогрессии: Цгг^! — х*|| <

2) при выборе а > последовательность хк сходится к решению адачи (3) со скоростью геометрической прогрессии: Цж^+х — ж*|| <

\\хк — х* ||, где q =

R(aM-1) at-R

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

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

Часть 3 второй главы посвящена многогранным аппроксимация сильно выпуклых множеств в М". Получена оценка на константу Липши ца оператора метрического проектирования на внешнюю многогранну аппроксимацию сильно выпуклого множества. Показано, что при некот ром наборе параметров, и в первую очередь достаточно малой мелкост сетки, константа Липшица может быть меньше 1.

Теорема 2.4.1 Пусть задана сетка G мелкости Д € (0, (гд мелкость сетки понимается в смысле определения 2-4-142)- Пусть мн жество А С М" является сильно выпуклым множеством с радиусо R > 0. Множество

А = {хе R"| (р, х) < s{p, A), Vp е G}

выпуклая внешняя многогранная аппроксимация множества А. Пуст заданы числа I > 0, g > 0. Пусть Xq,X\ € М" \ Ua{q), — > Определим множество В = со{Л U {жо,^}} и точки {о^} = P^ixi г 6 {0,1}. Тогда верно следующее неравенство:

||ао - а{\\ < |4 (у/2 R ■ diam В А + ДД2) j + д^} И^о - хг\\. (

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. М. В. Балашов, М. О. Голубев. Об условии Липшица для метриче ской проекции в гильбертовом пространстве. // Проблемы фунда ментальных и прикладных естественных и технических наук в со временном информационном сообществе. - Т.1: Труды 54-й научн01 конференции МФТИ. /Моск. физ. - техн. ин-т. - М. - Долгопруд ный, 2011. - С . 34-34.

2. М. V. Balashov, М. О. Golubev. About the Lipschitz property of th metric projection in the Hilbert space //J. Math. Anal. Appl. — 201

- 394:2 - P . 545-551. '

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

- С . 55-56.

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

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

6. M. О. Голубев. Связь сильно выпуклых множеств с сильной выпу лостыо функции расстояния и слабой вогнутостью функции ант расстояния. // материалы 17-й международной Саратовской зимне школы «Современные проблемы теории функций и их приложения

- Саратов: ООО Издательство «Научная книга», 2014. - С . 76-78

7. М. V. Balashov, М. О. Golubev. Weak concavity of tl antidistance function. // J. Convex Anal. - 2014.

N4. P. 951-964. on-line с октября 2013 года но адресу http://www.heldermann.de/JCA/JCA21/JCA214/jca21051.htm

Личный вклад соискателя в работы с соавторами заключается в следующем: [1] - теорема 2. [2] - теоремы 2.2 и 3.1. [7] - теорема 3.1.

Голубев Максим Олегович

МЕТРИЧЕСКАЯ ПРОЕКЦИЯ И ФУНКЦИИ РАССТОЯНИЯ И АНТИРАССТОЯНИЯ ДЛЯ СИЛЬНО ВЫПУКЛЫХ МНОЖЕСТВ

АВТОРЕФЕРАТ

Подписано в печать 10.10.2014. Формат 60 х 84 1/16 . Усл. печ. л. 1,0.

Тираж 100 экз. Заказ №360 Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9