Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 24
Текст из файла (страница 24)
(4. 5) Подставляя это выражение в формулу (4.4), получим ас(А ~ М) = зпр зпр((х„х ) — Игм(х*): Иго(хе) ах1) = хаПА х* = зпр ( зпр (хю х"') — Игм(х*): И'с (х*) (~1) х* |.х БА У 6 (хе! (О)) й (х': И'с (х*) < Ц д если 1с(х,) = О, дб ( ) гс (хв) С) й (х*: И'с (х ) = Ц (4.6) если гс(хе) > О. дгс(хо) = Но г,(хс) =О, только если хе=О. Так как по формуле (П.3.25) дб(хо)М) = — (соп (М вЂ” хойе, (4.7) а (соп (0) )* = Хе, то дб(0! (0) ) = — Х* = Хе, и в силу формулы (4.6) выполняется соотношение дг,(0) = (х*: И',(хе) (1).
(4.8) ПУсть тепеРь хечьО, так что гс(хо) ) О. Тогда соп (гх(хо)С вЂ” ха) = 0 (гс(хо)х — хо): Х О, х1ЕС), и поэтому сопряженный ему конус состоит пз тел п только тех точек хх, для которых <гх(хе)х — хо, х* > =-.- О, х ш С, что и требовалось доказать. Обратимся теперь к задаче об отыскании условий, характеризующих точку х1, в которой достигается минимум в правой части формулы (4.3), т. е.
характеризующих точку из М, ближайшую к х в метрике г,(х). Так как гс(х) =де(хНО)), то согласно теореме П.ЗА6 справедлива формула О а некотОРые ЗАЛАчи теОРии пРиБлижений 1я пли, по другому, — <хо, х*> ~ тс(хо)Иге( — хо). (4.9) Учнтывая формулы (4.7) и (4.6), получаем дтс(хо) = (хо1 <хо, хн> ~ >те(хо), И е(хо) = 1). (4.10) 11о хоеигс(хо)С по определению т,(хо) и в силу замкнутости С.
Поэтому <хо хо> - ге(хо)И'с(х~), а, значит, в формуле (4.10) имеет место равенство <хо, хн> = тс(хо). Зафиксируем полученный результат. Теорема 4.2. Если С вЂ” компактное выпуклое мно-. жество и Ож(н(С, то дг (х,) = (хо: И'с(хн)~(1), если хо = О, (хо: <хо х"> = "с(хе), И'с(х*) = 1), если х,е-О. (4.11) Теперь можно сформулировать условия, характери- зующпе точку х1, в которой функция ге(х — х1) достигает своего минимума де(Х1М) па множестве М. Теорема 4.3. Для того чтобы точка х1шМ была наилучшим приближвниеле к ХФМ в метрике г,(х — х1), необходимо и достаточно, чтоба1 нашелся такой вектор хо ~ Км (х,), что <х1 — х, х*> = г,(х — х1) = д(х'1М), И',( — хо) = 1.
Доказательство. Точка наилучшего приближения х1 по определению является точкой минимума функции у(хо) =г,(х — хо) при хоеиМ. По теореме 2.2 для этого необходимо и достаточно, чтобы нашелся такой вектор хв ен Км (х,), что х*еи ду(Х1). Но хо ж дд(Х1) тогда и только тогда, когда Е(Х2) у(Х1) = Гс(Х вЂ” Х2) — Гс(х — Х1) ~~ <Х2 Х1, Х > для всех хо. Обозначая 2=х — хо, зо х — х1, получаем Ге(2) — Г,(2О) В <2 — зе, — ХЕ>, Ы Б. Н.
Пюеннчныа 162 ГЛ. 1У. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ т. е. — х*!ндг,(х — х!). Согласно теореме 4.2 для выполнения етого неравенства необходимо и достаточно, чтобы <х — х1, — х*>-г,(х-х,) =Н.(Х~М), И",( — х~) =1, что доказывает теорему. Множество х + рС будем для удобства называть обобщенным шаром радиуса р с центром в точке х. Рассмотрим задачу нахождения обобщенного шара минимального радиуса, содержащего данный компакт А.
Эта задача сводится, как говорилось выше, к минимизации функции !)е(А!х) по х. По определению бс(А(х) = = Ы (р ) О: А = х+ рС) = !В1(р) О: А — х ее рС) = Р Р = зпр !П1(р) О: х! — хек рС) = зор тс(хг — х). х,аА р хзаА Таким образом, поставленная задача сводится к налождению минимума функции у(х) = ж!р г (х, — х). (4.12) х,НА Заметем, что )(х) есть радиус минимального шара с фиксированным центром х, с)!держащего множество А. Так как А — компакт, а г, — непрерывная функция, то верхняя грань в правой части формулы (4Л2) достигается.
Обозначим А(х) = (х1! Ре(х! х) = ~(х) х! !к А). Согласно теореме П.ЗЛ4, все условия которой в рассматриваемом случае выполняются, д~ (х) = со !' () д„гс (х! — Х)). (4.13) !х1аА(х! Из выкладок, проделанных в предыдущей теореме, и формулы (4Л1) следует, что д„г,(х! — х) = (хе! <х! — х, хе> = = ге(х — х!), И'е( — х*) = 1).
(4.14) Так как множество х*, для которых И"е( — хе) = 1, в силу неравенства (4Л) ограничено, а А(х) компактно, то нетрудно показать, используя теоремы 1.1.6 и 1ЛЛ, что в х т а задачи нлилтчшвго глвномвгиого ш ивлижвния 1ЕЗ формуле (4ЛЗ) вместо замкнутой выпуклой оболочки можно взять просто выпуклую оболочку, т. е. д~ (х) = со ( Ц д„тс (х, — х)).
(4.15) (х,ол(ю Теорема 2Л утвернгдает, что точка хг есть точка минимума функции ) (х) тогда и только тогда, когда Ош д~(х). Из формул (4.15), (4.14) и теоремы 1.1Л теперь следует, что если хг есть точка минимума )(х), то существуют такие числа Л,) О, М = О, ..., и, н такие векторы х,*., хд, я А (х,), 1= О, ..., и, что » » Ъ Л;х,*. = О, ~ч.", Л; = 1, 1=» г=о (хы — х» хх) = тс'(х» хм) = ((хг)~ ИУ, ( — х,') = 1, 1= О,..., и. Сформулируем полученный результат. Т е о р е м а 4.4. Для того чтобы обобщенный шар хо+((хс)С был шаром минимального радиуса, описанным вокруг компактного множества А, необходимо и достаточно, чтобы выполнялись условия (4Л6). Заметим, что в предыдущих рассуждениях никак не попользовалась выпуклость множества А, так что этого условия нет и в формулировке теоремы.
Т е о р е м а 4.5. Пусть А — компактное множество. Тогда существует такое его подмножество Аг, состоящее не более чем иг и+1 точек, что радиус минимального шара, описанного вокруг Аг, совпадает с радиусом минимального шара, описанного вокруг А. Д о к а з а т е л ь с т в о. Если рассмотреть множество Аг, состоящее из точек хи, 1=0, ..., и, фигурирующих в условиях (4.16), то, поскольку эти условия являются и достаточными, шар юг+~(хг)С будет шаром минимального радиуса, описанным вокруг Аг. й 5. Задачи наилучшего равномерного приближения Классической задачей наилучшего равномерного приближения является задача аппроксимации непрерывной функции на отрезке многочленами. И» 164 ГЛ, 1У. ВЫПУКЛОЕ ПРОГРАМЫНРОВАННЕ Пусть д(8), 1ш 10, 1),— непрерывная функция, Р„(х, 1) = х' + '1+... + х'~' ', где х — вектор с компонентами х', ..., х", являющимися коэффициентами многочлена Р„(х, 1) степени я — 1 относительно переменной 1.
Наилучшее равномерное приближение сводится к отысканию такого многочлена, для которого величина 1(х) = шах )д(1) — Р„(х, 1)) (5.1) еерл11 минимальна. Другая классическая задача, которая с иных позиций рассматривалась в предыдущем параграфе, есть задача нахождения центра шара, описанного вокруг компакта А ш К", для которого радиус был бы минимален, Нетрудно видеть, что такая задача сводится к минимизации функций 1(х) = шах(Цх — уи': у~ А). Как ни раалична на первый взгляд природа сформулированных задач, тем не менее они могут быть решены одним и тем же приемом. Этот прием основан на использовании теоремы 11.3А4.. Пусть )(х, а), ашА, где А — компакт, семейство выпуклых по х1иК", непрерывпыл по х и и функций.
Будем предполагать также, что при каждом я~нА су1цествует градиент функции 1(х, а) по х, т. е. существует / вектор 1х(х, а). Предположим, что он непрерывен по и при каждом х. Положим 1(х) = шах(1(х, а): и ы А), х (5.2) А (х) = (а ен А: ~ (х, а) = 1 (х)). Ясно, что 1(х) — выпуклая функция, а А(х) — компактное множество. Согласно теореме 11.3.14 д((х) = со/ () ~х(х, гз)). 1 анА(х) Легко видеть, что в силу сделанных предположений все условия теоремы 11.3А4 выполнены, а так как функ- % а ЗАНАчп нАнлучшкГО РАВнОмеРБОГО ПРНБлпжкния 165 Цип 7(х, и) дифференцируемы по х, то д) (х, а) = = Уи(х с()! Множество () 1и'(х,а) вил(х) 7'„(х, и): есть образ множества А(х) при отображении А- К",т.
е. 0 („(х, а) =)и(х, А(х)). акл(и) . Р Но А(х) — компакт, а отображение )„(х, (г) непрерывно по а в силу сделанных предположений. Поэтому / )и(х А(х)) — компактное множество. Итак, д/ (х) = со у„. (х, А (х)). Но в силу теоремы 1.1.7 (если М вЂ” компакт, то соМ= =соМ) имеем д~(х) = со ~ (х, А (х) ). Применяя теорему 1.1.1, окончательно получим д~(х) = ~ ~~"„Л(~„(х, и;)1 а( ~ А(х), Л( > О, ((=г 1=0,...,, ХЛ(=1.
1=0 (5.3) Из формулы (5.3) и теоремы 2.2 непосредственно вы- текает следующая Теор ем а5А. Для того чтобы Яункуия )(х), опре- деленная соотношением (5.2), достигала своего минимума на выпуклом множестве М в точке хг, необходимо и до- статочно, чтобы нашлись танис точки ои ш А(х„), 1=0, 1, ..., и, и такие числа Ль что п Д', Л(7'„(х„и() ен Км (хг), Л()0, 1=0,1,..., и, Л,+Л,+ ... +Л,„=1. (5.4) Замечание. Некоторые точки и; могут совпадать между собой так, что на самом деле число слагаемых в формулах (5.4) может быть меньше и+ 1. 1ее ГЛ. 1Ч. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ Рассмотрп11 теперь множество точек со~ он А(хо), 1'=О, ..., и, фигурирующих в теореме, и обозначим его через Ао.' Ао = (иа 1 = О, 1, ..., и).
Положим 1о (х) = шах (1(х, а)1 а еи Ао). (5.5) а (5.6) Пусть 1(х) = шах (!! х — у ~: у ен А), (5.7) А(х) = (у ен А: ~х — у~ = 1(х)). (5.8) Применение теоремы 5А в случае М = К" показывает, что точка х, тогда и только тогда является точкой минимума функции (5.7), когда существуют такие точки у;ш А, 1 = О, ...,п,и такие числа Лл > О,что Х Л, хо Рю „= О,,')', Л, = 1, '1 х — уо Ц = 1 (х ). Если точка хо является точкой минимума функции 1(х), то выполнены условия (5А), которые являются необходимыми и достаточными условиями минимума. Легко видеть, что применение теоремы 5А к функции 1о(х) показывает, что хо есть таки;е точка минимума и для функции 1о(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
