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

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

Дудова Аиастагля Сергеевна

ХАРА КТЕРИЗЛДИЯ УСТОЙЧИВОСТИ РЕШЕНИЯ ЗАДАЧ О ВНЕШНЕЙ И РАВНОМЕРНОЙ ОЦЕНКЕ ВЫПУКЛОГО КОМПАКТА ШАРОМ

Ql.01.00 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Сарапш 21НЮ

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

Научный руководитель - заслуженный деятель пауки РФ,

доктор физико-математических наук, профессор Хромов Август Петрович.

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

профессор Розен Виктор Владимирович, кандидат физико-математических наук, доцент Папшев Сергей Владимирович.

Ведущая организация - Центральный эконом и ко-ыате матн чос кий

институт РАН

Защита состоится 21 декабря 2006г. в 15.30 на заседании диссертационного совета 212.243.02 в Саратовском государственном университете им. Н. Г.Чери ыш евс кого по адресу: 410012, г.Саратов, ул .Астраханская, 83.

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

Автореферат разослан " ноября 2000г.

Ученый секретарь дисссртационного совета, кандидат физико-математических наук, доцелт

В.В. Коснев

Актуальность темы. Исторические сведения. Интерес математиков к оценке и аппроксимации достаточно сложных мисскесгв множествам в простой 1'еометрическоВ структуры возник очень давно (см. напр. моно графии Т.Боннеэеиа н В.Фенхеля1, Л.ФЛЬта3 и библиографии в них). Это направление активно поддерживается сейчас в рамках негладкого анализа и не дифференцнруемой оптимизации, основы которых заложены в трудах Р.Т.Рокафеллара, Б ,Н .П ше ни чного, В.Ф.Демьянова, А.М.Рубинова, Ф.Кларка, Ж.-П.Обеиа, И.Эклавда, В.ТЛоляка, М.С.Никольского, Е.С.Поювинкина и других математиков. Именно негладкий анализ дает эффективные необходимые математические инструменты для успешного исследован ия таких задач.

Задачи но оценке множеств находят обширные приложения в «стс-ствшнанин, в том числе и п самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (напр., работы А.Б. Куржанскот, Ф.Л.Чериоусько). Можно также указать на работы по внешним и юиутренннм оценкам заданных множеств ориентированным« параллелепипедами и их приложениям3. Е.С. Половин кипы и4 рассматривались внутренние и внешни» многогранные аппроксимации выпуклых множеств.

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

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

'Вишен Т., 1ЪисЫ IV. ТЬепгу Лег копусхеп Когр*г, ВегЦп: Брйпеег-УяЬб, 185*.

Л.Л. Ржошкквип па влоеюхта, в» еффе к ■ проярмктод.Ш №яш ЛКЭМАТЛИТ,

1Э».

*А/>|*яол О В., Здгф В.В., Огп»ш А. А. Далуаи я мам—«дм СИСТЧ'У уорашими. П.; Падко, 1979.

•Поливиииш Е.С., Вменив М.В. Элементы вьп^лвгои шли» ыиухлага »шимэл. М.: ФИЗмат Л ит, ахи

выглядит следующий образом.

Пусть И С № заданный компакт нз конечномерно го действительного пространства Иа функция п(х) удовлетворяет* »а № аксиомам нормы. ТЬгда задача о внешней оценке компакт» £) шаром нормы п(ж) может быть записана в виде

Я(х) = пмхп(* - у) пня. (1)

Значение функции Л(х) выражает радиус наименьшего шара с Центром в также х, содержащего в себе компакт £>. Точка х*, доставляющая минимальное злдчеяие функции является цешром искомого опи-

санного радиуса, а Л* = Л(#*) - радиус этого шара.

Известно1, что для случая, когда я(х) = ¡]х|| - евклидова норма, 1*;-шснке задачи (1) единственно. При этом центр опишипого шара принадлежит выпуклой оболочке точек, одновременно принадлежащих границе компакта О и поверхности описанного шара. Верно и обратное, а именно, шар, содержащий компакт и обладающий указанными выше точками на его границе, есть описанный шар.

Для случая произвольной нормы (и даже, когда вместо нормы используется функция Мяншвского выпуклого тепа, содержащего пулевой элемент) задача (1) рассматривалась Б.Н.Пшеничным*. Иы получена формула субднф4>срспцнала функции Л (г), которая является выпуклой на И", и на этой основе сформулировано необходимое и достаточное условие решения.

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

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

£>,) < е.

'ПикннчныА Б.Н, ВифииЛ шпз ■ вшпреыдлъные эядак.М^ Пдухл, 11)81).

Здесь £ > О - известная погрешность задания компакта D, а Л (Л, В) — гаах {s«p in Г n(a — b), sup inf п(а — Ь)}

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

И, таким образом, о решении нос одной задачи (1) мм можем судить по решению приближенно!! задачи

ILlx) = maxnfa: — и) —У min. (2)

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

Отмстим, что любая норма является выпуклой функций на всем пространстве R*. Поэтому, легко видеть, и функция также выпукла па КЛ Следовательно задача (1) является задачей выпуклого программирования. Известно0, что вопрос о характеризации устойчивости легко 1>ешается, если целевая функция является сильно выпуклой. Однако ни при каких условиях ид компакт D я используемую норму «{■) функция Л(л^) но является сильно выпуклой не только на но и любом выпуклом мпожест&е с непустой внутренностью. Именно это обстоятельство затрудняет иссдпдонапие устойчивости зяда'ш (1).

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

Пусть D C.W- непустой выпуклый компакт, В(х, г) - евклидов шар с центром в точке х и радиусом г, h(A, В) - расстояние Хаусцорфа между множествами А н В в евклидовой норме. ТЬгда задачу о равномерной окрике (наилучшем приближении) выпуклого компакта D евклидовыми шарами в метрике Хаусдорфа моисно записать в виде

(3)

ЧДЛ(»,г ) mm .

'Кирцшсй ВТ. nmiptuiiiipcBOBiu. Ll_: tt»n, 1980.

Задача (3), как частный случай более общей задачи, рассматривалась а работе М.С. Никольского и Д.В.Силинат, где установлен ряд интересных свойств се решения. Важным обстоятельством оказалось то, что прнгр шара наилучшего приближения для компакта D в задаче (3) является одновременно единственным решением задачи

R(z) - рп(:с) min. (4)

Здесь

Л(х) = пшх|(л:-1гЙ1 рп(х) = Ц* - Л П = »А Я.

При этом радиус шара наилучшего приближенна есть rt> — +

Задача (4) о построении шарового слоя иаименьшей "толщины содвр-жаи<его i-раннцу выпуклого компакта, известна давно1. Впервые близкая но постановке задача рассматривалась в работе М.Д'Оканя5, где был предложен оюсоб построения кругового кольца наименьшие В ширины, содержащего заданное конечное семейстио точек. А.Лебегои* рассматривалась задача, которая сводилась к построению кольца наименьшей "толщины содержащего границу 2-мерного выпукла го множества. Позднее Т.Вонисзен10 для задачи на плоскости и Н.Крнтикос11 для задачи п трехмерном пространстве получили необходимое н достаточное условие решения и доказали единственность решения, £>гн же вопросы для за^чи (4) в щюеграистве произвольной |>азмерносга р были решены средствами выпуклого анализа только в 1988 году в работе И .Бараньи12. Были и другие работы, касающиеся свойств решения задачи (4), однако вощюс об устойчивости решения но затрагивался.

TJIuKMbi*i4 М С., Скяч ДВ. О nwJviQi (цибян^нш шц^ла» ыипип sjuueurtmi «ляияа// Твудл маткн. hhciht7t> »и.НА. Стшлова. 1Р94. Х211, с-Мв-ЗМ.

*OOacn> M. Sur «naine ^шшШш!« //BuIL Soc. Math. v.1Z P. 165-177.

*l*b«gue H. Sut iiadim qaaUon Banian*», wUiivi* tu) cmiiIhi «Шли*, et n lem HLpport« «tec 1« afcul dm variation //J. khib.Puiwi Apfi. 1921. V.4. pdT-tKL "Вошквеп T. tlbcr du »(игжпеййкЬе De&ril cbaxr Firuirn //Math.Aaa. fl (1024) 8-212-200. "KiiiicoaN. lit** konve» Fkchea uad (ШасШкешЬ //Matb.Àm. 1027. V.fa. p.5s3-ssîl

"Biraiigr lOnttc iniJianJ ring ccntalnlrç tte botudaiy uf ctmvta ЪаЛу// Act» $d- Math. (Swp«J). 19». V il Ml/3. Р9Э-1С0.

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

для случаев строга- и сильно выпуклого множества Л (или когда А -дополнение таких множеств) и строго- и сильно квазивыпуклой нормы «(•). функции Ф(аг) = Щх) ~ра(х).

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

Научная новизна. Приведенные в диссертации результаты являются

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

• установлены свойства строго- н сильно квазнвыпуклых норм, функции А(х) и функций расстояния ¿>о(г) и рп(х), для случаев строго-н енлыю выпуклого множества £) и строго- и сильно квазивыпуклой нормы, в (|юрме, позволяющей сравнивать их поведение на отрезках с соответствующим поведением строго- или сильно выпуклых (вогнутых) функций;

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

, • подучены оценки сверху и снизу для производной по направлению функции расстояния при некоторых ограничениях па выбор направления;

• Дана характср|гищ1и[ устойчивости

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

- задачи (3) по радиусу и центру шара наилучшего приближения,

относительно погрешности оцениваемого (приближаемого) выпуклого компакта.

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

Апробация работы. Результаты диссертации апробировалось на 12-ой н 13-ой Саратовских зимних школах "Современные проблемы теории функций и их приложения"(Саратов, январь-февраль 2004, янпярь-феврпль 2000), па школе-конференции "Теория функций, ее приложения н смежные вопросы "(Казань, нюнь 2005), на научных семинарах СГУ но негладкому анализу, на научном семина[>е ка<1>едры дифференциальных уравнений и прикладной математики под руководством про-4>ессора А.П.Хромова, на объединен но м семинаре по дискретной математике и математической кибернетике под руководством профессора Д .В.Сперанско го.

Публикации. Ооювнме результаты опубликованы в ¡заботах, список которых приведен в конце авторе»^играна.

Структура диссертации. Работа состоит из двух глав, содержащих 11 л&рафафов и списка литературы (40 иаимешваний). Общкй обплм диссертации 107 страниц машинописного текст.

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

Первая глава дпоссртанут содержит §§1-0, ее главная цель - характе-

ризация устойчивости задачи (1) о внешней оценке.

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

Б §3 приводятся вспомогательные факты, главные из которых касаются свойств строго и сильно к вази выпуклы* норм. Понятие строго квазивыпуклое нормы, как нормы, шар которой является строго выпуклым множеством, не пол ьэоеа лось и випуктм анализе и ранее. Понятие г-шлыю квазивыпуклой нормы вводится впервые.

Определение I4. Множество Л С1' называется г-сильно выпуклым, сели око представили) в виде пересечения евклидовых шаров радиуса г.

Определение 2. Будем говорить, что норма п(-) является г-силыш квазивыпуклой, если ее шар единичного радиуса является г'Сильно выпуклым лшожеством.

Следующий факт позволяет сравнивать поведение таких норм на отрезках с поведением сильно выпуклых функций.

1 Лемма 2.8. ВЫи п(*) является г-сильно ххшл1чыпуклой нормой, то для любых точек XI м Хг, опмичкш; та Ор, « а б [0,1] выпмняется неравенепшо

»(ал + (1 — а)«а) £ ая{®1) + (1 — а)п(зй)—

Gia(l — «)«(»! )ti(j!a)

«2

и («О

2г(ап(ж1) + (1 - а)п(ж2)) где хонепшнта С\ - подомаипельиая ктстанта, для которой

< п(ж), Ых € К". (5)

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

Лемма 2.0. Если единичный шар норлш п(-) «л«сет вид

Вп(0р,1)=Оп(а,г),

где В [а, г) - евклидов шар с центром в точке а « радиусом г, А • етш< мстричный относительно 0Р хомпаюп и Л с 1'п<Б(0р,г), то саму норма можно выразить следующей формулой

. , _ |< «,» >| + а,х >< +Цх|Р(г» - ||а|Р) «(*} - ш®-г»-|в|"-"

й

В |3 исследуются свойства функции Л(а:), являющейся целевой функцией в экстремальной задэте (1). Важным для характеризацни устойчивости решения является следующий факс

ТЬорема 3.1. Если «(•) является г-сильно квазивыпуклой нормой, то Дня любых XI и хг из Л", а € (0,1) най&апся точка

йгбЯ»:|»1-||шЛ(в1), «ЯМ)

такал, что выполняется неравенство

Щах1 + (1 - а)**) < аЛ(жд) + (1

<?1а(1 - аОЛ(хО Л(>;2)

Щ-Уа *г-Уа

Я(*1) Щх2)

2г(аЛ(*0 + (1-«)Л(*2)) где Сь - помокителымя константа, Лш квторой выполняется неравенство ($).

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

Нижние лсбеюты множества функции />о(ж) характеризует

ТЪорема 4.3. Если О яеляапся старого еыпг/кльи» мнознхягьвам, а п(-) • строго квазивыпуклой нормой, та Оля любого А > 0 множество 0(Х,й) = {х е К": < А) является строго выпуклым.

Теорема 4.5. Пусть О • строго выпуклое лтоокеетео, а п(-) - строго квозивътухмш норма. Если точки и а^ ш Ш" у&юлетворяют мера-

венстау

Ра(х|) < ро{*2) < +«(*! - ¡г»),

причем т3 $ О, то Им любых а € (0,1) выполняется

рп{<*Х1 + (1 - < арв(х1) + (1 - а)рд(ж}).

Нижеследующие факты говорят о том, насколько усиливаются соответствующие свойства функции рй{х)л если О - сильно выпуклое множество, а «(•) - сильно квазнвыпуклая норма.

Теорема 4.6. Если I) является т\ -сильно выпуклым множествам, а »>(■)— га-м(лын» квлэткшпуи^лой иорлшй, то для любого А > О лто же.ство в(А, Р) является (г* + Лг2) -сильно выпуклым.

ТЬорема 4.9. Пусть О - г г-сильно выпуклое множество, «(■) - гг сильно квазивыпухлая норма, в точки х\ и »а таковы, что

~ = Р> 0, [х,, «а) П О ш 0.

Тогда для всех змач'мнв а е [0,1) справедливо недоемство

М***1 + (1 ~ <>)*?) <Р-~

где С\ - положительная константа, Аля которой выполняется неравенство (5).

Поведение (функции /ч>(аг) на множестве I), <жлн оно является сильно выпуклым, сравнимо с поведением сильно вогнутой функции.

ТЬоромя 4.10. Пусть О является г'Сильно выпуклым множеством. То*да д.яя любых точек и х? гц О таких, что д^'О ш Ра^з) 5= р и любых значений а € [0,1] выполняется неравенство

ра{<*1 + (1 -<*)*г) £ Р+СМ1~а)\\*1 -

Следует отмеггитц что важную роль в исследовании свойств функции н функции расстояния, касающихся случаев с сильно выпуклым множеством В или сильно квазипыпуклой нормой, сыграли <}>акты из сильно выпуклого анализа'1.

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

ТЬорема 5.1. ТЪчка х* является решением задачи (I) тогда и только тогда, когда для любого А > Л* = min {Л (г) : х 6 If} ома является центрам влоокенпого в множеапво GR(А) = {ïêKp: < А } ша/и наибольшего радиуса, тп есть peuteitucM задачи

да Iii (ж) « min n(® — tf) —» m ах , где iï(A) — Ш»'\СЯ(А). При этом радиус влооксиного шара есть

/*1{ц(з*) - A -iî*.

Именно этот критерий был в дальнейшем использован при характе-ризации устойчивости центра описанного шара.

Теорема 5.1 является самым сложным по доказательству результатом первой главы.

Основным в первой главе является §0, где собраны и доказаны факты, касающиеся устойчивости решения задачи (1).

Выяснилось, что устойчивость задачи (1) по оптимальному значению целевой функции Щх) имеет место всегда, причем для

Я' = mhi Л(х), Щ = ш ад,

справедлива

Теорема в.1. РЫеет место н<равеиетао

где a Ci - паложытеяьиал константа, для которой

«(*)<СУМЬ Vi ей". (6)

Каждому выпуклому компакту D, как элементу пространства всех выпуклых компактов , можно сопоставить X(D) - множество |*s-

шеннй задачи (1), то есть множество центров описанных шароа. Поэтому

можно рассматривать многозначное отображение

Elu характеризует

Теорема 6.2. Многозначное отображение Х(-) является пааунепрс-¡твным cecpœy eewjj/ на

Приведенный пример G.1 говорит о том, что в некоторых ситуациях многозначное отображение Х{<) может не обладать свойством полуне-н|>ерывностм снизу. Другими словами не все ]>ешеш1я точной задачи (1) янлякггея предельными точками решений приближенных задач (2) при е|0.

Основным результатом главы является

Теорема 6.3. Пусть п(-) является г-енлъио юваэивыпуклай hojimoû. Если точка х* является решением задачи (1), а точка хс - решением ааНичи (2), то c.npaee.ài%uaù неравенство

«te Ci и Cz - полоскательные константы, для коггюрых «mhiuiumiikji неравенства (5) и (б) соответственно,

Рто]]ця глава диссертации состоят из §7-11, ее цель - характер m ацня устойчивости задачи (3) о равномерной оценке.

О §7 дается постановка этой задачи и приводятся пекогоне (¡юрмулн-ррвки результатов ж работы7 M .С. Никольского и Д.Б.Силина, которые в значштшыюй мере далее исполняются.

В §8 приводятся свойства вспомогательной функции

Jîo{:s) = шахЦж -

где А» = S(xItiÍ(iíi))nB(*3) для произвольно выбранных точек Xi -ф х2. Показано, что функция Лр(*) ведет себя па отрезке как

сильно выпуклая функция, а точнее, имеет место

Лемма 8.2. Для любого а € [0,1] выполняется

+ -а)хг) =

» аЛ^) + (1 - - а(1 - л)!!®! - ^Н2.

Поводите самой функции иа отрезке жа] отражает Лемма 8.3. Для любою а £ [0,1] выполнял тел

+ (1 - а)*») < вДо(г1) + (1 - «)Ло(х2)-

а(1 - - *2Ц3 - (Яо(*0 - До(^))2) 2(аДо(х1) + (1 -а)Щх2)} Известно13, что функция расстояния рл(х), в случае использования евклидовой нормы, является дифференцируемой по любому направлению а точках ж £ А. В §Е> получены верхняя и иижиня оценки дня производной по направлениям функции расстояния

= + - /»«(г))

для О = Жр\£> при некоторых условиях на выбор направления д е Ж". Лемма 9.1. Пусть рп(х~) в р > О « точка у С. О такооа, что — КД = Л > р. Справедливы следующие утверждения: а) Если единичный вектор д еН' таков, что ^ х-у р

б) Еслн единичный вектор д £ Н.р таков, что $ > то

С помощью леммы 9.1 в §10 получена оценка снизу для п рою водно В по направлению функнрш Л(х). 'ЗДшьяне* ИФ, Ёкнлм* Л В Нсмффс^Ёцир^им аетиийацые-Мл Нлухл. 1081.

Лемма 10.2. Если точка х0 является решением задачи (3) и при этом шШ ^ 0, то для любого д 6 Нр, Цз]| = 1 выполняется

¡ПШ+РяШ

Лемма 9.1 использовалась также при получении важной оценки спиду для производной по направлениям функции Ф(х) — Л(х) — являющейся целевой функцией в экстремальной задаче (4).

Теорема 10.1. £Ьли {п10 -ф 0, точке х £ тШ, а единичное направление з е М* таково, что

W

то

Теорема 10.2. Пусть Df - выпуклый код такта, такой, что

h(D,Dt)Se,

где е > 0. Если точка хо - решение задачи (S), a xt - petiieitue приближенной задачи

h(Dt,B(x,г))-> (7)

то справедливо неравенство

Подученные в §5-Ю вспомогательные факты иенешьзо вались в §11 для решения главного вопроса • характериэации устойчивости центра и радиуса шара наилучшего приближения задачи (3). В предположении, что выпуклый компакт D отличен от евклидова шара и не вырождается в точку доказана

ТЪорема 11.1. Пусть х0 - центр шара наилучшего приближения в ■задаче (3), a Xf - в приближенной задаче (7). Тогда справедливо асшт-тотичсское неравенство

IK-X.HS4ам-i 2£(1+о(1»

Щхо) -ра(хоУ

где о(1) —0 при с ± 0.

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

Теорема 112. Если го - радиус шара наилучшего приближения в задаче (3), я г, ■ в прибли&ссннной задаче (7), то справедливо асимптотическое неравенство

где о(1) -4 0, е 4- О,

Автор выражает глубокую признательность про^ккхюру А.П.Хромову за помощь и внимание к работе.

ПЕЧАТНЫЕ РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Дудопа A.C. Об устойчивости задачи о внешней оценке компакта шаром произвольной нормы // Tfea. докл. 12-ой Саратовской зимней школы. Саратов. Изд-во ГЬс УНЦ "Колледж 2004, с.75-76.

2. Дудова A.C. Об устойчивости решения задачи внешней оценки компакта шаром произвольной нормы // Математика. Механика: Сб. научн.тр. - Саратов: Изд-во Овраг, ун-та. 2004. - вып.0. С-54-50.

3. Дудова A.C. Об аппроксимации выпуклого компакта многогранником //Материалы 7-й междунар. Казанской летней научной школы-конференцни. Казань: Изд-во Казанского матем. общества, 2005,

с. 08-69.

4. Дудова A.C. Об аппроксимации выпуклого компакта многогранником //Математика. Механика: Сб. научн. тр. - Саратов: Изд-во Сарнт. ун-та. 2005.- вып.7. с.45-47.

5. Дудопа A.C. Об одном критерии решения задачи о внешней оценке компакт» шаром }j Thi. докл. 13-ой Саратовской зимней шкалы. Саратов. Изд-во "Научная книга 2000, с.65-00.

0- Дудова A.C. Об устойчивости решення задачи наилучшего приближения выпуклого компакта шаром // Изв. вузов. Математика. - 2000, №7, с. 25-33.

Сдаповнабор 16.11.2006 Пгуушсапо в печать 01.11.2000

Формат 60x84 1/10. Печать о<|«егная,

Бумага офсетная. Усл.печ.л. 1,0 пл.

Тираж 100 экз. Заказ №187. Цена договорная

Отпечатало и ИАП РАН 410012, Саратов, ул. Московская, 94

Введение.

Глава 1. Задача о внешней оценке компакта шаром произвольной нормы.

§1. Постановка задачи о внешней оценке, вспомогательные сведения.

§2. Свойства строго и сильно квазивыиуклых норм.

§3. Свойства целевой функции R(x).

§4. Свойства функции расстояния до строго и сильно выпуклого множества.

§5. Критерии решения задачи о внешней оценке.

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

Глава 2. Задача о равномерной оценке выпуклого компакта евклидовым шаром.

§7. Постановка задачи о равномерной оценке, вспомогательные сведения.

§8. Свойства вспомогательной функции Rq(x).

§9. Оценки для производной но направлениям функции расстояния.

§10. Свойства целевой функции Ф(х).

§11. Характеризация устойчивости решения задачи о равномерной оценке.

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

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

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

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

Задача о наилучшем приближении (равномерной оценке) в метрике Хаусдорфа выпуклого компакта евклидовым шаром была поставлена и изучалась в работе М.С. Никольского и Д.Б. Силина [12].

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

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

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

R(x) = тахп(ж — у) —> min. (0.1) yeD хек?

Значение функции R(x) выражает радиус наименьшего шара с центром в точке х, содержащего в себе компакт D. Точка х*, доставляющая минимальное значение функции R(x), является центром искомого описанного шара, a R* = R(x*) - его радиус.

Известно([2]), что для случая, когда п(х) = ||х|| - евклидова норма, решение задачи (0.1) единственно. При этом центр описанного шара принадлежит выпуклой оболочке точек, одновременно принадлежащих границе компакта D и поверхности описанного шара (то есть его граничной сферы). Верно и обратное, а именно, шар, содержащий компакт и обладающий указанными выше точками множества D на его границе, есть описанный шар. Следовательно центр описанного шара всегда принадлежит выпуклой оболочке компакта D.

Диаметр компакта D d* = max Цж — % x,yeD и радиус описанного евклидова шара R* связаны неравенством, полученным Г. Юнгом (см. [И, с.73]).

R* < 4/ , Р „сГ.

2(р+1)

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

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

Здесь е > 0 - известная погрешность задания компакта D, а h(A, В) = max{sup inf п(а — b), sup inf n{a — 6)} сел ьев icii аел

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

И, таким образом, о решении задачи (0.1) мы можем судить по решению приближенной задачи

R£(x) = та.хп(х — у) min. (0.2) yeDt xGRp

Получение условия устойчивости и оценка характера устойчивости задачи (0.1) относительно оптимального значения целевой функции R(x) и центра описанного шара - один из вопросов, решаемых в диссертации.

Любая норма, как следует из ее аксиом, является выпуклой функцией на всем пространстве. Поэтому, легко видегь, и функция R(x), являющаяся результатом операции максимума от выпуклых функций, также выпукла на Следовательно задача (0.1) является задачей выпуклого программирования. Известно (см. [10, с.42]), что вопрос о характериза-ции устойчивости задачи выпуклого программирования легко решается, если целевая функция является сильно выпуклой ([3, с. 181]). Однако ни при каких условиях на компакт D и используемую норму п(-) функция R(x) не является сильно выпуклой не только на W, но и любом выпуклом множестве с непустой внутренностью. Именно это обстоятельство затрудняет исследование устойчивости задачи (0.1).

3. Приведем математическую формализацию второй задачи, исследуемой на устойчивость решения.

Пусть D непустой выпуклый компакт из ЕУ', h(A, В)- расстояние Ха-усдорфа между множествами А и В в евклидовой норме,

- евклидов шар с центром в точке х и радиусом г.

Тогда задачу о наилучшем приближении эюго выпуклого компакта D евклидовыми шарами в метрике Хаусдорфа можно записать в виде h(D, B(x,r)) -> min . (0.3)

4 4 " хеш, г>о 4 '

Задача (0.3) впервые была поставлена и рассматривалась в работе М.С.Никольского и Д.В.Силина [12]. В ней доказаны существование и единственность решения, получено необходимое условие решения. Отметим, что задача (0.3) рассматривалась авторами [12] в рамках более общей задачи о наилучшем приближении элемента пространства непустых выпуклых компактов с метрикой Хаусдорфа элементами его подпространства, которое представляет собой всевозможные линейные комбинации фиксированного набора элементов данного пространства. Очень важным обстоятельством, установленным в [12], оказалось то, что центр шара наилучшего приближения xq для компакта D в задаче (0.3) является одновременно единственным решением задачи

R(x)~pn(x) min. (0.4) xei)

Здесь

R(x) = max||a? - y\\, pn{x) = min \\x - г/||, ft = W>\D. yeD ye fi

При этом радиус шара наилучшего приближения есть

ЯЫ + РпЫ ro =-J-' а кроме того

• ит Pit \\ RM ~ min h[D, D [х. г)) =---. xe№,r>o v ' v ' JJ 2

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

Задача (0.4) о построении шарового слоя наименьшей толщины, содержащего границу выпуклого компакта D известна давно. Впервые близкая но постановке задача рассматривалась М.Оканем в [25], где был предложен способ построения кругового кольца наименьшей ширины, содержащего заданное конечное семейство точек. А.Лебегом в [2G] рассматривалась задача о построении кольца "наименьшей толщины содержащего границу 2-мерного выпуклого множества. Позднее Т. Боннезен и [27] для задачи на плоскости и Н. Критикос в [31] для задачи в трехмерном пространстве получили необходимое и досипочное условие решения и доказали единственность решения.

Свойства минимального по ширине кольца, содержащего границу двумерного выпуклого компакта изучались в связи с другими экстремальными задачами по оценке того же компакта (см. [29]-[32]). Так в работе I.Vincze ([30]) оценивается соотношение минимального радиуса круга, содержащего выпуклый компакт D С 3R2 и внешнего радиуса кольца "наименьшей толщины содержащего границу компакта D, а также соотношение максимального радиуса круга, содержащегося в D, и внутреннего радиуса кольца "наименьшей толщины". Получены следующие оценки

Для задачи (0.4) в пространстве произвольной размерности р необходимое и достаточное условие было получено уже в 1988 в работе I.Barany ([32]). Заметим, что в этой работе существенным образом были задействованы средства выпуклого анализа. Дело в том, что функция R(x) является выпуклой на всем пространстве Rp, а функция рп(х) - вогнутой

D. mm{R(x) :xGD] л/3 r{xq) maх{рп{х) :хе D} < РпЫ)

2. на выпуклом компакте D. Поэтому целевая функция Ф(ж) = R{x) —рп(ж) задачи (0.4) является выпуклой на D.

В работе [32] также доказано, что при р > 3 имеет место точная оценка: min {R(x) :х е D] ^ 1, * „ 1 N

- п/ ч-- > ~(cos а0 + cosа0 - Н--),

R{x о) 2 cosa о где ао € [0,7г/2] и является решением уравнения sin2 а — 2 cos3 а = 0, а величина тах{/зп(ж) : х 6 D] Рп(х о) может быть сколь угодно большой.

Ввиду эквивалентности задач (0.3) и (0.4) на них всегда интересно смотреть в сравнении с задачей о внешней оценке

R(x) min и с задачей о внутренней оценке

Рп(х) max

XdD выпуклого компакта D евклидовым шаром. В связи с этим задачи (0.3) и (0.4) можно назвать задачами о равномерной оценке выпуклого компакта D евклидовым шаром.

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

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

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

А + В = {а + Ь:аеА,ЪеВ},А-В = {а-Ь:аеА,ЬеВ}

- алгебраическая сумма и разность множеств А и В,

А - В = {с: с+ В С А}

- разность Минковского ([7]) или JI.C. Понтрягина множеств Aw В xhx2] = co{xhx2}

- отрезок, соединяющий точки х\ и х2, и=d>w)2),/2

1=1 евклидова норма элемента х Е Жр, р х,у>=^х{г)у{г) 1=1

- скалярное произведение элементов х, у Е

Вп(х, г) = {уеШр: п(х -у) < г}, Sn(x, г) = {у Е : п(ж - у) =

- шар и сфера нормы п(-) с центром в точке х и радиусом г,

Qp(x,D) = {yeD : рдОг) = п(® - у)}

- проекция точки х на множество D в норме п(-),

Qr(x, D) = {у Е D : Д(®) = п(® - у)}

- множество точек касания множества D и шара B(x,R(x)),

К (А) = {г; Е : За > 0, а Е A, v = аа}

- конус, натянутый на множество А,

K+ = {we Rp :< v, w >> 0, Vu Е К}

- конус, сопряженный к конусу Я",

К(х,А) - конус возможных направлений множества А в точке х Е то есть К(х, А) = 7(2, А), где

7(а?, Л) = {д Е Rp : < 0 : х + ад Е Д а Е (0, ад)},

W(x, A) = sup < x, a > a£A

- опорная функция множества A,

A/(z) = inf {a > 0 : x £ aM}

- функция Минковского множества А, df(x) - субдифференциал выпуклой функции /(•) в точке х, f\x,g) = \lma-1[f{x + ag) - f{x)}

Q| О

- производная функции /(•) в точке х по направлению д.

Первая глава диссертации содержит §§1-G, ее главная цель - характе-ризация устойчивости решения задачи (0.1) о внешней оценке.

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

В §2 приводятся некоторые вспомогательные факты, главные из которых касаются свойств строго и сильно квазивынуклых норм. Эги свойства использовались далее при исследовании свойств целевой функции R(x) в задаче (0.1) и функции расстояния, также играющей важную роль. Если понятие строго квазивыпуклой нормы и ее свойства использовались в выпуклом анализе ранее (см. напр. [34]), то понятие г-сильно квазивыпуклой нормы, как нормы, обладающей r-сильно выпуклым ([15]) единичным шаром, вводится впервые.

Следующий факт позволяет сравнивать поведение таких норм на отрезках с поведением сильно выпуклых функций.

Лемма 2.8. Если тг(-) является r-сильно квазивыпуклой нормой, то для любых точек х\ и Х2, отличных от 0;„ и a G [0,1] выполняется неравенство n(axi + (1 - а)х2) < an(xi) -I- (1 — а)п(хг)— Cia(l — а)п(х{)п(х2) " 2

2r(an{x\) + (1 - а)п(х2))

Х\ X2 п(х i) п(х 2) где константа С\ - полоэ/ситпелъная константа, для которой

CilMI<rcM, v®eRp. (0.5)

10

Для сильно квазивыпуклой нормы, единичный шар ко юрой имеет представление

Bn{Op,l) = f]B{a,r), (0.G) аел где А - симметричный относительно 0;, компакт, получена конкретная формула, ее выражающая.

Лемма 2.9. Если единичный шар нормы п(-) имеет вид (0.6) при условии А С intB(Qp,r), то саму норму можно выразить следующей формулой п(х) = шах а,® >| + у/< а,х >2 +||я||2(г2 — ||а||2) аел г2 - ||а|'2

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

Теорема 3.1. Если п(-) является г-сильно квазивыпуклой нормой, то для любых х\ и x<i из а € (0,1) найдется точка уа е Sn(x 1, R(xi)) р| Sn{x2, R(x2)) такая, что выполняется неравенство

R{axi + (1 - а)х2) < aR(xi) + (1 - oi)R{x2)

Cia(l-ot)R{xi)R(x2)

-Уа ®2 - Уа

R{x i) R{x2) 1

2r(aR{xi) + (1 - a)R{x2)) где C\ - полоэ/сительпая константа, для которой выполняется (0.5)

При исследовании задач (0.1) и (0.2) важную вспомогательную роль играет функция расстояния. В §4 изучаются свойства функции расстояния до строго и сильно выпуклых множеств, а также до множеств, которые являются их дополнениями. Нетрудно видеть, что функция расстояния

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

Для случая, когда D - строго выпуклое множество доказана

Теорема 4.1. Если D является строго выпуклым множеством и точки х\ и Х2 из D таковы, что

PtiM < рп(х2) < pq{xi) + п{х 1 - х2), то для любого a 6 (0,1) выполняется строгое неравенство рп(ахi + (1 - а)х2) > арп(хi) + (1 - а)рп(х2).

Описание поведения функции рп(х) сразу на всем множестве D даег

Теорема 4.2. Если D является строго выпуклым мноэюеством, то функция рп(х) является строго квазивогнутой па D.

Нижние лебеговы множества функции рр{х)

G(\, D) = {х GW : pD{x) < \] характеризует

Теорема 4.3. Если D является строго выпуклым мпоясеством, а гс(-) - строго квазивыпуклой нормой, то для любого А > О мноэюество G{A, D) является строго выпуклым.

По аналогии с теоремой 4.1, получены также условия, при которых функция pd{%) ведет себя на некоторых отрезках как строго выпуклая функция.

Теорема 4.5. Пусть D - строго выпуклое мнооюество, а п(-) - строго квазивыпуклая норма. Если точки х\ и х2 из Ер удовлетворяют неравенству

Pd{XI) < ря(®2) < Pd(X\) + п{х\ - х2), причем х2 D, то для любых а £ (0,1) выполняется pD(ax 1 + (1 - а)х2) < apD(xi) + (1 - a)pD{x2).

Нижеследующие два факта говорят о том, насколько усиливаются соответствующие свойства функции рп{х), зафиксированные в теоремах 4.3 и 4.5, если D - сильно выпуклое множество, а п(-) - сильно квазивы-иуклая норма.

Теорема 4.6. Если D является г\-сильпо выпуклым мпоэюеством, а п(') — Г2-сильио квазивыпуклой нормой, то для любого А > 0 мпоэ/сество G(X,D) является (п + Аг2)-сильно выпуклым.

Теорема 4.7. Пусть D является г\-сильпо выпуклым мпоэюеством, а п(-) - Г2-сильно квазивыпуклой нормой, и точки х\ и %2 таковы, что xhx2]f]D = l

Тогда для любых точек у\ € Qp(x 1, D), У2 Е Qp{x2, D) и любого а £ [0,1] справедливо неравенство: с pD(ax 1 + (1 - а)х2) < apD(x\) + (1 - a)pD(x2) - у0^1 ~ <*)*

У1~У2\\2 , PD(X\)pd(X2)

-г

Х\ ~У\ х2 - У2

PD{X 1) PD{? 2) n r2[apD(xi) + (1 - a)pD(x2)]

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

Теорема 4.9. Пусть D - г\-сильпо выпуклое Mnooicecmeo, п(-) -сильно квазивыпуклая норма, а точки х\ и Х2 таковы, что pD(x 1) = pD(x2) = р > 0, {хих2} р| D = 0.

Тогда для всех значений a G [0,1] справедливо неравенство pD(axi + (1 - а)х2) <Р~ НЖ1 ~ ж2||2, где С\ - положительная константа, удовлетворяющая (0.5)

Теорема 4.10. Пусть D является г-сильно выпуклым мноэюеством. Тогда для любых точек xi и х2 из D таких, что

Pn(®i) = РпМ = Р 13 и любых значений a £ [0,1] выполняется неравенство рп(ах 1 + (1 - а)х2) >р+ Cl0£^r НЖ1 ~

Следует отметить, что важную роль в исследовании свойств функции R(x) и функции расстояния, касающихся случаев с сильно выпуклым множеством D или сильно квазивыпуклой нормой, сыграли факты из сильно выпуклого анализа (см. [15]-[16]).

Свойства функции R(x) и функции рассюяния использованы далее в §5, где сформулирован и доказан критерий решения задачи (0.1) в форме, связывающий ее с задачей о внутренней оценке нижнего лебегова множества функции R(x) шаром используемой нормы.

Теорема 5.1. Точка х* является решением задачи (0.1) тогда и только тогда, когда для любого А > R* она является центром вло-оюенного в мноэюеетво GR(А) = {х Е Ш.р : R(x) < А} шара наибольшего радиуса, то есть решением задачи где Q(A) = MP\GR(А). При этом радиус вложенного шара есть рщ л)М = А-Я*.

Эта теорема является самым трудным но доказательству результатом первой главы.

Основным в первой главе является §6, где собраны и доказаны факты, касающиеся устойчивости решения задачи (0.1).

Выяснилось, что устойчивость задачи (0.1) относительно оптимального значения целевой функции R(x) имеет место всегда, причем справедлива

Теорема 6.1. Справедливо неравенство

R* - Щ\ < С2е, где

R* = min R(x), Rt = min R£(x). zeip v h £ v " а С2 - полоэюителъная константа, для которой п{х) < С2\\х\\, Vx е W.

0.7)

Каждому выпуклому компакту D, как элементу пространства всех выпуклых компактов Kv(W), можно сопоставить X(D) - множество решений задачи (0.1), то есть множество цен i ров описанных шаров. Поэтому можно рассматривать многозначное оюбражение

Его характеризует

Теорема 6.2. Многозначное отобраоюение Х(-) является полунепрерывным сверху всюду на Kv(Rp).

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

Основным результатом главы является

Теорема 6.3. Пусть п(-) является г-сильно квазивыпуклой нормой. Если точка х* является решением задачи (0.1), а точка х£ - решением задачи (0.2), то справедливо неравенство где полоэюителъные константы С\ и С2 удовлетворяют неравенствам (0.5) и (0.7) соответственно.

5. Вторая глава диссертации содержит §§7-11, ее цель - исследование устойчивости задачи (0.3). В §7 дается постановка этой задачи и формулировки результатов из работы М.С.Никольского и Д.Б.Силина [12], которые в значительной мере далее используются.

В §8 приводятся некоторые свойства вспомогательной функции

Х{-) : ЩШР) 2КР.

Ло(я) = max Ця-у||, y€D0 где

DQ = B{xhR{xl))f]B{x2,R{x2)) для некоторых фиксированных точек х\ ф хч

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

В §10 рассматриваются некоторые свойства целевой функции

Ф(х) = R{x) - рп(х) в экстремальной задаче (0.4).

Во первых, получена оценка снизу для ее производной по направлению через значение производной но этому направлению функции R(х).

Теорема 10.1. Если intD ф 0, точка х £ intD, а единичное направление g £ Ер таково, что я// ч с . рп(х) то рЫхУ

Я2(х) j'

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

Теорема 10.2. Пусть Д- - выпуклый компакт такой, что h(D, De) < е, где е > 0. Если точка хо - решение задачи (0.3), а х£ - решение прибли-оюенной задачи h(De,B(x,r))-* min (0.8) xCKp,r>0 то справедливо неравенство ф{х0)-ф(х£)\<4£.

Вспомогательные результаты §§8-10, а также работы [12] и первой главы диссертации применяются в §11 для получения основных результатов - характеризации устойчивости задачи (0.3).

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

Теорема 11.1. Пусть хо - центр шара наилучшего приближения в задаче (0.3), а хе - в приближенной задаче (0.8). Тогда справедливо асимптотическое неравенство где о(1) -)• 0 при £ | 0.

Ее следствием, но сути, является получаемая далее оценка устойчивости радиуса шара наилучшего приближения

Теорема 11.2. Если го - радиус гиара наилучшего приближения в задаче (0.3), а г£ - в приблиэ/сеннной задаче (0.8), то справедливо асимптотическое неравенство где о(1) 0 при с 4- 0.

Основные результаты диссертации опубликованы в [35]-[40].

Автор выражает глубокую признательность своему научному руководителю профессору А.П.Хромову за помощь и внимание к работе.

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

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

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

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

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

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

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

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

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

10. Карманов В.Г. Математическое программирование. М.: Наука, 1986 И. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985.

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

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

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

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

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

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

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

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

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

20. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Изд-во ФИЗМАТЛИТ, 1958.

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

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

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

24. D'Ocagne М. Sur certaine figures minimales //Bull. Soc. Math. France 1884. v.12. P.168-177.

25. 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.

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

27. Bonnesen Т., Fenchel W. Theory der konvexen Korper. Berlin: Springer-Verlag, 1934.

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

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

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

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

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

33. Dudov S.I., Zlatorunskaya I.V. Best approximation of a compact convexset by a ball in an arbitrary norm // Advances in mathematics research. 2002. V.2. Nova Science Publishers, Inc. New York, P.81-114.

34. Дудова А.С. Об устойчивости задачи о внешней оценке компакта шаром произвольной нормы // Тез. докл. 12-ой Саратовской зимней школы. Саратов. Изд-во Гос УНЦ "Колледж'2004, с.75-76.

35. Дудова А.С. Об устойчивости решения задачи внешней оценки компакта шаром произвольной нормы // Математика. Механика: Сб. научн.тр. Саратов: Изд-во Сарат. ун-та. 2004. - выи.6. С.54-56.

36. Дудова А.С. Об аппроксимации выпуклого компакта многогранником //Материалы 7-й междунар. Казанской летней научной школы-конференции. Казань: Изд-во Казанскою матем. общества, 2005,с. 68-69.

37. Дудова А.С. Об аппроксимации выпуклого компакта многогранником //Математика. Механика: Сб. научн. тр. Саратов: Изд-во Сарат ун-та. 2005.- вып.7. с.45-47.

38. Дудова А С. Об одном критерии решения задачи о внешней оценке компакта шаром // Тез. докл. 13-ой Саратовской зимней школы. Саратов. Изд-во "Научная книга2006, с.65-66.