Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 23
Текст из файла (страница 23)
(2.29) Легко подсчитать (так же, как это делалось в доказательстве теоремы 1.4), что КВ,(хо) = =(*: * = — Х ао* 1 >О ХО;( )=О) ~2.30~ 1=О+1 Так как точка хп фигурирующая в условии теоремы, принадлежит и Рь то г(К1(х,) П КВ,(хо)чь Я. Поэтому на основании теоремы 1.4.16 заключаем, что Коо (хо) = Кй (хо) + КВ, (хо) Таким образом, вектор хоен д„Х(хо, уо) можно представить в виде хо = х1 — ~ч.", Лох;, Х1)0, ХД(хо) = О, 1=1,...,т, 1=-1+1 х1 ~ КВ (хо).
(2.31) Тогда пз теоремы 2.6 следует, что существует такой вектор у*,что (2.28) ~(хо уо) ~~~(х> уо) хан Роо Уо Ъ Оэ Уо /1(хо) = О, 1 = 1,..., х. 154 ГЛ. 1У. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ Положим тепеРь У~о = Х~, 1=к+1, ..., т. ТогДа т Ь(х, У',) =Т(х, Уо)+ ~ Л1У1(х), и вектор х, = хо + ,~~~ Х;х;, 1=ОО-1 очевидно, принадлежит д„г' (х„у,").
Итак, д„Ь(х„уо) П К*о(х) ~ Я, и из теоремы 2.2 можно заключить, что хо — точка минимума функции Р (х, уо) на множестве Р. Вместе с соотношениями оо)О, Х4~(хо) =О, 1=я+1, ..., т, вытекающими из формул (2.31) и (2.28), это доказывает теорему. 3 3. Двойственные задачи выпуклого программировании Как и в предыдущем. параграфе, рассмотрим задачу выпуклого программирования: минимизировать функцию 1о(х) на множестве М=(х: ~д(х) (О, 1=1, ...,,т, х1НР), Йош~,жР, 1=1, ..., и.
Относительно функций ~,(х) будем предполагать, что они собственные, выпуклые и замкнутые; Р— выпуклое множество. Эти предположения считаются выполненными всюду в этом параграфе и специально не оговариваются в формулировках теорем. Пусть опять Х (х, уо) = до (х) + ~ у ); (х), 1 1 ~Р(у*) =1п((Ь(х, у*): хан Р), уо)О, х 1=-1, ..., и, хяР). о'(у) = 1~1(~~(х): ~1(х)(у1, з 3. Двоиствкнныв ВАдАчи Если ввести многозначное отображение а(у) =((х, х') ~ К"+': ~~(х)(у', 1=1, ..., тп, ~в(х)(хь, х~ О), то, как показано в предыдущем параграфе (формулы (2.11), (2Л4)), (ЗЛ) Рт',(у, О, 1) = т'(у), ф(ув), если ув)0, — оо, если у <О $Э для некоторого й (3.2) Й~ (- у*, О, 1) = Назовем задачу максимизации ф(ув) по всем у*~О двойственной задачей.
Теорема ЗЛ. Пусть У(0) чьж и 1зункция т'(у) полунепрерывна снизу в точке у = О. Тогда 1ИЦ)з(х): хе= М)= зпр(ф(ув): ув~)0), (3.3) т. е. точная нижняя грань в исходной задаче совпадает с точной верхней гранью целевой функции в двойствен- ной задаче. Доказательство. Согласно теореме 111.4.2, при- мененной к введенному многозначному отображению а(у), с учетом замены обозначений (пространства Х н У нужно поменять местами, вместо хз в формуле (4.4) следует взять у = 0) получаем зпр (ьг, (ув, О, 1) + (О, ув)) = Ит, (О, О, 1), гь так как функция И".(у, О, 1) = т'(у) по предположенизо полунепрерывна снизу в нуле, и, значит, условия теоре- мы 111.4.2 выполнены.
Используя соотношения (3.1), (3.2),получаем из последнего равенства зпр(ф(у*): у*)0) = Р (0), Ф что и требовалось доказать. Заметим теперь, что если х ж М, у* > О, то ф (у ) ( Ь (х, у*) = ~ (х) +,."~~ у~'~, (х) ( ~ (х), так что всегда ф(ув) <Дх) для хжМ, ув > О. ГЛ. 1У. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ 166 Дадим соотношению (3.3) другую интерпретацию. Легко видеть, что $(х) = зпр(Т (х, у*): уе)0) = Ф Ув(х), если 11(х)((0, 1=1, ..., т, + ОО, если 11(х)) 0 для некоторого 1.
Поэтому соотношение (3.3) эквивалентно следующему: (п1 зпр Ь (х, у*) = зпр 1п1 Ь (х, у*), (3.4) хип вх>в „хэв хап так что равенство (3.3) выполнено тогда п только тогда, когда выполнено равенство (3.4). Т е о р е м а 3.2. Пусть Р— замкнутое мнохсество и мнохсество Ра — точек минимума функиии 1с(х) на в1— ограничено. Тогда выполнены соотношения (3.3) и (3.4).
Доказательство. Определим многозначное отображение а(у, ус) =(х: 1;(х) (у', 1=0, ..., т, хшР). В силу замкнутости ), и Р отобраигение а — замкнутое п выпуклое и Ре = а(0, У(0)), так что а(0, т'(0)) ограничено. Но тогда по лемме 111.11 а(у, ус) — ограниченное отображение и множество а(у, ус) ограничено и замкнуто, т. е. компактно. Пусть теперь у, - О, Нш У(у;) = (А. з Ф Можно предполагать, что )з ( + , так как случай и =* = + тривиален. Тогда У(уг) = 1п1(1,(х): хеп а(уг, р+ з)) (3.5) при больших у. Но а(уь (1+ в) — компактное множество, а рс(х) — замкнутая собственная функция, поэтому нижняя грань в (3.5) достигается в некоторой точке х1сн ш а(УВ (А+ е).
Так как а — огРаниченное отобРажение, то последовательность х, ограничена и из нее можно выбрать сходящуюся. Будем считать, что х1- хс. Так как а — замкнутое отображение, то хв1иа(0, р+з). Тогда из определения а слеДУет, что хс1вМ и (с(хс) ( 11+ а. Но в этом слУчае $ г. дВОЙстВенные эАдАчп 1т(0) ( (А+ э, и так как з > 0 произвольно, то р = 1(ш т'(уг) ~ ИО), 1-~00 т. е. (т(у) полунепрерывна в точке нуль. Для завершения доказательства остается применить результаты теоремы 31.
Теорема 3.3. Пусть задача выпуклого прогр ммиро* винил имеет вектор Куна — Таккера уэ. Тогда выполнены соотношения (3.3), (3.4) и ф(уг) = эпр(ф(у*): у*~~ О). Доказательство. Если у, '— вектор Куна — Таккера, то — у*ги де'(О) по теореме 2.8. Поэтому р(у) ~у(о) — <у, у,*> для всех у. В частности, если у- О, то 1(ш т'(у) Р- т'(0), т. е. функция )т(у) полунепрерывна снизу в нуле. Отсюда по теореме 3 1 следует, что соотношения (3.3) и (3.4) выполнены. Далее, по определению 2.1 ф (у*) = )т. (0) = ш1 (1, (х): х ен М). В то же время выше было показано, что ф(уе) ( 1ь(х) для любого у*~ О, х ~к М.
Поэтому ф(уэ) =1ВХ(Уг(х): хжМ»ф(у*), уе>0, х что завершает доказательство. Комбинируя зту теорему с теоремами 2.5 и 2.10 предыдущего параграфа, гарантировавшими существованпе вектора Куна — Таккера, можно получить различные более просто проверяемые условия, при которых справедливы соотношения (3.3) н (3.4). Заметим также, что если фуякции 1,(х) имеют внд (х, х*.) — сгн 1= 0, ..., и, П =Х, то получающаяся задача есть задача линейного программирования.
Для нее определенное выше многоэначное отображение а(у) многогранно, а поэтому согласно теореме 111.3.6 функция т'(у) = Ит,(у, О, 1) замкнута. Отсгода следует, что спра- ведлива 158 Гл, гт Выпуклок ПРОГРАмииРОВАнпн Теорема 3.4. Если всв Функции 1,(х) имеют вид <х, х~) — ин 1 О, ..., и, т. с. рассматривается задача линейного программирования, то имеют место соотноигения (3.3) и (3.4). Нетрудно убедиться, что получающаяся при этом двойственная задача совпадает с рассмотренной в з 1.
3 4. Некоторые задачи теории приближений Пусть С вЂ” выпуклое компактное множество в Х н О ~н (п(С. По определению И'с (хв) = шах ((х, х*>: х ен С). х Так как Ою (п(С, то С вЂ” еВ, где  — единичный шар, а е ~О. Поэтому Итс(х*)) шах((х, хв>: х~ еВ) = е(х*1. (4Л) Последнее соотношение следует из того, что по известной формуле <х, хв> ( 'гх11х*1, положив хг = е1хг1 'х*, получим хо ю еВ, <хс, хв> = е1хв!!. Возьмем теперь функцию Минковского множества Сс гс(х) =1п1(р: хенрС).
о~в По доказанному в п. 2 3 2 главы 1 функция г,(х) положительно однородна, выпукла и конечна для всех х, так что т,(х) непрерывна по х. Так как С вЂ” компакт, то г,(х) ) О для хФО. Поэтому гс(х) может служить в качестве обобщенного расстояния от точки х до точки О. Введем для компактного выпуклого множества А и замкнутого выпуклого множества М величину Ис (А) М) = ш1(р) О: А с: М+ рС). (4.2) Р В частности, если А состоит из одной точки х, то получается функция дс(х! М), рассмотренная п. 4 $3 главы П.
Вычисление же функции дс(х(М) сводится к оценке расстояния от точки х до множества М, когда метрика задается прп помощи функции т,(х). Чтобы это стало более $ Ь НЕКОТОРЫЕ ЗАДАЧИ ТЕОРИИ НРИЕЛИЖЕНИй 159 ясно, заметим, что Ис(х~М) = )п((р)0: х~ М+ РС) = Р = 1пг гпг (Р )~ О: х еи хг + РС) = х1ям Р = иЛ гп((р: (х — х,) еп РС) = гп( гс(х — хг) х,ям Р х,нм т.
е. ~)с (х!М) = гп((гс (х — х,): х, ~ М). (4.3) х~ В общем случае Нс (А ~ М) = М (р х: 0: А с= М + РС) = = зпр (п((Р) 0: х ей М+РС) = зпр Сс(хз! М). (4.4) хзнА Р х~яА Таким образом, вычисление ох(А~М) сводится к нахождению в А точки, которая наихудшим образом аппроксимируется множеством М в метрике, определяемой множеством С. Если С=В, где  — единичный шар, то г,(х) = ~~ха!, так что в етом случае приближение получается в естественной метрике пространства Х.
Пусть теперь множество М состоит из одной точки х. Тогда сс(А)х) = 1п((р РО: Аях+ РС) = Р = (п((Р~~О: А — х~рС). Р Отсюда видно, что вычисление А(А)х) сводится к на= хождению наименьшего козффнинента растяжения, прга котором мноягество РС содержит А — х. Если поставиты задачу нахождения минимума ох(А!х) по х, то геометрически задача сведется к нахождению такого сдвига множества А, при котором его можно погрузить в множество РС с наименьшим коэффициентом растяжения.
В частности, если С= — шар, то задача состоит в нахождении шара наименьшего радиуса, описанного вокруг А. Рассмотрим, что может дать теория, развитая в пре дыдущих параграфах, для поставленных задач. 160 ГЛ. 1Ч, ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ Т е о р е и а 4А. Справедлива формула дс(А) М) = зпр(И' (х*) — Игм(х*): И'с(х*)(1). Доказательство. Согласно теореме П.3.15 дс (х ( М) = зпр ((х, х*) — И', (хе): Иге (х*) ( 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
