close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
ГОЛУБЕВ МАКСИМ ОЛЕГОВИЧ
МЕТРИЧЕСКАЯ ПРОЕКЦИЯ И ФУНКЦИИ
РАССТОЯНИЯ И АНТИРАССТОЯНИЯ
ДЛЯ СИЛЬНО ВЫПУКЛЫХ МНОЖЕСТВ
01.01.09 — дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва — 2014
Работа выполнена на кафедре высшей математики Московского
физико-технического института (государственного университета)
Научный руководитель:
Доктор физико-математических наук,
доцент
Балашов Максим Викторович
Официальные оппоненты:
Доктор физико-математических наук,
профессор
Дудов Сергей Иванович,
Саратовский государственный университет
имени Н. Г. Чернышевского
кафедра математической экономики,
заведующий кафедрой.
Кандидат физико-математических наук,
доцент
Алимов Алексей Ростиславович,
Московский государственный университет
имени М. В. Ломоносова, кафедра
теоретической информатики
механико-математического факультета,
научный сотрудник.
Ведущая организация:
Институт проблем управления
имени В. А. Трапезникова РАН
Защита состоится
2014 г. в
часов на
заседании диссертационного совета Д 212.156.05 на базе Московского физикотехнического института (государственного университета) по адресу 141700,
Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета) и на сайте университета
http://www.mipt.ru.
Автореферат разослан
Ученый секретарь
диссертационного совета
2014 г.
Федько Ольга Сергеевна
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Оператор метрического проектирования является классическим объектом исследования специалистами по теории
функций и оптимизации. Понятие оператора метрического проектирования играет важную роль в оптимизации (см. 1,2,3,4), негладком анализе
(в работах5,6,7,8), теории приближений (см. работы 9,10,11,12). Свойства
оператора метрического проектирования представляют большой интерес именно в гильбертовом пространстве, поскольку понятие гильбертова
пространства является важным для широкого круга приложений. Классический результат состоит в том, что оператор метрического проектирования на выпуклое замкнутое множество в гильбертовом пространстве
удовлетворяет условию Липшица с константой равной 1 по точке (в бесконечномерном гильбертовом пространстве результат, вероятно, впервые
широко опубликован в работе13, в конечномерном пространстве - известен много раньше). При этом, как следует из результатов Й. Линденштраусса14, равномерная непрерывность оператора метрического проектирования на любое замкнутое подпространство в банаховом пространстве характеризует это пространство: в нем существует эквивалентная
1
Ф. П. Васильев. Численные методы решения экстремальных задач. — М.:Наука, 1980. — 520с.
Б. Т. Поляк. Введение в оптимизацию. — М.:Наука, 1983. — 384с.
3
А. Г. Сухарев, А. В. Тимохов, В. В. Федоров. Курс методов оптимизации. — М.:ФИЗМАТЛИТ,
2005. — 368с.
4
Ю. Е. Нестеров. Введение в выпуклую оптимизацию. — М.:МЦНМО, 2010. — 279с.
5
Ж. -П. Обэн, И. Экланд. Прикладной нелинейный анализ. — М.: Мир. 1984.
6
J. -P. Aubin, A. Cellina. Differential Inclusions. Set-Valued Maps and Viability Theory. BerlinHeidelberg-New York-Tokyo, Springer-Verlag 1984.
7
J. -P. Aubin, H. Frankowska. Set-Valued Analysis. — Boston-Basel-Berlin: Birkhauser. 1990.
8
F. H. Clarke, Yu. S. Ledyaev, R. J. Stern, P. R. Wolenski. Nonsmooth analysis and Control Theory.
Springer-Verlag, New-York Inc., 1998. 276p.
9
Н. В. Ефимов, С. Б. Стечкин. Некоторые свойства чебышевских множеств // Докл. АН СССР,
118:1. (1958) С. 17–59.
10
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.
11
M. Edelstein. On nearest points of sets in uniformly convex Banach spaces. J. Lond. Math. Soc., 43
(1968), P. 375–377.
12
В. И. Бердышев. Непрерывность многозначного отображения, связанного с задачей минимизации
функционала // Изв. АН СССР. Сер. матем. 1980. Т. 44, В. 3. С. 483–509.
13
R. R. Phelps. Convex sets and nearest points // Proc. Amer. Math. Soc. 8 (1957), P. 790–797.
14
J. Lindenstrauss, L. Tzafiri. Classical Banach Spaces I: Sequence Spaces. New York: Springer-Verlag.
— 1977.
2
3
гильбертовой норма. Как доказал Дж. Даниэль15, при фиксированной
точке проектирования оператор метрического проектирования является
гёльдеровым по множеству с показателем 12 в метрике Хаусдорфа. Указанные свойства и в первую очередь условие Липшица с константой 1,
являются важными во многих теоретических и прикладных вопросах.
Однако во многих задачах условия Липшица с константой 1 недостаточно - нужна сжимаемость оператора метрического проектирования. Например, в различных проекционных алгоритмах (в частности, в методе
проеции градиента при отсутствии условия сильной выпуклости функции хороших оценок для скорости сходимости обычно не получается) и
итеративных методах (см. 1,2,3,4,16,17,18). Очевидно, что сжимаемость оператора метрического проектирования возможна лишь при условии, что
точка проектирования достаточно удалена от множества, а также при
некоторых ограничениях на геометрические свойства самого множества.
Исследованием оператора проектирования занимались многие специалисты: Р. Фелпс13,19, Н. В. Ефимов9, С. Б. Стечкин9, В. Кли10,
Дж. Даниэль15, В. И. Бердышев20,21,12 и его школа (А. В. Маринов22
и др. (ИММ УрО РАН)), Дж. Вулф23, Т. Абацоглу24,25, С. В. Коня15
J. W. Daniel. The continuity of metric projection as function of data // J. Approxim. Theory 12:3
(1974), P. 234–240.
16
D. Butnariu, Y. Censor. Strong convergence of almost simultaneous block-iterative projection methods
in Hilbert spaces // Journal of Computational and Applied Mathematics 53 (1994), P. 33–42.
17
H. H. Bauschke, J. Borwein. On projection algorithms for solving convex feasibility problems // SIAM
Review, 38 (1996), P. 367–426.
18
C. Byrne. Iterative oblique projection onto convex sets and the split feasibility problem // Inverse
Problems, 18 (2002), P. 441–453.
19
R. R. Phelps. Convex sets and nearest points II // Proc. Amer. Math. Soc. 9 (1958), P. 867–873.
20
В. И. Бердышев. Пространства с равномерно непрерывной метрической проекцией // Матем.
заметки. 1975. Т. 17, В. 1. С. 3–12.
21
В. И. Бердышев. Эквивалентность равномерной непрерывности метрической проекции и ν–
проекции // Матем. заметки. 1980. Т. 28, В. 4. С. 571–582.
22
А. В. Маринов. Константы Липшица оператора метрического ε–проектирования в пространствах
с заданными модулями выпуклости и гладкости // Изв. РАН. Сер. матем. 1998. Т. 62. В. 2. С. 103–130.
23
J. M. Wolfe. Differentiability of nonlinear best approximation operators in a real inner product space.
J. Approximation Theory 16 (1976), P. 341–346.
24
T. J. Abatzoglou. The minimum norm projection on C 2 -manifolds in Rn . // Trans. of AMS. 1978.
V. 243. — P. 115–122.
25
T. J. Abatzoglou. The Lipschitz continuity of the metric projection // Journal of Approximation theory.
1979. V. 26. P. 212–218.
4
гин26,27, Б. Бьорнсталь28, С. Фицпатрик29,30, Ф. Кларк31,8, И. Г. Царьков32, Р. Штерн8, П. Воленски8, Л. Тибо33.
В некотором смысле окончательные результаты в гильбертовом пространстве для аппроксимативных компактов с C 2 -гладкой границей (то
есть граница множества является многообразием, которое в окрестности
граничной точки m представляется таким отображением f , что выполнены следующие условия: (l) f – открытое отображение на своей области
определения, то есть некотором открытом множестве в Rn, (2) f – C 2, (3)
f 0(a) · Rn = Rn, где a = f (m) ) были получены в работах Абацоглу24,25.
При условии, что граница множества C 2 -гладкая, Абацоглу предложил
обобщение понятия радиуса кривизны множества и при определенных
условиях получил точную оценку константы Липшица меньше 1. При
этом для множеств с негладкой границей точных результатов получено не было, кроме того, не было ясно, на какой класс множеств не с
C 2 -гладкой границей могут быть обобщены результаты, полученные для
множеств с C 2 -гладкой границей.
Метрическая проекция на множество тесно связана со свойствами
функции расстояния от точки до множества. Здесь классическим является результат о том, что выпуклость замкнутого множества эквивалентна
выпуклости функции расстояния (см. например31). Исследованием функции расстояния занималось огромное число математиков: Р. Т. Рокафел26
С. В. Конягин. Аппроксимативные свойства произвольных множеств в банаховых пространствах.
Докл. АН СССР 239:2. (1978). 261–264.
27
С. В. Конягин. О множествах точек непустоты и непрерывности метрической проекции. Матем.
заметки, 33:5 (1983), 641–655.
28
B. O. Björnestȧl. Local Lipschitz continuity of the metric projection operator // Banach Center
Publications. 1979. V. 4. P. 43–54.
29
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.
30
S. P. Fitzpatrick. Metric projections and the differentiability of distance function. Bull. Austral. Math.
Soc. 22 (1984) P. 291–312.
31
Ф. Кларк. Оптимизация и негладкий анализ. М.: Наука, 1988.
32
И. Г. Царьков. Непрерывность метрической проекции, структурные и аппроксимативные свойства
множеств // Матем. заметки. 1990. Т. 47, В. 2. С. 137–148.
33
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.
5
лар34,35, И. Экланд36,5, Х. Франковска37,7, Ж. -П. Обэн5,6,7, А. Челлина6,
С. Фицпатрик29,30,38, Ф. Кларк31,8, С. И. Дудов39,40, Е. С. Половинкин41,42,
М. В. Балашов42,43.
Гораздо в меньшей степени известна и популярна функция, которую мы называем функцией антирасстояния. Для замкнутого ограниченного множества в банаховом пространстве функция антирасстояния
– это супремум расстояния от заданной точки до точек из множества.
В отличие от функции расстояния, которая может не быть выпуклой,
функция антирасстояния всегда выпукла. Важный результат был получен Эделстейном44, который доказал некоторые "антиаппроксимативные"свойства для множеств в гильбертовом пространстве. Существенным продвижением в исследовании функции антирастояния и единственности и непрерывности антипроекции (точки множества, на которой реализуется функция антирасстояния) содержатся в работе М. В. Балашова и Г. Е. Иванова45 и работе Г. Е. Иванова46. Из результатов работы45
следует, что в гильбертовом пространстве совокупность условий существования, единственности и липшицевой зависимости от x метрической
антипроекции x на множество A для точек x, достаточно удаленных от
множества A, эквивалентна сильной выпуклости множества A.
34
Р. Т. Рокафеллар. Выпуклый анализ. — М.:Мир, 1973.
R. A. Poliquin, R. T. Rockafellar, L. Thibault. Local differentiability of distance functions, Trans.
Amer. Math. Soc. 352 (2000), P. 5231–5249.
36
И. Экланд, Р. Темам. Выпуклый анализ и вариационные проблемы. — М.:Мир, 1979.
37
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.
38
J. 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:3
(1995) С. 29–52.
40
С. И. Дудов. Субдифференцируемость и супердифференциреумость функции расстояния // Матем. заметки, 61:4 (1997) С. 530–542.
41
Е. С. Половинкин. Сильно выпуклый анализ, Матем. сб., 187:2 (1996), С. 103-130.
42
Е. С. Половинкин, М. В. Балашов. Элементы выпуклого и сильно выпуклого анализа. —
М.:Физматлит, 2007. — 440с.
43
M. V. Balashov. Weak convexity of the distance function, J. Convex Anal. 20:1 (2013), P. 93–106.
44
M. Edelstein. Farthest points of sets in uniformly convex Banach spaces // Israel J. Math. — 1966. —
V. 4, No.3. — P. 171–176.
45
М. В. Балашов, Г. Е. Иванов. Об удаленных точках множеств // Матем. заметки. 80:2. (2006)
С. 163–170.
46
Г. Е. Иванов. Наиболее удаленные точки и сильная выпуклость множеств // Матем. заметки.
87:3. (2010) С. 355–366.
35
6
Одно из важных приложений оператора метрического проектирования в оптимизации – это построение проекционных алгоритмов для решения некоторого класса экстремальных задач. В первую очередь речь
идет о поиске минимума выпуклой функции на выпуклом множестве.
Одним из классических алгоритмов здесь является метод проекции градиента (метод детально изложен в работах1,2,3,4). Последовательность генерируется по правилу
xk+1 = PA(xk − αk f 0(xk )),
x1 ∈ bd A,
αk > 0,
где через bd A будем обозначать границу множества A. При этом в
работах1,2,3,4 для выпуклого множества и сильно выпуклой функции при
условии липшицевой дифференцируемости функции при определенном
выборе параметра шага αk доказывается сходимость данного метода к
единственному решению со скоростью геометрической прогрессии.
Цели работы.
1. Показать, что оператор метрического проектирования на дополнении
к шаровой окрестности сильно выпуклого множества из гильбертова пространства на данное множество липшицев с константой строго меньше 1. Выяснить взаимосвязь между константой Липшица
метрической проекции на сильно выпуклое множество и радиусом
сильной выпуклости. Охарактеризовать часть границы множества,
метрическая проекция на которую липшицева с константой Липшица строго меньше 1.
2. Показать, что функция антирасстояния до сильно выпуклого множества из гильбертова пространства слабо вогнута на некотором
подмножестве. Выяснить взаимосвязь между константой слабой вогнутости функции антирасстояния и радиусом сильной выпуклости
множества.
3. Доказать сходимость метода проекции градиента для выпуклой (в общем случае, не обязательно сильно выпуклой) функции и сильно
выпуклого множества. Получить оценки скорости сходимости.
7
Получить оценку константы Липшица метрической проекции на
внешнюю многогранную аппроксимацию сильно выпуклого множества в Rn.
Методы исследования. В работе используются результаты выпуклого и сильно выпуклого анализа.
Научная новизна. Все результаты работы являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты могут применяться в дальнейших исследованиях в области выпуклого и сильно выпуклого анализа, в оптимизации и теории приближений. В работе получены новые критерии сильной
выпуклости множества в гильбертовом пространстве связанные с условием Липшица с константой строго меньше 1 оператора метрического
проектирования и слабой вогнутостью функции антирасстояния. Также
получены новые результаты связанные с оценкой скорости сходимости
метода проекции градиента для выпуклой функции, а также сильно выпуклого множества. Работа поддержана грантами РФФИ 13-01-00295-а и
10-01-00139-а.
Апробация работы. Результаты, изложенные в диссертации, в разное время докладывались и обсуждались на
• 54-й научной конференции МФТИ «Проблемы фундаментальных
и прикладных естественных и технических наук в современном
информационном сообществе» Москва–Долгопрудный–Жуковский,
2011;
• 16-й международной Саратовской зимней школе «Современные проблемы теории функций и их приложения», Саратов, 2012;
• Научных семинарах кафедры высшей математики МФТИ, Долгопрудный, 2011 – 2014;
• Научных семинарах «Негладкий анализ» под руководством
Г. Е. Иванова, Долгопрудный, 2011 – 2014;
• Научном семинаре «Теория автоматического управления и оптимизация» лаборатории 7 ИПУ РАН, Москва, 2012;
8
• IV International Conference on Optimization Methods and Applications
«Optimization and Applications (OPTIMA-2013)» Petrovac, 2013;
• 17-й международной Саратовской зимней школе «Современные проблемы теории функций и их приложения», Саратов, 2014.
Публикации. Основные результаты опубликованы в семи работах,
список которых приведен в конце автореферата. Работы [2,4,7] входят в
список изданий, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения,
двух глав, заключения и списка литературы. Общий объем диссертации
составляет 89 страниц. Список литературы содержит 82 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Нумерация определений, предложений, теорем, следствий в автореферате совпадает с нумерацией определений, предложений, теорем, следствий соответственно в диссертационной работе.
Во введении дается краткий обзор публикаций посвященных функции расстояния и метрической проекции, а также методам оптимизации,
и в частности, методу проекции градиента, излагается краткое содержание диссертации, перечисляются основные результаты работы.
В части 1 первой главы даются определения связанные с понятиями метрической проекции на множество и функцией расстояния и
антирасстояния. Также приводятся результаты, которые будут использоваться в дальнейшем в первой главе.
Все результаты первой главы получены для вещественнозначного
гильбертова пространства H. Через hp, xi будем обозначать скалярное
произведение векторов p, x ∈ H. Для множества A ⊂ H через bd A
будем обозначать границу данного множества. Замкнутый шар радиуса R ≥ 0 с центром в точке x ∈ H будем обозначать через BR (x) =
{y ∈ H : ky − xk ≤ R}. Диаметр множества A определяется следующим образом diam A = sup kx − yk. Нормальным конусом к выx,y∈A
пуклому замкнутому
множеству A в точке a ∈ A называется множество N (A; a) = p ∈ H : hp, ai ≥ suphp, xi . Напомним, что для мноx∈A
9
жества A выпуклой оболочкой множества co A называется пересечение
всех выпуклых множеств, содержащих A. Расстояние от точки x ∈ H
до множества A задается формулой %A(x) = inf kx − ak. Метричеa∈A
ской проекцией точки x ∈ H на множество A ⊂ H называется множество PA(x) = {a ∈ A : kx − ak = %A(x)}. Для множества A ∈ H
определим открытую %-окрестность множества A следующим образом
UA(%) = {x ∈ H : %A(x) < %}.
Одним из важных понятий, с которым связаны основные результаты
диссертации, является понятие сильно выпуклого множества.
Определение 1.1.5 [Определение 4.3.142] Непустое множество A ⊂
H называется сильно выпуклым множеством с радиусом R, если оно
может быть представлено в виде пересечения замкнутых шаров радиуса
T
R > 0, то есть A =
BR (x) для некоторого множества X ⊂ H.
x∈X
В части 2 первой главы упоминается результат М. В. Балашова.
Предложение 1.2.147 Пусть A ⊂ H замкнутое выпуклое ограниченное множество, % > 0, C ∈ (0, 1). Пусть выполнено следующее условие:
для любой пары точек x0, x1 ∈ H \ UA(%), где {ai} = PA(xi), i ∈ {0, 1}
верно
ka0 − a1k ≤ C · kx0 − x1k.
C%
.
Тогда A является сильно выпуклым множеством с радиусом R = 1−C
В связи с этим результатом возникает вопрос: как устроен модуль
равномерной непрерывности оператора метрического проектирования на
сильно выпуклое с радиусом R > 0 подмножество гильбертова пространства? Ответ на этот вопрос дает следующая теорема.
Теорема 1.2.147 Пусть множество A ⊂ H является сильно выпуклым множеством с радиусом R. Тогда для любых точек x0, x1 ∈ H\A
выполнено неравенство
ka0 − a1k ≤ p
R
(R + %0)(R + %1)
p
· kx0 − x1k2 − (%0 − %1)2,
где {ai} = PA(xi), %i = kxi − aik, i ∈ {0, 1}.
47
M. V. Balashov, M. O. Golubev. About the Lipschitz property of the metric projection in the Hilbert
space, J. Math. Anal. Appl. 394:2 (2012), P. 545–551.
10
Из предложения 1.2.1 и теоремы 1.2.1 вытекает следующее утверждение.
Следствие 1.2.147 Пусть непустое множество A ⊂ H выпукло и
замкнуто. Тогда следующие условия эквивалентны:
1) A сильно выпуклое множество с радиусом R > 0,
2) ∀% > 0, ∀x0, x1 ∈ H \ UA(%), где {ai} = PA(xi), i ∈ {0, 1}, выполнено
R
· kx0 − x1k.
ka0 − a1k ≤
(R + %)
В теореме 1.2.1 мы требовали сильной выпуклости множества, однако
нередка ситуация, когда часть границы множества устроена как часть
границы некоторого сильно выпуклого множества, а само множество при
этом не является сильно выпуклым и может быть даже неограниченным,
например, надграфик функции f : R → R

√
1− 3

x ≤ − 12 ;

−x +
2 ,
√
f (x) = 1 − 1 − x2, x ∈ (− 12 , 12 );
√


x + 1− 3 ,
x ≥ 1.
2
2
Тогда возникают определенные трудности в переносе результатов для
сильно выпуклых множеств на этот случай.
Пусть S ⊂ bd A. Определим следущее множество
!
[
.
Φ = Φ(A, S, %) =
x + N (A; x)
\ UA(%).
(1)
x∈S
Определение 1.2.148 Пусть E – банахово пространство. A ⊂ E замкнутое выпуклое множество. Модулем выпуклости называется функция δA : [0, diamA) → [0, +∞) определяемая формулой
n
x + x o
0
1
δA(t) = sup δ ≥ 0 | Bδ
⊂ A, ∀x0, x1 ∈ A : kx0 − x1k = t .
2
48
Б. Т. Поляк. Теоремы существования и сходимость минимизирующих последовательностей в задачах на экстремум при наличии ограничений // ДАН СССР. — 1966. — Т. 166, В. 2. — С. 287-290.
11
Отметим, что модуль выпуклости замкнутого выпуклого множества с
непустой внутренностью удовлетворяет условию δA(t) ≤ Ct2 для некоторого C > 0 [Следствие 2.349].
Для части границы множества S ⊂ bd A мы рассмотрим аналог модуля выпуклости
n
x + x o
.
0
1
δS (t) = sup δ > 0 | Bδ
⊂ A, ∀x0, x1 ∈ S : kx0 − x1k = t .
2
Теорема 1.2.2 Пусть A ⊂ H замкнутое выпуклое множество,
S ⊂ bd A, а множество Φ задано формулой (1). Пусть функция δS (t)
удовлетворяет условию δS (t) ≥ Ctp, где C > 0, p ≥ 2.
Тогда ∀ε > 0 ∃δ > 0 ∀x0, x1 ∈ Φ : kx0 − x1k < δ, {a0} = PA(x0),
{a1} = PA(x1), kx0 − a0k ≥ %, kx1 − a1k ≥ %, выполнена оценка
8C%
− ε ka0 − a1kp+
1−p
1−2
16C 2%2
2p−2
+
−
ε
ka
−
a
k
.
0
1
(1 − 21−p)2
kx0 − x1k2 ≥ ka0 − a1k2 +
Отметим, что теорема 1.2.2 является в некотором смысле локальным
аналогом теоремы 1.2.1. В частности, если множество A сильно выпукло с
1
радиусом R = 8C
, то теорема 1.2.2 дает ту же оценку, что и теорема 1.2.1.
При p = 2 на константу Липшица метрической проекции получена оценка
аналогичная оценке в пункте 2 следствия 1.2.1.
Следствие 1.2.2 Пусть выполнены условия теоремы 1.2.2, p = 2.
Тогда для любых точек x0, x1 ∈ Φ таких, что [x0, x1] ⊂ Φ выполнено
неравенство
ka0 − a1k ≤
1
kx0 − x1k,
1 + 8C%
где {ai} = PA(xi), i ∈ {0, 1}.
49
M. V. Balashov, D. Repovs̃. Uniform convexity and the splitting problem for selections, J. Math. Anal.
Appl. 360:1 (2009), P. 307–316.
12
Теорема 1.2.3 Пусть A ⊂ H выпуклое замкнутое множество.
Пусть S ⊂ bd A, а множество Φ задано формулой (1). Предположим,
что существует число C ∈ (0; 1), такое что для любых x0, x1 ∈ Φ верна
следующая формула:
ka0 − a1k ≤ Ckx0 − x1k,
{ai} = PA(xi), i ∈ {0, 1}.
(2)
C%
Пусть a ∈ S, и R = 1−C
.
T
Тогда для всех ε ∈ (0, R) со свойством Bε(a) bd A ⊂ S множество
T
A Bε(a) является сильно выпуклым с радиусом R.
Теорема 1.2.3 обобщает предложение 1.2.1 на более широкий класс
множеств.
В части 3 первой главы немного уточняется результат о сильной
выпуклости (при определенных условиях) функции расстояния [Теорема
4.950].
Рассматривается функция антирасстояния.
Определение 1.1.844,38 Пусть A ⊂ H выпуклое замкнутое ограниченное множество. Тогда функция fA : H → [0, +∞),
fA(x) = sup kx − ak
a∈A
называется антирасстоянием от точки x до множества A.
Основным результатом 3 части является следующая теорема.
Теорема 1.3.351 Пусть A ⊂ H сильно выпуклое множество с радиусом R. Пусть r > R. Тогда функция
антирасстояния fA(x) слабо
вогнута на множестве H \ Br (0) + A с константой
C=
1
.
r−R
Также упоминается результат М. В. Балашова.
50
А. С. Дудова. Характеризация устойчивости решения задач о внешней равномерной оценке выпуклого компакта шаром. Диссертация на соискание ученой степени кандидата физикоматематических наук. Саратов. 2006.
51
M. V. Balashov, M. O. Golubev. Weak concavity of the antidistance function // J. Convex Anal. 2014.
– N4. P. 951–964
13
Предложение 1.3.351 Пусть A ⊂ H замкнутое выпуклое ограниченное множество и r > 0. Предположим, что функция антирасстояния
fA слабо вогнута на множестве H \ Br (0) + A с константой C > 0.
Тогда множество A сильно выпуклое множество радиуса r − C1 .
Из теоремы 1.3.3 и предложения 1.3.3 вытекает следующее утверждение.
Следствие 1.3.251 Пусть A ⊂ H замкнутое выпуклое ограниченное
множество и R > 0. Тогда следующие условия эквивалентны:
1) A сильно выпуклое множество с радиусом R
2) Для всех r > R функция антирасстояния fA слабо вогнута на
1
.
множестве H \ Br (0) + A с константой C = r−R
Оценки 1) и 2) следствия 1.3.2 точны в том смысле, что если R – наименьший радиус сильной выпуклости множества A, то C – наименьшая
константа слабой вогнутости функции антирасстояния fA, и наоборот,
если C – наименьшая константа слабой вогнутости функции антирасстояния fA, то R – наименьший радиус сильной выпуклости множества
A.
В части 1 второй главы описывается стандартный метод проекции
градиента и приводятся известные оценки скорости сходимости метода
для сильно выпуклой функции и выпуклого множества1,2,3.
В части 2 второй главы доказывается сходимость метода проекции
градиента для выпуклой функции (которая в общем случае не обязательно сильно выпуклая) и сильно выпуклого множества.
Рассмотрим задачу минимизации
f (x) → min,
x ∈ A ⊂ H.
(3)
Последовательность генерируется следующим образом:
xk+1 = PA(xk − αk f 0(xk )),
x1 ∈ bd A,
αk > 0.
(i) t = min kf 0(x)k > 0,
x∈bd A
(ii) Множество A ⊂ H сильно выпукло с радиусом R,
14
(4)
(iii) Функция f : H → R является выпуклой, дифференцируемой и градиент f 0(x) удовлетворяет условию Липшица с константой M > 0,
(iv) Решение x∗ ∈ bd A задачи min f (x) единственно,
x∈A
(v) Для всех k ∈ N существует вектор n(xk ) ∈ N (A; xk ), такой что выполняется неравенство hn(xk ), f 0(xk )i ≤ 0 (то есть xk − αk f 0(xk ) ∈
/A
для любого αk > 0).
В случае, когда условие (v) не выполняется, мы имеем дело с безусловной минимизацией и следует использовать один
из стандартных алгоритмов поиска безусловного минимума (см.
например4(Теорема 1.2., Теорема 2.1. Глава 5)).
Теорема
2.2.1 52 a) Пусть выполнены условия (i)–(v). Пусть αk =
α ∈ 0, M2 .
Тогда последовательность xk , генерируемая по правилу (4), сходится
к решению задачи (3) со скоростью геометрической прогрессии: kxk+1 −
R
x∗k ≤ qkxk − x∗k, где q = √
;
4
(R2 +α2 t2 )(R+αt)2
2
b) Пусть выполнены условия (ii)–(v). Пусть αk = α ∈ 0, M .
Тогда последовательность xk , генерируемая по правилу (4), сходится
к решению
задачи (3) и верна формула: kxk+1 − x∗k ≤ qk kxk − x∗k, где
q
2
qk = 4 R2+α2Rkf 0(x )k2 .
k
Теорема 2.2.2 52Пусть выполнены условия (i)–(iii). Пусть RM
t < 1.
Последовательность xk генерируется по правилу (4) с αk = α > 0
для всех k.
Тогда:
2R 2
1) при выборе α ∈ t , M последовательность xk сходится к решению задачи (3) со скоростью геометрической прогрессии: kxk+1 − x∗k ≤
R
qkxk − x∗k, где q = αt−R
;
2) при выборе α > M2 последовательность xk сходится к решению
задачи (3) со скоростью геометрической прогрессии: kxk+1 − x∗k ≤
−1)
qkxk − x∗k, где q = R(αM
αt−R .
52
М. О. Голубев. Метод проекции градиента для сильно выпуклого множества // Изв. Сарат. ун-та.
Нов. сер. Сер. Математика. Механика. Информатика. 13:1(2) (2013), С. 33–38.
15
В части 2 второй главы при помощи результата теоремы 1.2.1 получена оценка скорости сходимости метода проекции градиента для сильно
выпуклой функции и сильно выпуклого множества. Отметим, что сильная выпуклость множества обеспечивает (при прочих равных условиях)
более высокую скорость сходимости.
Часть 3 второй главы посвящена многогранным аппроксимациям
сильно выпуклых множеств в Rn. Получена оценка на константу Липшица оператора метрического проектирования на внешнюю многогранную
аппроксимацию сильно выпуклого множества. Показано, что при некотором наборе параметров, и в первую очередь достаточно малой мелкости
сетки, константа Липшица может быть меньше 1.
Теорема 2.4.1 Пусть задана сетка G мелкости ∆ ∈ 0, 12 (где
мелкость сетки понимается в смысле определения 2.4.142). Пусть множество A ⊂ Rn является сильно выпуклым множеством с радиусом
R > 0. Множество
b = {x ∈ Rn| (p, x) ≤ s(p, A), ∀p ∈ G}
A
выпуклая внешняя многогранная аппроксимация множества A. Пусть
заданы числа l > 0, % > 0. Пусть x0, x1 ∈ Rn \ UA(%), kx0 − x1k ≥ l.
b ∪ {x0, x1}} и точки {abi} = P b(xi),
Определим множество B = co{A
A
i ∈ {0, 1}. Тогда верно следующее неравенство:
1
√
R
2R · diamB∆ + R∆2
+
kx0 − x1k.
kab0 − ab1k ≤ 4
l R+%
(5)
В заключении сформулированы основные результаты, полученные
в диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Доказано, что оператор метрического проецирования на сильно выпуклое множество из гильбертова пространства липшицев с константой строго меньше 1 на дополнении к шаровой окрестности данного множества. Получена формула, показывающая взаимосвязь между радиусом окрестности, радиусом сильной выпуклости множества
16
и константой Липшица метрической проекции. Доказано, что если
метрическая проекция на некоторое подмножество границы выпуклого множества липшицева с константой строго меньше 1, то при
некоторых условиях пересечение множества с шаром с центром на
данном подмножестве границы является сильно выпуклым множеством. Получена оценка радиуса сильной выпуклости.
2. Доказано, что функция антирасстояния до сильно выпуклого множества из гильбертова пространства слабо вогнута на некотором подмножестве (антиокрестности). Получена взаимосвязь между параметром, задающим антиокрестность, константой слабой вогнутости
функции антирасстояния и радиусом сильной выпуклости множества.
3. Показано, что для выпуклой (в общем случае, не обязательно сильно
выпуклой) функции и сильно выпуклого множества при некоторых
достаточно общих условиях метод проекции градиента сходится со
скоростью геометрической прогрессии. Получены оценки скорости
сходимости. Также получены улучшенные оценки скорости сходимости метода проекции градиента для сильно выпуклой функции и
сильно выпуклого множества.
Получена оценка константы Липшица метрической проекции на
внешнюю многогранную аппроксимацию сильно выпуклого множества в Rn. Показано, что при определенных условиях (в первую очередь, достаточно малой мелкости сетки и расстоянии между проецируемыми точками того же порядка, что и мелкость сетки) константа
Липшица метрической проекции строго меньше 1.
17
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. М. В. Балашов, М. О. Голубев. Об условии Липшица для метрической проекции в гильбертовом пространстве. // Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном сообществе. – Т.1: Труды 54-й научной
конференции МФТИ. /Моск. физ. – техн. ин-т. – М. – Долгопрудный, 2011. – С . 34–34.
2. M. V. Balashov, M. O. Golubev. About the Lipschitz property of the
metric projection in the Hilbert space // J. Math. Anal. Appl. – 2012.
– 394:2 – P . 545–551.
3. М. О. Голубев. Метрическая проекция в гильбертовом пространстве
и сильная выпуклость. // материалы 16-й международной Саратовской зимней школы «Современные проблемы теории функций и их
приложения» – Саратов: ООО Издательство «Научная книга», 2012.
– С . 55–56.
4. М. О. Голубев. Метод проекции градиента для сильно выпуклого
множества. // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. – 2013. – 13:1(2) – С . 33–38.
5. M. O. Golubev. Local strong convexity in the Hilbert space. //
proceedings of IV International Conference on Optimization Methods
and Applications «Optimization and applications» (OPTIMA-2013). –
Petrovac, 2013. – P . 68–69.
6. М. О. Голубев. Связь сильно выпуклых множеств с сильной выпуклостью функции расстояния и слабой вогнутостью функции антирасстояния. // материалы 17-й международной Саратовской зимней
школы «Современные проблемы теории функций и их приложения»
– Саратов: ООО Издательство «Научная книга», 2014. – С . 76–78.
7. M. V. Balashov, M. O.
antidistance function. //
Golubev. Weak concavity of the
J. Convex Anal. – 2014. –
18
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.
19
Голубев Максим Олегович
МЕТРИЧЕСКАЯ ПРОЕКЦИЯ И ФУНКЦИИ РАССТОЯНИЯ И
АНТИРАССТОЯНИЯ ДЛЯ СИЛЬНО ВЫПУКЛЫХ МНОЖЕСТВ
АВТОРЕФЕРАТ
Подписано в печать . .2014. Формат 60 × 84 1/16 . Усл. печ. л. 1,0.
Тираж 100 экз. Заказ №
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования «Московский физико-технический
институт (государственный университет)»
Отдел оперативной полиграфии «Физтех-полиграф»
141700, Московская обл., г. Долгопрудный, Институтский пер., 9
Документ
Категория
Без категории
Просмотров
5
Размер файла
430 Кб
Теги
проекции, сильні, множества, функции, расстоянии, антирасстояния, выпуклых, метрические
1/--страниц
Пожаловаться на содержимое документа