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

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

005042443

Мещерякова Елена Александровна

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

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

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

1 0 уд з

Саратов-2012

005042443

Работа выполнена на кафедре математической экономики механико-математического факультета Саратовского государственного университета им. Н.Г. Чернышевского.

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

доктор физико-математических наук, профессор Дудов Сергей Иванович

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

профессор Розен Виктор Владимирович

кандидат физико-математических наук, доцент Акимова Светлана Александровна

Ведущая организация Волгоградский

государственный

университет

Защита состоится 24 мая 2012 г. в 17 час 00 мин на заседании диссертационного совета ДМ 212.243.15 при Саратовском государственном университете им. Н.Г.Чернышевского по адресу: 410012, г.Саратов, ул.Астраханская, 83, СГУ, механико-математический факультет.

С диссертацией можно ознакомиться в библиотеке в Научной библиотеке Саратовского государственного университета.

Автореферат разослан « Л-3> » апреля 2012г.

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

диссертационного совета к.ф.-м.н., доцент

В.В. Корнев

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

Актуальность темы.

Интерес математиков к оценкам и приближению выпуклого компакта шаром возник очень давно (см., например, монографии Бляшке [1], Т.Боннезена и В.Фенхеля [2], Л.Ф.Тота [27], а также библиографии в них) и возобновлялся по мере появления в математике новых средств исследования, позволяющих рассматривать как новые задачи, так и старые задачи, но на более высоком уровне. Ныне это направление поддерживается в рамках негладкого анализа и недифференцируемой оптимизации, основы которых заложены в трудах Р.Т.Рокафеллара, Б.Н.Пшеничного, В.Ф.Демьянова, А.М.Рубинова, Ф.Кларка, Ж.-П.Обена, И.Экланда, Н.З.Шора, Б.Т.Поляка, М.С.Никольского, Е.С.Половинкина, В.М.Миклюкова ([26], [23]-[24], [5]-[7], [14], [19]-[20], [30], [28], [21]-[22], [31]) и других отечественных и зарубежных математиков. Именно негладкий анализ дает эффективные математические инструменты для успешного исследования задач по оценкам и приближению сложных множеств множествами простой структуры.

Задачи по оценке множеств находят обширные приложения в естествознании, в том числе и в самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (напр., работы Н.З.Шора [30], Ф.Л.Черноусько [29], А.Б.Куржанского и др.). Можно указать на работы по внешним и внутренним оценкам заданных множеств ориентированными параллелепипедами и их приложениями. Много работ посвящено внутренним и внешним полиэдральным аппроксимациям выпуклых множеств.

Наряду с эллипсоидом и многогранником к числу наиболее простых множеств, которыми осуществляется оценка или приближение выпуклого компакта относится шар любой нормы. Задача о внешней оценке компакта шаром произвольной нормы, которая заключается в построении шара используемой нормы с наименьшим радиусом, содержащим оцениваемый компакт, рассматривалась Б.Н.Пшеничным в [23]. Понимаемая по аналогии задача о внутренней оценке заданного выпуклого тела рассматривалась С.И.Дуловым в [10].

Задача о наилучшем приближении в метрике Хаусдорфа выпуклого компакта евклидовым шаром была поставлена и изучалась в работе М.С.Никольского и Д.Б.Силина [18]. Эта же задача о приближении шаром произвольной нормы исследовалась С.И.Дуловым и И.В.Златорунской в [9].

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

Пусть D - заданное выпуклое тело (то есть выпуклый компакт с непустой внутренностью) из конечномерного действительного пространства Кр, а функция п{х) удовлетворяет на Ер аксиомам нормы. Функция, определяемая как

Rix) — maxn(x — у),

y€D

выражает радиус наименьшего шара в норме п(-) с центром в точке х £ Кр, содержащего тело D. Другими словами, это радиус описанного шара с центром в точке х. Для х € D и множества П = Mp\D функция

р{х) = min n(x - у),

yen

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

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

виде

, ч ЯСО

xpix) = —--г min. (1)

р{Х) x£D

Это основной объект исследования диссертации. Из непрерывности конечных функций Rix) и р(рс) легко следует, что решение задачи (1) существует. Далее понимаем под

Г = min гр(х), Сф = {уе D: ^(у) = П

XED г

Величину 1р* договоримся называть показателем асферичности тела D, а С^ — множеством центров асферичности.

Показатель асферичности iр* нередко используется (обычно для случая, когда п(х) — евклидова норма) при описании свойств выпуклого тела и построении методов по приближению (см., напр., [17]). Очевидно хр* = 1 тогда и только тогда, когда тело D является шаром используемой нормы п(-). Поэтому величина гр* — 1 может рассматриваться как некоторая мера отличия тела D от шара.

Несмотря на естественность постановки задачи, работ по ее исследованию найти не удалось. Близкой к ней, по постановке, является давно известная (см. [2]) задача об отыскании центра шарового слоя наименьшей толщины, содержащего границу выпуклого тела D

Ф(х) = Rix) - pQx) —> min. (2)

x£D

В качестве близкой, по смыслу, к задаче (1) можно назвать также задачу о наилучшем приближении выпуклого компакта D шаром в метрике Хаусдорфа:

ср(,х, г) = hiD, Вп(х, г)) —> jmn^. (3)

Здесь Bnix, г) = (у Е Кр:п(х — у) < г] - шар в норме п(-) с центром в точке х и радиусом г, а

h(A,B) = max jsup inf n(a — b),supinfn(a - b)[ -l-аел bee beß a€A )

- расстояние между множествами А и В в метрике Хаусдорфа, индуцированное используемой нормой п(•)•

Задача (2) для случая евклидовой нормы рассматривалась в [2] (см. также библиографию в [2]), а задача (3) в [18]. Для случая произвольной нормы свойства решения задач (2) - (3) исследовались в [8], [9], [12]. В работе [9], в частности, приводятся условия на норму п(-) и тело D, при которых задачи (2) и (3) являются эквивалентными. Установлено, что в общем случае справедливо соотношение

Сф = CtpCiD.

Здесь Сф = {у 6 D: Ф(у) = min^gD Ф(лг)} - множество центров шаровых слоев наименьшей толщины, содержащих границу тела D. А Су = {у 6 Мр: Зг > 0, <р(у,f) = ттхеЕрг>0 <р(у,г)} - множество центров шаров наилучшего приближения в задаче (3).

Отметим, что если величина гр* — 1 выражает относительную меру отличия тела D от шара, то оптимальные значения целевых функций задач (2) и (3) выражают абсолютную меру, то есть зависящую от размера тела D. Поэтому естественно ожидать, что решения задач (2) и (3) могут не совпадать с решениями задачи (1), что и показывают примеры.

Цель работы заключалась в следующем:

• изучить свойства целевой функции гр{х) задачи (1),

• получить необходимые и достаточные условия ее решения,

• получить условия единственности ее решения,

• дать сравнение задачи (1) с задачами (2) и (3), а также задачами о внешней и внутренней оценке тела D с помощью задачи

(р(х,г) —* min (4)

^ лгеКР V '

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

• разработать и обосновать метод приближенного решения задачи (1).

Методика исследования.

Известно, что функция R{x) выпукла на Ер (см., напр., [23]), а функция р(х) является вогнутой на D ([11]). Поэтому целевая функция задачи (2) также выпукла на D. В [9] показано, что целевая функция <р(х,г) задачи (3) является выпуклой по совокупности переменных (х, г) £ Rp х Таким образом задачи (2) - (3) являются задачами выпуклого программирования. Однако, как показано в диссертации, целевая функция

i/>(x) задачи (1) может быть не выпуклой и не вогнутой. При исследовании в основном применялись методы выпуклого анализа, теории минимаксных задач и элементы многозначного анализа.

Научная новизна.

Результаты диссертации являются новыми и состоят в следующем:

1. Установлены свойства целевой функции i/jQx) задачи (1): ее квазивыпуклость на D и субдифференцируемость (в смысле определения В.Ф. Демьянова - A.M. Рубинова [7]).

2. Получено необходимое и достаточное условие ее решения.

3. Получены условия единственности ее решения.

4. Дано параметрическое сравнение задачи (1) с задачами (2) и (3), а так же с задачами о внешней и внутренней оценке тела D шаром используемой нормы, с помощью задачи (4), где значение радиуса г используется в качестве некоторого параметра для сравнения.

5. Разработан и обоснован метод приближенного решения.

Теоретическое значение и практическая ценность.

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

Апробация работы.

Основные результаты диссертационной работы докладывались на семинаре по негладкому анализу и математической экономике кафедры математической экономики Саратовского государственного университета (руководитель — проф. Дудов С.И.) (2006-2012г.); на научных конференциях сотрудников механико-математического факультета Саратовского государственного университета (2006-2012г.); на 14-ой, 15-ой и 16-ой Саратовских зимних школах «Современные проблемы теории функций и их приложения» (Саратов, 2008г., 2010г., 2012г.); на 9-ой, 10-ой международной Казанской летней научной школе-конференции «Теория функций, её приложения и смежные вопросы» (Казань, 2009г., 2011г.); на Воронежской зимней математической школе «Современные методы теории функций и смежные вопросы» (Воронеж, 2009г.); на Суздальской международной конференции по математической теории управления и механике (Суздаль, 2009г.); на объединенном научном семинаре механико-математического

факультета и факультета КНИТ СГУ по дискретной математике и математической кибернетике (март 2012г.).

Публикации.

Результаты исследований опубликованы в работах [32] - [42]. Работы [39], [41] входят в список изданий, рекомендуемых ВАК РФ при защите кандидатских диссертаций.

Структура диссертации.

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

Содержание работы

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

Первая глава диссертации состоит из 5 параграфов и посвящена характеризации решения задачи (1).

В §1 дается математическая формализация задачи и ставится цель исследования.

В §2 приводятся вспомогательные сведения необходимые для дальнейшего исследования. Они касаются свойств функций /?(х), р(х), решений задач о внешней и внутренней оценке выпуклого тела D шаром нормы п(-), а также решений задач (2) и (3).

В §3 изучаются свойства целевой функции 4>(х) задачи (1). Эти свойства отражаются следующими доказанными фактами.

Теорема 3.1. Функция iр(х) является квазивыпуклой на D, а если D — строго выпуклый компакт, то строго квазивыпуклой.

Теорема 3.2. Функция ф(х) является субдифференцируемой (в смысле определения В.Ф. Демьянова - A.M. Рубинова [7]) в любой точке х0 £ intD, причем ее субдифференциалом в этой точке является выпуклый компакт

дф(х0) = (р(*о)Г2[р<Л>Ж(*о) - Д(*о)0р(*о)] _ (5) где dR(xn) - субдифференциал выпуклой функции R(x), а др(х0) -супердифференциал вогнутой функции р(х) в точке х0.

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

7

В §4 на основе формулы (5) субдифференциала функции тр(х) получен критерий решения задачи (1).

Теорема 4.1. Для того, чтобы точка х* S intD, была точкой минимума функции тр(х) на выпуклом теле D, необходимо и достаточно, чтобы

0р е р(ж*)ЗЯ(**) - Я(**)3р(**). (6)

Как показывают примеры, решение задачи (1) может быть неединственным. В §5 приводятся условия, выполнение которых обеспечивают единственность решения.

Теорема 5.1. Если выполняется хотя бы одно из условий:

1) D — строго выпуклое тело,

2) выпуклое тело D обладает центральной симметрией и при этом

либо а) п(х) - строго квазивыпуклая норма, либо б) размерность пространства р = 2, то задача (1) имеет единственное решение.

Вторая глава диссертации состоит из §§6 - 9, в ней изучается взаимосвязь задачи (1) с другими задачами.

В работе [8] установлено, что решение задачи (2) и (3), а также решение задачи о внешней оценке

R(x) —> min (7)

хеКР V '

и задачи о внутренней оценке

р(х) —» max (8)

X€D

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

Целью главы является ответ на вопрос: может ли задача (4) выражать также и решения задачи (1) при каких либо значениях радиуса г и в случае положительного ответа уточнить соответствующий диапазон значений этого радиуса.

В методическом плане проводимое в этой главе исследование опирается на работу С.И. Дудова [8], где выявлена параметрическая взаимосвязь задач (2), (3), (7) и (8) с помощью задачи (4), в которой значение радиуса г используется в качестве параметра.

В §6 приводятся вспомогательные сведения из работы [8] о параметрической взаимосвязи задачи (4) с задачами (2) — (3) и (7) - (8). Введем обозначения

р(х) = min п(х - у), PO) = р(х) - pix), (9)

y€D

R* = min ДО), p* = тахрО), (10)

X6K" ^ xeD Г V '

СЛг) =

CR = {у е RP: Я (у) = R*l Ср = {у Е D\р(у) = р'1 (11) R± = max (min) R(pc), P± = шах (min) P(x), (12)

X£Cp X€Cr

г„± = (й*-Р+)/2, rP± = (R±+p*)/2, (13)

C„(r) = fy 6 ШР: (p(y,r) = min (p{x,r)\ (14)

ЛГбШЦР J

Из (9) - (13) вытекает следующая последовательность расположения значений Гд* и Тр* на числовой оси

О <rR~ < rR+ < rP~ < гР+ < оо. (15)

В [8] доказано, что, если СпГ\Ср = 0, то решения Сф(г) задачи (4) выражают решения задач (7) и (8) в соответствии с формулой

Cr , если г £ [0,rß~],

CRV\{x е Мр: Р{х) <R*~ 2г}, если г G [rR~,rR+], СрГ\{х е W:R(x) < 2г - р'}, если г б [гР~,гР+], (16>

, еслиг>гР+,

а кроме того существует отрезок Г(р+] такой, что решения задачи (4) выражают решения задачи (3) в виде

С„ = и С„(г), (17)

relr<p~'r<p ]

и при этом

[г„- г„+] С [rR+,rp-]. (18)

Отметим, что если СдПСр Ф 0, то rR+ - rP~ - (Я* + р*)/2 и при этом С„((Я* + р*)/2) = = С,, = СйПСр. В §7 изучаются свойства решения Сф(г) задачи (4). Самые важные их них относятся к функции

Лемма 7.4. Функция fP(r) непрерывна на К+, не возрастает на М+, выпукла при г > rR+, строго убывает на отрезке [гд+, гР~].

В §8 доказана теорема с о параметрическом вложении задачи об асферичности (1) в шкалу (15), к которой формулами (16) - (17) привязаны решения и других сравниваемых здесь задач.

Теорема 8.1. Пусть СнГ\Ср — 0. Тогда существует отрезок [Гф~,гф+] такой, что

V СФ = Urefr^-.r,/]^^).

2) hr-VIс h+'rp~l (19)

Таким образом, соотношения (19) и (16) - (18) говорят о том, что решения задачи (1) об асферичности, выражаемые решениями задачи (4) по шкале (15), лежат «между» решениями задачи (3) и решениями задачи (8).

В §9 для двухмерного случая с евклидовой нормой доказано, что у задачи (1) обязательно есть хотя бы одно общее решение с задачей (3) (теорема 9.1). Для трехмерного случая с евклидовой нормой приводится пример, когда у задач (1) и (3) нет общих решений.

Главная цель третьей главы - разработка метода приближенного решения задачи (1).

В §10 предлагается подход к получению приближенного решения, в виде построения итерационного процесса, на каждом шаге которого решается задача выпуклого программирования. Его суть заключается в следующем. Если уже построена точка очередного приближения хк 6 D и ак = гр(хк), то в качестве точки хк+1 берется решение задачи

грк(х) = fl(x) - акр(х) —» min, (20)

xeD

Важным обстоятельством является то, что целевая функция ipk(.x) вспомогательной задачи (20) является выпуклой на D. Поэтому для ее решения можно использовать широкий спектр методов выпуклого программирования. В качестве обоснования сходимости процесса доказана

Теорема 10.1. Любая предельная точка последовательности ixk}k=о,1,2,... является центром асферичности выпуклого тела D.

Кроме того, показано что в случае, когда выпуклое тело D и шар используемой нормы являются многогранниками, то задача (20) сводится к задаче линейного программирования (теорема 10.2).

В §11 исследуется вопрос об устойчивости решения задачи (1) к погрешности задания оцениваемого на асферичность выпуклого тела D. Доказано, что задача обладает устойчивостью оптимального значения целевой функции (теорема 11.1). Также рассматривалось многозначное отображение С^(-), сопоставляющее элементам пространства выпуклых тел Kv(JRP) соответствующие множества центров асферичности. То есть -

множество центров асферичности для D € Kv(MP~).

Доказано, что это отображение обладает полунепрерывностью сверху (теорема 11.2). Из этого факта вытекает, что решая некоторую последовательность задач об асферичности для выпуклых тел D£., где h{p, D£.) < £;, £¡10 при i—>00, мы можем получить приближенное значение хотя бы одного из центров асферичности для D.

Кроме того приведен пример, когда полунепрерывность снизу отображения Сф(-) отсутствует. Это значит, что имеет место

Л^ОО.СДЛ*,))-* 0 при М 0, i —» оо

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

В §12 обсуждаются вопросы практического получения субградиентов функции /?(*) и суперградиентов функции р(х) в конкретной

10

точке с целью использования при построении численного метода решения задачи (1).

В §13 дается принципиальная схема построения последовательности приближений в итерационном методе решения задачи (1).

Пусть на к - ом шаге получена четверка объектов {хк,ак,Мк,Тк}, удовлетворяющая условиям:

- точка хк е intD, ак = min{afc_1(T/)(xfc)},

- многогранник Мк, Тк построены так, что Вп(Ор, 1) с Мк, D с Тк. Приведем описание вычислений на к + 1-ом шаге метода для

получения четверки объектов {хк+1,ак+1,Мк+1,Тк+1} с аналогичными свойствами:

1) Находим любую точку z 6 QR(xk) и в точке (z - xk)/n(z - хк) строим опорную гиперплоскость к шару ßn(Op, l):

7Tß(z) = \х е RP-. (v, х - Хк\) = о]. I nKz — х:к) )

Здесь v - нормаль к гиперплоскости nB{z), найденная в процессе построения. Будем считать для определенности

Вп(0р, 1) С 7TB+(z) = \xEmP:(v,x- (-гГ Хк\) > о).

n(z - хк) )

Теперь берем в качестве многогранника Wfc+i = МкПтгв+(£),

а в качестве Rk(x) функцию

Rk(x) = maxnMk+i (х - у),

где пМк+1(х) - функция Минковского множества Мк+1, то есть

nMfc+1(*) = in/{а > 0: ^ е Мк+1).

2) Находим любую точку у 6 Qp(xk+1) и полагаем значение параметра m := 0, Tkm ■= Тк.

3) В точке у строим опорную гиперплоскость к выпуклому компакту

D:

nD{y) = {х е lRp:(w,x - у) = 0}. Здесь w - нормаль к гиперплоскости nD (у), найденная в процессе построения. Считаем для определенности, что

D с 7Го + (у) = {х 6 RP; (w,x- у) > 0}. Теперь берем в качестве многогранника 1 = Tkimf)nD + (y'), и полагаем m ~ m + 1, а также Qfc m = ШР/Ткт,

Pk.mOc) = min п(х- у).

У^кт

4) Решаем задачу

Rk(x) - akpkm(x) —> min .

*еткт

Пусть xKm e Tkm и

Як(*к.т) - akPk,m(xk,m) = min (дк(х) - akpkjn(x)).

*eTk.m 4 7

5) Если хктп ё intD, то берем в качестве точки у пересечение отрезка \хк, хкт\ с границей выпуклого компакта D и передаем управление в пункт 3).

6) Если хкт £ intD, то полагаем

*к+1 = хк,т> Tfc+1 = ТКт, ак+1 = mm{ak,xjj(xk+1)}

и учитывая, что многогранник Мк+1 уже получен при выполнении пункта 1), считаем выполнение вычислений на к + 1-ом шаге завершенными.

Таким образом, многогранники Мк и Тк (а также Tk m во внутреннем цикле пп 3)-5)) являются внешними полиэдральными аппроксимации для ßn(Op, l) и D соответственно. Они уточняются с каждым шагом за счет построения новых опорных гиперплоскостей к Вп(Ор, l) и D. Важное обстоятельство заключается в том, что вспомогательная задача вида (21) сводится к задаче линейного программирования, что было показано ранее в §10.

В основе данного метода заложена идея, предложенная в §10. А с другой стороны он допускает сравнения с методом Келли ([6], [25]), который используется при решении задач выпуклого программирования. Однако ввиду затруднений в проведении прямой аналогии с методом Келли, в §14 дается прямое обоснование приведенного метода. Доказано (теорема 14.3), что предел любой сходящейся подпоследовательности из последовательности {хк}к=12является центром асферичности.

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

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

1. Бляшке В. Круг и шар. М.: Наука, 1967.

2. Боннезен Т., Фенхель В. Теория выпуклых тел. М.: Фазис, 2002.

3. Васильев Ф.П. Численные методы решения экстремальных задач.

М.: Наука, 1988.

4. Грюнбаум Б. Этюды по комбинаторной геометрии и теории

выпуклых тел. М.: Наука, 1971.

5. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука,

1972.

6. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. М.: Наука, 1981.

7. Демьянов В.Ф., Рубинов A.M. Основы негладкого анализа и квазидифференциальное исчисление. М.: Наука, 1990.

8. Дудов С.И. Взаимосвязь некоторых задач по оценке выпуклого компакта шаром // Матем. сборник. 2007. Т. 198, №1. с. 45-58.

9. Дудов С.И., Златорунская И.В. Равномерная оценка выпуклого компакта шаром произвольной нормы // Матем. сборник. 2000. Т. 191, №10. с. 13-38.

10. Дудов С.И. Внутренняя оценка выпуклого множества телом нормы// ЖВМ и МФ. 1996. Т. 36, №5. с. 153 - 159.

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

12. Дудов С.И. Об оценке границы выпуклого компакта шаровым слоем// Изв. Саратовского университета. 2001. Т. 1, №2, с. 64 - 75.

13. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974.

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

15. Карманов В.Г. Математическое программирование. М.: Наука, 1986.

16. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985.

17. Каменев Г.К. Скорость сходимости адаптивных методов полиэдральной аппроксимации выпуклых тел на начальном этапе // ЖВМ и МФ. 2008. Т. 48, №5. с.763-778.

18. Никольский М.С., Силин Д.Б. О наилучшем приближении выпуклого компакта элементами аддиала // Труды матем. института им. В.А.Стеклова. 1995.Т. 211, с.338-354.

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

20. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.

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

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

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

24. Пшеничный Б.Н. Необходимые условия экстремума. М.: Наука, 1982.

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

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

27. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958.

28. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. М.: Наука. 1966.

29. Черноусько Ф.Л. Оценивание фазового состояния динамических систем: Метод эллипсоидов. М.: Наука, 1988.

30. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979.

31. Миклюков В.М. Введение в негладкий анализ. Волгоград: Изд-во ВолГУ, 2008.

Список работ автора по теме диссертации

32. Мещерякова Е.А. О двух задачах по оценке выпуклого компакта шаром // Тез. докл. 14-ой Саратовской зимней школы. Саратов. Изд-во Сарат. ун-та, 2008. с. 115 - 116.

33. Мещерякова Е.А. О двух задачах по оценке выпуклого компакта шаром // Математика. Механика: Сб.науч.тр. Саратов: Изд-во Сарат. ун-та, 2008. вып. 10. С. 48-50.

34. Дудов С.И., Мещерякова Е.А. Об асферичности выпуклого компакта // Математика. Механика: Сб.науч.тр. Саратов: Изд-во Сарат. ун-та, 2009. вып. 11. С. 24-27. (Дудову С.И. принадлежит постановка задачи, основные результаты принадлежат Мещеряковой Е.А.)

35. Дудов С.И., Мещерякова Е.А. Об асферичности выпуклого компакта // Тез. докл. Междунар. конференции по математ. теории управления и механике, Суздаль. Изд-во Суздаль, ун-та, 2009. с. 55 -56.

36. Дудов С.И., Мещерякова Е.А. Критерий решения задачи об асферичности выпуклого компакта // Материалы 9-й междунар. Казанской летней научной школы-конференции. Казань: Изд-во Казанского матем. общества, 2009, с. 113 - 114.

37. Мещерякова Е.А. О приближенном решении задачи об асферичности выпуклого компакта // Тез. докл. 15-ой Саратовской зимней школы . Саратов. Изд-во Сарат. ун-та, 2010. с. 117-118.

38. Мещерякова Е.А. О приближенном решении задачи об асферичности выпуклого компакта // Материалы Воронежской зимней мат. школы, Изд.-полигр. центр Воронежского гос. университета. 2010. с. 219-220.

39. Дудов С.И., Мещерякова Е.А. О приближенном решении задачи об асферичности выпуклого компакта // Изв. Сарат. ун-та. Нов.сер. Математика. Механика. Информатика. 2010, Т. 10, №4, с.13-17.

40. Мещерякова Е.А. Характеризация устойчивости решения задачи об асферичности выпуклого компакта // Материалы 10-й междунар. Казанской летней научной школы-конференции. Казань: Изд-во Казанского матем. общества, 2011, с. 253 - 255.

41. Дудов С.И., Мещерякова Е.А. Характеризация устойчивости решения задачи об асферичности выпуклого компакта // Изв. Сарат. ун-та. Нов.сер. Математика. Механика. Информатика. 2011, Т.11, №2, с.20-26.

42. Мещерякова Е.А. Условия единственности решения задачи об асферичности выпуклого компакта // Тез. докл. 16-ой Саратовской зимней школы. Саратов. Изд-во Сарат. ун-та, 2012. с. 120.

Подписано в печать 18.04.2012 Формат 60 х 4В 1/16. Бумага офсетная. Гарнитура Times. Печать цифровая. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 115-Т

Типография Саратовского государственного университета

имени Н.Г. Чернышевского 410012 г. Саратов, ул. Большая Казачья, д.. 112а Тел.: (8452) 27-33-85

61 12-1/884

Саратовский государственный университет им. Н.Г. Чернышевского

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

Мещерякова Елена Александровна ОЦЕНКА ВЫПУКЛОГО ТЕЛА НА АСФЕРИЧНОСТЬ

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

Диссертация

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

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

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

профессор С.И. Дудов

Саратов 2012

Содержание

Введение..................................................................................................................3

Глава 1. Характеризация решения задачи......................................................16

§ 1. Постановка задачи.......................................................................................16

§2. Вспомогательные сведения, обзор близких задач....................................19

§3. Свойства целевой функции.........................................................................30

§4. Необходимые и достаточные условия решения.......................................40

§5. Условия единственности решения.............................................................44

Глава 2. Параметрическая связь с другими задачами.................................50

§6. Задача наилучшего приближения выпуклого компакта шаром фиксированного радиуса...................................................................................50

§7. Вспомогательные факты.............................................................................53

§8. Вложение задачи в параметрическую шкалу............................................58

§9. Двумерный случай с евклидовой нормой, примеры................................64

Глава 3. Метод приближенного решения........................................................70

§10.0 подходе к построению приближенного решения...............................70

§ 11. Об устойчивости решения.........................................................................74

§12. Получение субградиента целевой функции............................................82

§ 13. Схема метода...................................... ........................................................85

§14. Обоснование метода..................................................................................89

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

Введение

1. Интерес математиков к оценкам и приближению выпуклого компакта шаром возник очень давно (см., например, монографии Бляшке [1], Т.Боннезена и В.Фенхеля [2], Л.Ф.Тота [27], а также библиографии в них) и возобновлялся по мере появления в математике новых средств исследования, позволяющих рассматривать как новые задачи, так и старые задачи, но на более высоком уровне. Ныне это направление поддерживается в рамках негладкого анализа и недифференцируемой оптимизации, основы которых заложены в трудах Р.Т.Рокафеллара, Б.Н.Пшеничного, В.Ф.Демьянова, А.М.Рубинова, Ф.Кларка, Ж.-П.Обена, И.Экланда, Н.З.Шора, Б.Т.Поляка, М.С.Никольского, Е.С.Половинкина, В.М.Миклюкова ([26], [23]-[24], [5]-[7], [14], [19]-[20], [30], [28], [21]-[22], [43]) и других отечественных и зарубежных математиков. Именно негладкий анализ дает эффективные математические инструменты для успешного исследования задач по оценкам и приближению сложных множеств множествами простой структуры.

Задачи по оценке множеств находят обширные приложения в естествознании, в том числе и в самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (напр., работы Н.З.Шора [30], Ф.Л.Черноусько [29], А.Б.Куржанского [31] и др.). Можно указать на работы по внешним и внутренним оценкам заданных множеств ориентированными параллелепипедами и их приложениями. Много работ посвящено внутренним и внешним полиэдральным аппроксимациям выпуклых множеств.

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

компакт, рассматривалась Б.Н.Пшеничным в [23]. Понимаемая по аналогии задача о внутренней оценке заданного выпуклого тела рассматривалась С.И.Дудовым в [10].

Задача о наилучшем приближении в метрике Хаусдорфа выпуклого компакта евклидовым шаром была поставлена и изучалась в работе М.С.Никольского и Д.Б.Силина [18]. Эта же задача о приближении шаром произвольной нормы исследовалась С.И.Дудовым и И.В.Златорунской в [9].

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

Пусть И - заданное выпуклое тело (то есть выпуклый компакт с непустой внутренностью) из конечномерного действительного пространства Шур, а функция п(х) удовлетворяет на аксиомам нормы. Функция, определяемая как

Я(х) = та хп(х — у),

уев

выражает радиус наименьшего шара в норме п(-) с центром в точке х 6 Мр, содержащего тело Г). Другими словами, это радиус описанного шара с

центром в точке х. Для х 6 D и множества П = MP\D функция

р(х) = min п(х — у),

yen

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

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

виде

R(x)

ф(х) = , N -» min. (0.1)

^ р(х) XED

Это основной объект исследования диссертации. Из непрерывности конечных функций R(x) и р(х) легко следует, что решение задачи (0.1) существует. Далее понимаем под

ip* = min VW, C^ = {y£ D: ф(у) = V*}.

XED

Величину ip* договоримся называть показателем асферичности тела D, а С^р - множеством центров асферичности.

Показатель асферичности гр* нередко используется (обычно для случая, когда п (х) - евклидова норма) при описании свойств выпуклого тела и построении методов по приближению (см., напр., [17]). Очевидно ip* = 1 тогда и только тогда, когда тело D является шаром используемой нормы п(-). Поэтому величина гр* — 1 может рассматриваться как некоторая мера отличия тела D от шара.

3. Несмотря на естественность постановки задачи следов ее исследования найти не удалось. Близкой к ней, по постановке, является давно известная (см. [2], [32] - [40], [12]) задача об отыскании центра шарового слоя наименьшей толщины, содержащего границу выпуклого тела D

Ф(х) = R(x) -р(х) —> min. (0.2)

XED

В качестве близкой, по смыслу, к задаче (0.1) можно назвать также задачу о наилучшем приближении выпуклого компакта D шаром в метрике Хаусдорфа:

(р(х,г) = h(D,Bn(x,r)) —» min . (0.3)

Здесь Bn(x, г) = {у Е Шр\п(х — у) <г] - шар в норме п(-) с центром в точке х и радиусом г, а

h{A, В) = max ]sup inf п(а — b), sup inf n(a — b) j -

iaEA bEB bEB aEA >

- расстояние между множествами А и В в метрике Хаусдорфа, индуцированное используемой нормой п(-).

Задача (0.2) для случая евклидовой нормы рассматривалась в работах [32] - [40], а задача (0.3) в [18]. Для случая произвольной нормы свойства решения задач (0.2) - (0.3) исследовались в [8], [9], [12], [41]. В работе [9], в частности, приводятся условия на норму п(-) и тело D, при которых задачи

(0.2) и (0.3) являются эквивалентными. Установлено, что в общем случае справедливо соотношение

Сф = СрПО.

Здесь Сф = {у е Ф(у) = тт^д Ф(х)} - множество центров шаровых слоев наименьшей толщины, содержащих границу тела О. А Су = [у е Ер: Зг > 0, (р(у,г) = ттхеЕрг>0 <р(у,г)} - множество центров шаров наилучшего приближения в задаче (0.3).

Отметим, что если величина гр* — 1 выражает относительную меру отличия тела Б от шара, то оптимальные значения целевых функций задач (0.2) и (0.3) выражают абсолютную меру, то есть зависящую от размера тела Б. Поэтому естественно ожидать, что решения задач (0.2) и (0.3) могут не совпадать с решениями задачи (0.1), что и показывают примеры. 4. Цель исследования заключалась в следующем:

1) изучить свойства целевой функции гр(х) задачи (0.1),

2) получить необходимые и достаточные условия ее решения,

3) получить условия единственности ее решения,

4) дать сравнение задачи (0.1) с задачами (0.2) и (0.3), а также задачами о внешней и внутренней оценке тела О с помощью задачи

ф,г)->т ш (0.4)

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

5) разработать и обосновать метод приближенного решения задачи (0.1).

Известно, что функция Я(рс) выпукла на Кр (см., напр., [23]), а функция р(х) является вогнутой на О ([11]). Поэтому целевая функция задачи (0.2) также выпукла на О. В [9] показано, что целевая функция ср(х, г) задачи (0.3) является выпуклой по совокупности переменных (х,г) 6 1р х!+. Таким образом задачи (0.2) - (0.3) являются задачами выпуклого программирования. Однако, как будет показано, целевая функция гр(х)

задачи (0.1) может не быть выпуклой или вогнутой. Это обстоятельство доставляет затруднения при исследовании задачи (0.1) и, возможно, объясняет отсутствие результатов ее исследования.

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

5. Диссертация состоит из трех глав, содержащих 14 параграфов. Нумерация параграфов сквозная. При изложении, кроме уже введенных используются следующие обозначения:

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

А ± В = {а ± b: a Е A, b Е В} — алгебраическая сумма и разность множеств А и В,

К (А) = {v Е ШР-. За > 0, а £ A, v — аа} - коническая оболочка множества А,

К+ = {w 6 {v, w) >0, Vv Е К] — сопряженный конус к конусу К, К(х,А~) — конус возможных направлений множества А в точке х G А, то

есть К(х,А) = у(х, Л), где

у(х,А) = [д £ Зад > 0: х + ад Е А,а е (0, ад)}, (рм(х) = inf{a > 0: х Е аМ} - функция Минковского множества М, df(x0) = {vE ЩР- fix) - f(xQ) >{v,x- x0),Vx E 5} -

субдифференциал выпуклой функции fix), определенной на выпуклом множестве S с в точке х0,

Qr(x) = {z Е D: Rix) = nix - z)} — множество точек касания множества D и шара Bn(x,Rix)),

Qpix) = {z Е Q: pix) = n(x - z)} - проекция точки x на множество Í1 = W\D.

Первая глава диссертации состоит их 5 параграфов и посвящена характеризации решения задачи (0.1).

В 1-ом параграфе дается математическая формализация задачи и ставится цель исследования.

Во 2-м параграфе приводятся вспомогательные сведения необходимые для дальнейшего исследования. Они касаются свойств функций R(x), р{х), решений задач о внешней и внутренней оценке выпуклого тела D шаром нормы п(-), а также решений задач (0.2) и (0.3).

В §3 изучаются свойства целевой функции ф(х) задачи (0.1). Эти свойства отражаются следующими доказанными фактами.

Теорема 3.1. Функция ф{х) является квазивыпуклой на D, а если D -строго выпуклый компакт, то строго квазивыпуклой.

Теорема 3.2. Функция гр(х) является субдифференцируемой (в смысле определения В. Ф. Демьянова — A.M. Рубинова [7]) в любой точке х0 £ intD, причем ее субдифференциалом в этой точке является выпуклый компакт

дгКх0) = (р(*о)Г2[р(хоЖОо) - R(xo№(*o)L (°-5)

где dR_(x0) - субдифференциал выпуклой функции R{x), а др(х0) -супердифференциал вогнутой функции р(х) в точке х0.

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

В §4 на основе формулы (0.5) субдифференциала функции ф(х) получен критерий решения задачи (0.1).

Теорема 4.1. Для того, чтобы точка х* Е intD, была точкой минимума функции ip(x) на выпуклом теле D, необходимо и достаточно, чтобы

0р 6 p{x*)dR{x*) - R(x*)dp(x*). (0.6)

Как показывают примеры, решение задачи (0.1) может быть неединственным. В §5 приводятся условия, выполнение которых обеспечивают единственность решения.

Теорема 5.1. Если выполняется хотя бы одно из условий:

1) В- строго выпуклое тело,

2) выпуклое тело И обладает центральной симметрией и при этом

либо а) п(х) - строго квазивыпуклая норма, либо б) размерность пространства р = 2, то задача (0.1) имеет единственное решение.

6. Вторая глава диссертации состоит из §§6 - 9, в ней изучается взаимосвязь задачи (0.1) с другими задачими.

В работе [8] установлено, что решение задачи (0.2) и (0.3), а также решение задачи о внешней оценке

и задачи о внутренней оценке

R{x) min (0.7)

хеШР

р{х) —» шах (0.8)

xeD

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

Целью главы является ответ на вопрос: может ли задача (0.4) выражать также и решения задачи (0.1) при каких либо значениях радиуса г и в случае положительного ответа уточнить соответствующий диапазон значений этого радиуса?

В §6 приводятся вспомогательные сведения из работы [8] о параметрической взаимосвязи задачи (0.4) с задачами (0.2) - (0.3) и (0.7) -(0.8). Введем обозначения

р(х) = minn(x - у), Р(х) = р(х)~ р(х), (0.9)

уео

R* = min R(x), р* = maхр(х), (0.10)

xeEn xeD

CR={yeW:R(y) = R*}, Cp = {yeD:p(y)=p*l (0.11)

R* = max (min) R(x), P± = max (min) P(x), (0.12)

xGCp xeCft

rR± = (R*- P+)/2, rP± = (R±+ p*)/2, (0.13)

Cv(r) =

c<p(r) = {у 6 <p(y,r) = min <pO,r)J. (0.14)

Из (0.9) - (0.13) вытекает следующая последовательность

+ +

расположения значении rR - и тР- на числовой оси

0 < rR~ < rR+ < rP~ < гР+ < оо. (0.15)

В [8] доказано, что, если CRf]Cp = 0, то решения С(р(г) задачи (0.4)

выражают решения задач (0.7) и (0.8) в соответствии с формулой

r CR , если г е [0,гй~],

СдП{х £ Ж v\P{x) < R* - 2 г}, если г £ [rR~,rR+],

СрГ\{х £ E?-.R(x) < 2r-р*}, если г £ [гр-,гр+], (0Л6)

Ср , если г>гР+,

а кроме того существует отрезок такой, что решения задачи (0.4)

выражают решения задачи (0.3) в виде

С„ = и С<р{г), (0.17)

ГЦГср ,Г(р + \

и при этом

[r<p-,г/] с [rR+,rp~l (0.18)

Отметим, что если CR ПСр Ф 0, то rR+ — rP~ = (R* + р*)/2 и при этом

Cv(iR* + Р*)/2) = Сф = С<р = СйПСр. В §7 изучаются свойства решения (^(г) задачи (0.4). Самые важные их них относятся к функции

/рО) = min Р(х). хес<р(г)

Лемма 7.4. Функция fP(r) непрерывна на Е+, не возрастает на Е+, выпукла при г > rR+, строго убывает на отрезке [rR+,rp~].

В §8 доказана теорема о параметрическом вложении задачи об асферичности (0.1) в шкалу (0.15), к которой формулами (0.16) - (0.17) привязаны решения и других сравниваемых здесь задач.

Теорема 8.1. Пусть CRf]Cp = 0. Тогда существует отрезок [г, такой, что

1) С^Р= ^ге[гф-,гф+)Сср(.г)>

fo+,rP~l (o.i9)

Таким образом, соотношения (0.19) и (0.16) - (0.18) говорят о том, что решения задачи (0.1) об асферичности, выражаемые решениями задачи (0.4) по шкале (0.15), лежат «между» решениями задачи (0.3) и решениями задачи (0.8). При этом допустимы ситуации когда С^ПС^ 0 или Ф 0 даже

в случае, когда CRf]Cp = 0.

В §9 для двухмерного случая с евклидовой нормой доказано, что у задачи (0.1) обязательно есть хотя бы одно общее решение с задачей (0.3) (теорема 9.1). Для трехмерного случая с евклидовой нормой приводится пример, когда у задач (0.1) и (0.3) нет общих решений.

7. Главная цель третьей и последней главы - разработка метода приближенного решения задачи (0.1).

В §10 предлагается подход к получению приближенного решения, в виде построения итерационного процесса, на каждом шаге которого решается задача выпуклого программирования. Его суть заключается в следующем. Если уже построена точка очередного приближения хк 6 D и ак = гр(хк), то в качестве точки хк+1 берется решение задачи

грк(х) = R(x) — акр(х) min, (0.20)

xeD

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

Теорема 10.1. Любая предельная точка последовательности {xk)k=о 1,2,... является центром асферичности выпуклого тела D.

Кроме того, показано что в случае, когда выпуклое тело D и шар используемой нормы являются многогранниками, то задача (0.20) сводится к задаче линейного программирования (теорема 10.2).

В §11 исследуется вопрос об устойчивости решения задачи (0.1) к погрешности задания оцениваемого на асферичность выпуклого тела D.

Доказано, что задача обладает устойчивостью оптимального значения целевой функции (теорема 11.1). Также рассматривалось многозначное отображение С^(-), сопоставляющее элементам пространства выпуклых тел Ку(ШР) соответствующие множества центров асферичности. То есть С^ф) -множество центров асферичности для И Е Ку(Шр).

Доказано, что это отображение обладает полунепрерывностью сверху (теорема 11.2). Из этого факта вытекает, что решая некоторую последовательность задач об асферичности для выпуклых тел 0£., где

< £ь £¿>10 при ¿—»оо, мы можем получить приближенное значение хотя бы одного из центров асферичности для О.

Кроме того приведен пример, когда полунепрерывность снизу отображения С^ (•) отсутствует. Это значит, что имеет место

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

В §12 обсуждаются вопросы практического получения субградиентов функции Я(х) и суперградиентов функции р{х) в конкретной точке с целью использования при построении численного метода решения задачи (0.1).

В §13 дается принципиальная схема построения последовательности приближений в итерационном методе решения задачи (0.1).

Пусть на к - ом шаге получена четверка объектов {хк,ак,Мк,Т)с}, удовлетворяющая условиям:

- точка Е ¿пШ, ак = тт{ак_1,гр(хк)},

- многогранник Мк, Тк построены так, что Вп(Ор, 1) с Мк, О а Тк.

Приведем описание вычислений на к + 1-ом шаге метода для

получения четверки объектов {хк+1,ак+1,Мк+1,Тк+1} с аналогичными свойствами:

1) Находим любую точку гЕС}11^]^) и в точке (г - хк) /п(г — хк) стро�