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

• Осипцев, Михаил Анатольевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Осипцев, Михаил Анатольевич

Оглавление

Введение

Раздел 1. Свойства решения задачи

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

2 Вспомогательные сведения

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

4 Вариационные свойства решения

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

6 Случай редукции к задаче линейного программирования

Раздел 2. Характеризация устойчивости решения задачи

7 Постановка вопроса об устойчивости решения задачи

8 Вспомогательные факты из сильно выпуклого анализа

9 Чувствительность решения по функционалу

10 Общая характеристика устойчивости решения

11 Чувствительность решения при г € [0,гд] и г ^ гр

12 Чувствительность решения при г € (г^гр)

Заключение

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

Введение диссертации (часть автореферата) на тему «Оценка выпуклого тела шаром фиксированного радиуса в метрике Хаусдорфа»

Введение

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

Негладкий анализ и недифференцируемая оптимизация развивались в трудах Р. Т. Рокафеллара, Б.Н. Пшеничного, В.Ф. Демьянова, А.М. Руби-нова, Ф. Кларка, Ж.-П. Обена, И. Экланда, Ж.-Б. Ириарт-Уррути, М.С. Никольского, Е. С. Половинкина, В.М. Миклюкова, В.В. Гороховика, Л.И. Минченко, Г. Е. Иванова, М.Б. Балашова ( [39], [37]- [38], [10]- [12], [28], [32]- [33], [49]- [50], [31], [34]- [36], [30], [8], [22]) и других отечественных и зарубежных математиков.

Одним из направлений негладкого анализа является оценка и аппроксимация достаточно сложных множеств множествами простой структуры. Задачи такого типа имеют широкое применение в естественных науках, а также и в самой математике. В этом русле находятся многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (см., например, монографии [42], [52] и др.). Известно также много работ по внешним и внутренним оценкам заданных множеств многогранниками (см., например, обзор [5], [24]- [26]) и, в частности, ориентированными параллелепипедами (напр. [1]) и их приложениям.

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

Интерес математиков к оценкам и приближению выпуклого компакта шаром возник давно (см., например, монографии В. Бляшке [3], Т. Бонне-зена, и В. Фенхеля [4], Л.Ф. Тота [40]), а также [47], [53], [51], [46], [54]- [56]). Этот интерес возобновлялся по мере появления в математике новых средств

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

Рассматриваемая в диссертации задача относится именно к задачам по шаровым оценкам выпуклого тела.

Приведём ее математическую формализацию.

Пусть D - выпуклое тело из конечномерного действительного пространства Rp, а функция n(x) - некоторая норма на Rp,

p(A, B) = sup inf n(a — b)

aEÄ bEB

- уклонение множества A от множества B,

h(A,B) = max{p(A, B),p(B,A)}

- расстояние Хаусдорфа между множествами A и B, индуцированное нормой n(),

Bn(x, r) = {y E Rp : n(x — y) ^ r}

- шар в норме n( ) с центром в точке x и радиусом r.

Тогда задачу о наилучшем приближении (оценке) выпуклого тела D шаром нормы n( ) с радиусом r в метрике Хаусдорфа, порождённой этой нормой, можно записать в виде

Ф(х,г) = h(D, Bn(x,r)) ^ min. (1)

x€Mp

Это основной исследуемый объект в диссертации.

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

x,r) ^ min , (2)

то есть когда функция ф(х,г) минимизируется не только по х £ но и по г ^ 0, была поставлена и рассматривалась в работе М.С. Никольского, Д.Б. Силина [31] для случая евклидовой нормы. В этой работе доказаны существование и единственность решения , получено необходимое условие решения. Там же отмечено, что полученные результаты нетрудно перенести на случай более общей «эллипсоидальной» нормы, ввиду простой связи решений для этих норм. Позднее С.И. Дудовым и И.В. Зла-торунской в работах [20], [48] задача (2) исследовалась для произвольной нормы. В [20] получены критерий решения задачи, условия единственности решения (для неевклидовой нормы задача (2) может иметь неединственное решение), условие принадлежности центра шара наилучшего приближения выпуклому компакту В.

Задача (1) интересна следующим обстоятельством. В работе С.И. Дудо-ва [18] показано, что она является «канонической» для некоторого класса задач по оценкам выпуклого компакта шаром в виде экстремальных задач, целевая функция которых выражается через функцию расстояния до наиболее удаленной точки компакта и функцию расстояния до ближайшей точки компакта или его дополнения. Доказано, что решение любой задачи из указанного в [18] класса могут быть выражены решениями задачи (1) при некоторых значениях радиуса г. Кроме того, исходя из некоторых дополнительных априорных данных, указаны диапазоны значений радиуса г в которых она выражает решения задач о вписанном и описанном шарах, задачи (2) - о равномерной оценке шаром в метрике Хаусдорфа, задачи об асферичности выпуклого тела [21], задач о шаровых оболочках наименьшей толщины [4], [16], и наименьшего объема [18], [57], [58] для границы выпуклого тела. Что касается непосредственно задачи (1), то в [18] получены лишь необходимое и достаточное условия ее решения и указаны

некоторые используемые свойства решения.

В связи с этим актуален вопрос о более полном исследовании задачи

(1).

Цели и задачи диссертации

Целями и задачами диссертации являются:

• получение условий единственности решения задачи (1) в зависимости от диапазонов значения параметра г,

• исследование вариационных (по г) свойств решения,

• рассмотрение случая редукции задачи (1) к задаче линейного программирования и, на этой основе, предложение подхода к получению приближенного решения в общем случае,

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

Методология и методы исследования

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

Научная новизна и положения, выносимые на защиту

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

2. Установлены вариационные свойства решения задачи (1).

3. Рассмотрен случай редукции задачи (1) к задаче линейного программирования и, на этой основе, предложен подход к получению приближенного решения в общем случае.

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

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

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

Степень достоверности и апробация результатов

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

Основные результаты диссертации докладывались на научных конференциях сотрудников механико-математического факультета Саратовского государственного университета (2013-2016 г.); на 17-ой, 18-ой Саратовских зимних школах «Современные проблемы теории функций и их приложения» (Саратов, 2014 г., 2016 г.); на 11-ой, 12-ой международной Казанской летней научной школе-конференции «Теория функций, её приложения и смежные вопросы» (Казань, 2016 г., 2014 г.); на VII Петроза-

водский международной конференции «Комплексный анализ и его прило-жения»(Петрозаводск, 2014 г.); на 3 международной школе конференции «Геометрический анализ и его приложения» (Волгоград 2016 г.); на объединенном научном семинаре механико-математического факультета СГУ под руководством профессора А.П. Хромова (Саратов, 2016 г.), на научном семинаре кафедры высшей математики Московского физико-технического института (государственного университета) под руководством проф. Е.С. Половинкина (Долгопрудный, 2016 г.), на семинаре отдела «Математическое моделирование экономических систем» ВЦ РАН ФИЦ ИУ под руководством член-корр. РАН И.Г. Поспелова (Москва, 2017 г.).

Результаты исследований опубликованы автором в двенадцати работах. Работы [61], [62], [66], [68] опубликованы в изданиях, входящих в перечень рецензируемых научных изданий, рекомендованных ВАК РФ.

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

Первый раздел состоит из шести подразделов. В первом подразделе даётся постановка исследуемой задачи и ее обсуждение. Во 2-ом подразделе приводятся вспомогательные сведения о свойствах функций расстояния, как основных средствах исследования. В 3-ем подразделе приводятся полученные в [18] необходимые и достаточные условия решения задачи, и на примере демонстрируется их применение. В 4-ом подразделе изучаются вариационные (по фиксируемому радиусу) свойства решения задачи. В 5-ом подразделе установлены условия единственности решения при определенных значениях фиксируемого радиуса в виде требований на приближаемое тело, используемую норму и размерность пространства. В 6-ом подразделе показано, что если шар используемой нормы и приближаемое тело являются многогранниками, то задача может быть сведена к задаче линейно-

го программирования. Это обстоятельство даёт возможность предложить подход к приближенному решению задачи.

Второй раздел состоит шести из подразделов. В подразделе 7 дается постановка вопроса об устойчивости решения, а также количественной ха-рактеризации устойчивости (чувствительности) решения задачи (1.1) относительно погрешности задания тела О и единичного шара используемой нормы. В подразделе 8 приводятся вспомогательные факты, в основном относящиеся к сильно выпуклому анализу. В 9-ом подразделе получена оценка чувствительности оптимального значения целевой функции задачи (чувствительности по функционалу). В 10-ом подразделе доказано, что уклонение множества решений «приближенной» задачи от множества решений «точной» задачи стремится к нулю, при стремлении погрешностей задания тела О и единичного шара используемой нормы к нулю.

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

Раздел 1 Свойства решения задачи

Раздел состоит из шести подразделов. В первом подразделе даётся постановка исследуемой задачи и ее обсуждение. Во 2-ом подразделе приводятся вспомогательные сведения о свойствах функций расстояния, как основных средствах исследования. В 3-ем подразделе приводятся полученные в [18] необходимые и достаточные условия решения задачи, и на примере демонстрируется их применение. В 4-ом подразделе изучаются вариационные (по фиксируемому радиусу) свойства решения задачи. В 5-ом подразделе установлены условия единственности решения при определенных значениях фиксируемого радиуса в виде требований на приближаемое тело, используемую норму и размерность пространства. В 6-ом подразделе показано, что если шар используемой нормы и приближаемое тело являются многогранниками, то задача может быть сведена к задаче линейного программирования. Это обстоятельство даёт возможность предложить подход к приближённому решению задачи.

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

Пусть D заданное выпуклое тело из конечномерного пространства Rp, а n(x) - некоторая норма на Rp. Рассматривается задача

Ф(х,г) = h(D, Bn(x,r)) ^ min. (1.1)

Здесь Bn(x,r) = {y G Rp : n(x — y) < r} - шар нормы n(^) радиуса r с центром в точке x,

h(A, B) = max{sup inf n(a — b), sup inf n(a — b)}

aGA bGB bGB aGA

(1.2)

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

Впервые задача о приближении выпуклого тела евклидовым шаром в метрике Хаусдорфа, причем произвольного радиуса, то есть когда функция ф(х,г) минимизируется по (х,г) Е х (равномерная оценка), рассматривалась в [31]. Для случая произвольной нормы такая задача исследовалась в [20], [48].

В работе [18] показано, что задача (1.1) играет роль «канонической» задачи для целого класса задач по шаровым оценкам выпуклых тел. В частности показано, что своими решениями для значения радиуса из определённых диапазонов она выражает решения задач о вписанном и описанном шарах, задачи о равномерной оценке шаром, задачи об асферичности выпуклого тела, задач о шаровых оболочках наименьшей толщины и наименьшего объема для границы выпуклого тела.

Необходимые и достаточные условия решения задачи (1.1) получены [18], там же приведены некоторые свойства ее решения.

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

При изложении, кроме уже введенных, используются следующие обозначения:

• А - замыкание множества А;

• ъША - внутренность множества А;

• соА - выпуклая оболочка множества А;

• в^х А -сильно выпуклая оболочка радиуса Л (А-сильно выпуклая

оболочка) множества А;

А + В = {а + Ь : а Е А, Ь Е В} - сумма множеств А и В;

*

А — В = {с : с + В С А} - геометрическая разность множеств А и В;

К (А) = {и Е : За ^ 0, а Е А, и = аа} - коническая оболочка множества А;

К + = {и Е : {и, и) ^ 0,Уи Е К}-конус, сопряжённый к конусу К;

К(х, А) = {д Е : Зад > 0,х + ад Е А, а Е (0, ад)} - конус возможных направлений множества А в точке х; дГ(х) - субдифференциал выпуклой функции Г(х) в точке х;

dF(x) - супердифференциал вогнутой функции F(x) в точке x; n(•) - используемая норма; || • || - евклидова норма;

Bn(x,r) = {y Е Rp : n(x — y) ^ r} - шар с центром в точке x радиуса r в норме n(•);

R(x, D) = max n(x — y) - расстояние от точки x до самой удалённой

yED

точки тела D;

p(x, D) = min n(x — y) - расстояние от точки x до ближайшей точки

yED

тела D;

p(x, ü) = min n(x — y) - расстояние от точки x до ближайшей точки

yEÜ _

замыкания дополнения тела D, ü = Rp \ D;

P(x,D) = p(x,D) — p(x, ü) - симметризованное расстояние до границы тела D;

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

Qp(x,D) = {y G D : p(x,D) = n(x — y)} - проекция точки x на множество D;

Qp(x, ü) = {z G ü : p(x, ü) = n(x — z)} - проекция точки x на

множество ü = Rp \ D.

2 Вспомогательные сведения

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

1. В силу того, что норма n(x) является выпуклой конечной на Rp функцией, то (см. [11], гл. 1, §4) она является дифференцируемой по любому направлению g G Rp в любой точке x G Rp, при этом ее субдифференциал dn(x), как многозначное отображение, является полунепрерывным сверху. Для производных по направлению справедлива формула

к \ т n(x + eg) — n(x) , . .

n (x,g) = lim-= max (v,g), (2.1)

£^0 e vGdn(x)

где (•, •) - скалярное произведение.

Известна формула субдифференциала нормы ( [23], [37]):

{v G Rp : n*(v) < 1}, если x = 0p,

dn(x) = { (2.2)

{v G Rp : n*(v) = 1,n(x) = (v, x)}, если x = 0p,

где

n*(v) = max (v, x)

n(x)^1

полярная к n(x) норма.

Определение 2.1. Норма n(x) называется строго квазивыпуклой если для любых x\ Е Rp, x2 Е Rp и а Е (0, 1) выполняется

п(ах\ + (1 — ах2)) < max{n(xi), n(x2)}.

Примером строго квазивыпуклой нормы является евклидова и «эллип-саидальная» норма, а также функция Минковского, порождённая строго выпуклым телом, симметричным относительно 0p. Норма

n(x) = max\x(k)\, x = (x(l),x{2), • • • ,x(p)) Е Rp, k=i,p

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

2. Расстояние от точки x до самой удалённой точки компакта D, в норме n( ), выражает функция

R(x,D) = max n(x — y). (2.3)

yED

Очевидно, R(x, D) конечная выпуклая на Rp функция. Известна формула ее субдифференциала (см. [37])

dR(x, D) = co{dn(x — z): z Е QR(x, D)}, (2.4)

где

Qr(x, D) = {z Е D : R(x, D) = n(x — z)}.

3. Расстояние от точки x до ближайшей точки компакта D выражает функция

p(x,D) = min n(x — y). (2.5)

УЕD

Если компакт Б является выпуклым, то функция р(х, Б) является выпуклой и конечной на а ее субдифференциал может быть выражен формулой ( [14])

др(х, Б) = дп(х — г) р|{ —К+(г, Б)}, (2.6)

где г - любая точка из Qp(x, Б) = {у <Е Б : р(х, Б) = п(х — у)} - проекция точки х на Б.

4. Важное значение для нас будет играть функция расстояния от точ-

ки x до ближайшей точки множества ü = Rp \ D

p(x, ü) = minn(x — y). (2.7)

vgü

Если D - выпуклое тело, то функция p(x, ü) является вогнутой на D функцией, а для ее супердифференциала в точке x G int D справедлива формула (см. [14])

dp(x, ü) = co{dn(x — z) П K+(z, D) : z G Qp(x, ü)}, (2.8)

где

Qp(x, ü) = {z G ü : p(x, ü) = n(x — z)} - проекция точки x на ü.

5. Более информативно по сравнению с функциями p(x, D) и p(x, ü) множество D характеризует функция

P(x,D) = p(x, D) — p(x, ü).

Функция P(x,D) выражает расстояние от точки x до границы множества D, причем с отрицательным знаком, если x G int D. Впервые эта функция

была введена в [49] - [50]. В случае евклидовой нормы ее свойства рассматривались также в [8]. Ее называют «симметризованным» расстоянием.

Если Б - выпуклое множество, то функция Р(х, Б) выпукла на В [20] получена формула ее субдифференциала

дР (х,Б) = <

дп(х — —К + (г, Б), У г Е Яр(х, Б), х£ Б; со{дп(г — х) П —К + (г, Б)}, У г Е Яр(х, П), х Е Б; (2.9) со{и Е —К +(г, Б) : п*(и) = 1}, х Е дБ,

где п*(и) - полярная норма, дБ -граница множества Б.

Эти функции и их свойства являются главными средствами исследования задач по шаровым оценкам множеств. Отметим, что специфика компакта Б и используемой нормы (например, строгая или сильная выпуклость Б (см. [36]) и строгая или сильная выпуклость шара используемой нормы) индуцируют интересные свойства функций расстояния, которые можно использовать.

Везде далее, как и при постановке задачи (1.1), мы считаем множество Б выпуклым телом. Поэтому имеют место все указанные характеристики данных функций расстояния (2.4), (2.6), (2.8), (2.9).

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

При исследовании вариационных свойств решения задачи (1.1) и получения условия единственности ее решения будем использовать необходимое и достаточное условие решения задачи (1.1), полученные в [18]. В данном параграфе мы приведём эти условия и продемонстрируем их применение на примере.

Важное значение будет иметь формула полученная в [20]

х, г) = шах{Я(х, Б) — г, Р(х, Б) + г}. (3.1)

В силу выпуклости функций R(x, D) и P(x, D) функция ф(х,т) также выпукла по х на Rp. Нижние лебеговы множества функций R(x, D) и P(х, D) ограничены и выпуклы. Действительно,

GR(a) = {х е Rp : R(x, D) < а} = {х е Rp : max n(x — y) < а} =

y۟

= {x е Rp : n(x — y) < a, Vy е D} = p| Bn(y, а).

yeD

Далее, при а ^ 0 имеем

GP(а) = {x е Rp : P(x, D) < а} = {x е Rp : p(x, D) < а} =

= {x е Rp : minn(x — y) ^ а} = I I Bn(y, а) = D + Bn(0p, а), y&D ^

y£D

если а < 0, то

GP(а) = {x е Rp : P(x, D) < а} = {x е Rp : p(x, ü) ^ —а} С D.

Поэтому, учитывая (3.1), нетрудно сделать вывод, что решение задачи (1.1) существует и множество ее решений

Сф(т) = {y е Rp : ф(у, т) = min ф(х, т)}, (3.2)

хем^

как пересечение нижних лебеговых множеств функций R(x,D) и P(x,D), является выпуклым компактом. При этом, как известно из выпуклого анализа (см. [37], гл. 4, §2)

y е Сф(т) & 0p е дхф(у,т). (3.3)

Здесь дхф(у, т)-субдифференциал выпуклой функции ф(х,т) по х в точке y.

Следуя правилам субдифференциального исчисления (см. [11]) и ис-

пользуя (3.1), можем записать

дхф(х,т) = <

dR(x,D), если R(x,D) - r>P (x,D) + r,

dP (x,D), если R(x,D) - r<P (x,D) + r,

co{dR(x,D),dP(x, D)}, если R(x,D) - r = P(x,D) + r.

(3.4)

Для конкретизации критерия решения задачи (1.1) для различных значений r, введем следующие обозначения:

R* = min R(x, D), Cr = {y e Rp : R(y, D) = R*}

xERp

p* = maxp(x, ü), Cp = {y e D : p(y, ü) = p*}.

xED

То есть эти данные выражают решения задач о описанном и вписанном шарах:

R(x, D) ^ min, p(x, ü) ^ max.

xEd xEü

Эти задачи мы будем также называть задачами о внешней и внутренней оценке тела D шаром нормы n( ).

Считая эти данные известными, будем также считать известными величины

R± = max(min)R(x, D), P± = max(min)P(x,D), (3.5)

xeCp xEcR

r± = (R* - PT)/2, r± = (R± + p*)/2. (3.6)

В силу того, что R(x,D) ^ P(x,D) при любом x e Rp из (3.5), (3.6)

следует

0 < r-< r+ < r-< r+ < oo. (3.7)

Очевидно, если задача о внешней оценке имеет единственное решение, то r- = r+, а если задача о внутренней оценке имеет единственное решение то r- = r+.

В [17] показано, что

гР = г+

& Cr[) Cp = (3.8)

Теперь сформулируем необходимые и достаточные условия решения задачи (1.1) в зависимости от значений г.

Теорема 3.1. [18] Для того, чтобы х* € Сф(г) необходимо и достаточно, чтобы

1)0p е dR(x*,D), если r е [0, rp],

2) 0Р е dR(x*, D) и R* - P(x*, D) > 2r, если r е [rp, r+],

3)0p е co{dR(x*,D), dP(x*,D)} и R(x*,D) — P(x*,D) = 2r, если r е [r+,r—],

4) 0p е dP(x*, D) и R(x*, D) + p* < 2r, если r е [rp, r+],

5) 0Р е 3P_(x*, D), если r > r+.

Замечание 3.1. В соответствии с критерием минимума для выпуклой функции

y е Cr & 0p е dR(y,D),

а в соответствии с критерием максимума для вогнутой функции

y е Cp & 0p е dp(y, Q).

Поскольку Cp С int D, то для точки y е Cp выполняется P(y,D) = —p(y, Q) и следовательно, dP(y,D) = —dp(y, Q). Поэтому

y е Cp & 0p е dP(y, D). Учитывая это, из теоремы 3.1 вытекает ( [17])

Cr, если r е [0, rp] Cr п{x е Rp : R* — P(x, D) ^ 2r}, если r е [rp,r+]

C^(r) = {

Cpd{x е Rp : R(x,D) + p* < 2r}, если r е [r—,r+] Cp, если r ^ r+.

Как показано в [17], имеет место Следствие 3.1. Если СдР| Ср = то

1) Сф(т)[) Си = Ут>т+,

2) Сф(г)() Ср = Уг е [0,г-),

3) Сф(п)[) Сф(г2) = Уп = Т2,Т1,Т2 е [Г+,Г-].

Если Си П Ср = то г+ = г- = (Я* + р*)/2 и Сф((Я* + р*)/2) = Си П Ср.

Замечание 3.2. Формулы (2.4) и (2.9) субдифференциалов функций Я(х, Б) и Р(х, Б) придают конструктивный характер теореме 3.1 и позволяет решать конкретные задачи.

Пример 3.1 Пусть р =2, п(х) = \\х\\ - евклидова норма, Б-разносторонний треугольник. В данном случае задачи об описанном и вписанном шарах имеют единственное решение. Поэтому

Си = {хи}, Ср = {хр},

где хи и хр - центры описанного и вписанного круга и

± Я* + р(хи, П) ± Я(хр,Б) + р*

ги = ги =-2-' гр = Гр = 2 ■

Для евклидовой нормы п(х) = \\х\\ ее субдифференциал для х = 0Р состоит из единственной точки д\\х\\ = {"рц}. Тогда формула (2.4) прини-

мает вид

dR(x,D) = co ( X ~ Z : z E QR(x,D)\. (3.9)

I x z I

Соответственно для точек x E int D из (2.9) получаем

dP_ (x, D) = co\ Z ~ x : z E Qp(x, Q)\ . (3.10)

i z x I

1) Случай r E [0,rR].

Рис. 3.1. Решение задачи в случае r е [0,rR].

На рисунке 3.1 в качестве D = co {z1, z2, z3} - разносторонний треугольник, xR - центр описанного круга, QR(xR, D) = {z1, z2, z3}. В соответствии с формулой (3.9),

3R(xr,D) = co {yi,y2,y3}, где y- = —^ = ~R—z-, i = 1, 2, 3.

\\xr — z-1| R*

Поскольку в соответствии с критерием минимума выпуклой функции (напр., [37], гл. 4, §2)

y е Cr & 0p е dR(y,D),

то, учитывая Cr = {xr}, из теоремы 3.1 вытекает

^(7-) = {xr}, Vr е [0,rR].

2) Обозначим через x* - точку пересечения перпендикуляра к наибольшей стороне и биссектрисы наименьшего угла. В нашем случае, это сторона соединяющая точки z1 и z3, а угол - угол с вершиной z1

Возьмем произвольную точку х е (хи,х*) (см. рис 3.2). Для неё як(х, Б) = {гигз}, Яр(х, и) = Ы, где х4 - проекция точки х на сторону [г\, г3]. Тогда имеем

дЯ(х,Б) = со {у1,уз}, Уг = _ ^м = 1,3;

х

дР(х, Б) = {у} У4 = _ х

\х4 _ х\\

В данном случае, из геометрических построений, видим, что 02 е со{дЯ(х, Б),дР(х,Б)}. Следовательно, по теореме 3.1, х е Сф(г) для значений

= Я(х, Б) _ Р(х, Б) = Я(х, Б) + р(х, и) г = 2 = 2 '

Заметим, что при перемещении точки х от точки хи до х* значение Я(х,Б) растёт от Я* до Я(х*,Б), а значение р(х, и) растёт от р(хи, и) до р(х*, и). Поэтому, и значение радиуса г, соответстветствующее точке х, растёт от значения ги до значения —— ——.

Рис. 3.3. Решение задачи в случае г =

_ К(х*,Б)+р(х* ,П)

_ Е(х*,П)+р(х*,П)

3) Покажем, что х* € Сф(г) при значении г = 2 .

Для точки х* имеем (см. рис. 3.3)

Як(х*,Б) = {хихз}, Яр(х*, Я) = {Х4,Х5},

где х4,х5 - проекции точки х* на стороны [¿ь^з] и [х\,х2] соответственно. Поэтому по формулам (3.9), (3.10) получаем

X* — X'

дЯ(х*, Б) = со {у1,уз}, Уг = ,, * _ = 1, 3;

X X' X' — X*

др(х*,Б)= со {У4,У5}, Уг = ^-^ = 4, 5.

Хг X

В данном случае также выполняется 02 € со{дМ(х*, Б), дР(х*,Б)} и

, , Ц(х* П)—Р(х* П) Я(х* П)+п(Х* О)

следовательно х* € Сф(г) для значения г = —— 2 — = —' 2 — . 4) Обозначим через хр - центр вписанного в Б круга. Пусть х - произвольная точка из (х*, хр). Для нее имеем

ЯК(х, Б) = {х} ЯР(х, П) = {Х4, Х5},

2

Рис. 3.4. Решение задачи при г Е (^Я(х ,Б"12+р(х ^ , Я(хр^.

где х4, х5 - проекции точки х на стороны [хг, х3] и [хг, х2]. В соответствии с формулами (3.9) и (3.10) имеем

х — Х\

дЯ(х*, В) = {уг}, уг =

\х — хг\

дР(х*,В) = со {У4,У5}, Уг = — х, = 4, 5.

Хг X

Таким образом (см. рис. 3.4), видим, что 02 Е со{дЯ(х, В),дР(х,В)} и

^ ГУ / \ Я(х,Б)—Р(х,Б) Я(х,П)+р(х,П)

поэтому х Е Сф(т) для значения г = к 2 = 2 .

Отметим, что при перемещении точки х от точки х* до точки хр значение Я(х,В) растёт от Я(х*,В) до Я(хр,В), значение р(х, и) пробегает значения от р(хи) до р*. Соответствующее значение радиуса растёт от

г = Я(х*,Б)+р(х* ,П) до Я(хр,В)+р* = I 2 2 'Р'

5) Случай г ^ гР.

Для точки хр имеем (см. рис. 3.5)

Яр(хр, и) = {х4,Х5,Хб}, дР_(хр, В) = {уг,у2,уз},

Рис. 3.5. Решение задачи при г ^ гР.

где точки х4, х5,х6 - проекции точки хр на стороны [х\, х3], [х\, х2] и [х2, х3], а уг = \^-хр\\, г = 4, 5,6.

Таким образом 02 € Р(хр,0) и следовательно по теореме 3.1, точка

Хр €

Сф(г) для любого значения г ^ гр. Далее в разделе 5 (см. теорему 5.3) будет доказано, что в двумерном случае решения задачи (1.1) для г € [г+,г— всегда является единственным. Поэтому можем сделать вывод, что в данном случае решение является единственным для любого г ^ 0.

Таким образом, вся совокупность решений задачи (1.1) для различных значений г ^ 0 представляет собой два отрезка с общей точкой х*:

\^Оф(г) = [хр, х**] и [х*,хр]. С ростом радиуса г точка х(г) перемещается из точки хр в точку х* по

отрезку [хр,х*], а затем в точку хр по отрезку [х*,хр], причем

1 хр, если г € [0,гр], х(г) = '

хр, если г ^ гР,

. . , ( R(x*,D) + p(x*, tt)

x(r) E (xR, x ), если r E I rR,-^-

.. . (R(x*,D) + p(x*, tt) N

x(r) E (x , xp), если r El -^-,rP

R(x*, D) + p(x*,D) x(r) = x , если r =---.

4 Вариационные свойства решения

1. Рассмотрим функцию

f (r) = min ф(x,r). (4.1)

Функция f (r) выражает поведение оптимального значения целевой функции задачи (1.1) с ростом r на положительной полуоси.

Функция f (r) на отрезке [0,r+] и при r ^ r— ведёт себя как линейная, а именно верна

Теорема 4.1. [17] Функция f (r) является конечной выпуклой на R+ функцией, причем

V - r, если r E [0,r$. f (r) = { R(4.2)

r — p*, если r ^ rp.

Простым следствием теоремы 4.1 является Следствие 4.1. 1. Справедливо включение

Arg min f (r) E [r+, r—]. (4.3)

r>0

2. Для производных по единичным направлениям

Пг, —!) = цт ?(г + Аг) — /(г); Г(г, 1) = 1т ^(г +Аг) — ^(г)

^ у д^0 Аг у Дг|0 Аг

имеет место оценка

\/'(г, ±1)\ < 1, Уг ^ 0. (4.4)

Отметим, что функции Р(х,В) и Я(х,В) для любого х Е Сф(г) при фиксированном г Е [г+, г—] принимают фиксированное значение и верно Следствие 4.2. [18] При любом фиксированном г Е [г+, г— выполняется

Я(х, В) = /(г)+ г, Р(х, В) = /(г) — г, Ух Е Сф(г). (4.5)

Кроме того, имеет место монотонность соответствующих значений этих функций с ростом г.

Список литературы диссертационного исследования кандидат наук Осипцев, Михаил Анатольевич, 2017 год

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

1. Абрамов О. В., Здор В. В., Супоня А. А. Допуски и номиналы систем управления. М.: Наука, 1976.

2. Авдеева Л.И., Зуховицкий С.И. Линейное и выпуклое программирование. М.: Наука, 1964.

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

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

5. Бронштейн Е. М. Аппроксимация выпуклых множеств многогранниками// Совр. математика. Фундам. направления. 2007. Т. 22. С. 5-37.

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

7. Васильев Ф. П. Методы оптимизации М: МЦНМО, 2011.

8. Гороховик В.В. Выпуклые и негладкие задачи векторной оптимизации. М.: Либроком, 2012.

9. Грюнбаум Б. Этюды по комбинаторной геометрии и теории выпуклых тел. М.: Наука, 1971.

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

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

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

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

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

15. Дудов С. И. О задаче фиксированных допусков. //Ж. выч. матем. и матем. физ., 1997, Т. 37, №8, С. 937-944.

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

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

18. Дудов С. И. Систематизация задач по шаровым оценкам выпуклого компакта.// Математический сборник, 2015, т. 206, № 9, С. 99-118.

19. Дудов С. И., Дудова А. С. Об устойчивости решения задач о внешней и внутренней оценке выпуклого компакта шаром // Ж. выч. матем. и матем. физ., 2007, Т. 47, № 10, С. 1657-1671.

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

21. Дудов С. И.,Мещерякова Е. А. О методе приближённого решения задачи об асферичности выпуклого тела // ЖВМ и МФ., 2013, т. 53, N 10, с. 1668-1678.

22. Иванов Г.Е. Слабо выпуклые множества и функции. М: ФИЗМАТ-ЛИТ, 2006.

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

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

25. Каменев Г. К. Метод полиэдральной аппроксимации шара с оптимальным порядком роста мощности гранной структуры.// Ж. вы-числ. матем. и матем. физ., 2014, Т. 54, № 8, 1235-1248.

26. Каменев Г. К. Асимптотические свойства метода уточнения оценок при аппроксимации многомерных шаров многогранниками.// Ж. вы-числ. матем. и матем. физ., 2016, Т. 56, № 5, 756-767.

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

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

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

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

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

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

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

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

35. Половинкин Е.С. Многозначный анализ и дифференциальные включения. М.: Физматлит, 2014.

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

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

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

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

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

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

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

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

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

45. Barany I. On the minimal ring containing the boundary of convex body // Acta Sci. Math. (Szeged). 1988. V.52. №1/2. P.93-100.

46. Bonnesen T. Uber das isoperimetrusche Defizit ebener Figuren // Math. Ann. 91(1924). S.252-268.

47. D'Ocagne M. Sur certaine figures minimales // Bull. Soc. Math. France. 1884. V.12. P.168-177.

48. Dudov S.I., Zlatorunskaya I.V. Best approximation of a compact convex set by a ball in an arbitrary norm // Advances in Mathematics Research. 2003. V.2. P.81 - 114.

49. Hiriart-Urruty J.B. Tangent cones. generalized gradients and mathematical programming in Banach Spaces. Math. Oper. Research, 4(1): 79-97, 1979.

50. Hiriart-Urruty J.B. New concepts in nondifferentiable programming. Bull. Soc.Math. France Mem., 60 (1979), 57-85

51. Kriticos N. Uber konvexe Flachen und einschlissende Kugeln // Math. Ann. 1927. V.96. P.583-586.

52. Kurzhanski A.B., Valyi I. Ellipsoidal calculus for estimation and control. Boston: Birkhauser, 1997. 100

53. Lebesgue H. Sur quelques questions de minimum, relatives and courbes orbiformes, et sur leurs rapports avec le calcul des variations // J. Math. Pures Appl. 1921. V.4. p.67-96.

54. Vincze St. Uber den Minimalkreisring einer Eiline // Acta Sci. Math. (Szeged). 1947. V.11. №3. P.133-138.

55. Vincze I. Uber Kreisringe, die eine Eiline einschlissen // Studia Sci. Math. Hungar. 1974. V.9. №1/2. P.155-159.

56. Zucco A. Minimal shell of a typicall convex body // Proc. Amer. Math. Soc. 1990. V.109. №3. P.797-802.

57. Осипцев М.А., Дудов С.И. О шаровой оболочке наименьшего объема для границы выпуклого тела // Матер.межд.Казанской летней научной шк-конф., Казань: Казан.ун-т, 2013., Т.46. С.183-184.

58. Осипцев М.А., Дудов С.И. О наименьшем по объему шаровом слое, содержащем границу выпуклого тела // Математика. Механика: Сборник науч. Трудов Саратов: Изд-во Сарат. ун-та, 2013, Вып .15, С.59-61.

59. Осипцев М.А., Дудов С.И. О равномерной оценке выпуклого компакта шаром фиксированного радиуса// Соврем.проблемы теории функций и их приложения. Мат.17-й межд.Сарат.зимней школы. Сара-тов:ООО Изд-во «Научная книга», 2014. С.201-203

60. Osiptsev M.A., Dudov S.I. Uniform estimate of a convex compact by a ball with fixed radius // Комплексный анализ и его приложения. Мат^П Петрозаводский международной конференции, Петрозаводск: Изд-во ПетрГУ. 2014. С. 42.

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

ного радиуса // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2014, Т. 14, вып. 3, Часть 2, С 267-272.

62. Осипцев М.А., Дудов С.И. Об устойчивости по функционалу решения задачи о наилучшем приближении выпуклого тела шаром фиксированного радиуса // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2015, Т. 15, вып. 3, С. 273-279.

63. Осипцев М.А., Дудов С.И. Оценка устойчивости по функционалу задачи наилучшего приближения выпуклого тела шаром фиксированного радиуса // XII Международная Казанская летняя школа-конференция "Теория функций, ее приложения и смежные вопросы" , Казань: Казан.ун-т, 2015, Т.51, С.182-184.

64. Дудов С.И., Осипцев М.А., Об устойчивости решения задачи о равномерной оценке выпуклого тела шаром фиксированного радиуса // Соврем.проблемы теории функций и их приложения. Мат.18-й межд.Сарат.зимней школы. Саратов:ООО Изд-во «Научная книга», 2016, С. 127 -131.

65. Осипцев М.А., Дудов С.И. Случай редукции задачи о равномерной оценке выпуклого тела шаром фиксированного радиуса к задаче линейного программирования // Соврем.проблемы теории функций и их приложения. Мат.18-й межд.Сарат.зимней школы. Саратов:ООО Изд-во «Научная книга», 2016, С. 202-204.

66. Осипцев М.А., Дудов С.И. Об устойчивости решения задачи о равномерной оценке выпуклого тела шаром фиксированного радиуса // Ж. выч. матем. и матем. физ., 2016, Т. 56, № 4, С. 29-44.

67. Осипцев М.А. О сведении задачи о наилучшем приближении выпуклого тела шаром фиксированного радиуса к задаче линейного про-

граммирования // Геометрический анализ и его приложения Мат. III межд. школы-конф. Волгоград: ВолГУ, 2016, С. 154 -157. 68. S. Dudov, M. Osiptsev. Uniform Estimation of a Convex Body by a Fixed-Radius Ball// Journal of Optimization Theory and Applications, 2016, V. 171, № 2, pp. 465-480.