Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 22
Текст из файла (страница 22)
~г(х)(х', ~1(х)(у), 1'=-1,..., лт„хенР)= (х,х~) =1п1Ц,(х): ~1(х)(у', 1=1, ..., т, хвнЮ~. (2Л1) х В частности, если у О, то У(О) совпадает созначением точной нижней грани функции ~г(х) на множестве М. Вычислим теперь Й.(у*, х*, хгв) в случае, когда хг = =О, ага=1: й,(уг, О, 1) = )п1 ( — (у, уг)+х'. (х, х') с= а(у)) = ~г,х,х~) аале-йи );и) *-в). х 1=1 если — у* > О, — со, если — уьв < 0 для некоторого 1 = 1, ..., т. (2ЛЗ) В ведем следующее обозначение: Ь(х у') =4(х)+ Х ус"Л(х). 1=1 Функция г (х, у~) называется функцией Лагранжа рас- сматриваемой задачи выпуклого программирования. Обозначим )р (уе) = 011 (г, (х, у"): х ен Р). х Тогда можно записать 12,(уе,0,1) = 1г ( — ув), если — у* ~ ~О, (2Л4) — сс, если — уьв < 0 для некоторого й Пусть теперь для некоторого х)гиР выполняются не- равенства )1(х)) <О, 1=1, ..., и), и У(0) — конечное чис- ло.
Это означает, что в исходной задаче нахождения нижней грани функции )г(х) на множестве М эта точ- ная нижняя грань есть конечное число. Согласно лемме 1П.2Л функция г"(у) = И~.(у, О, 1) выпукла. Так как для у из некоторой окрестности точки у= О выполняются неравенства Дх)) (у', 1 1, ..., т, х) юР, то у(у) не принимает значения + в этой окрестности и, значит, у =0 есть внутренняя точка области опреде- $2, неОБхОдимые услОВия экстгвмума 147 ления т'(у): О~ншсаош т. Но в начале т 1 главы П было показано, что если выпуклая функция 7 принимает значение —, то она равна — всюду в г)йош7'. Так как У(0) конечно и О ~нш1аош т', то отсюда следует, что функция У(у) не принимает значений — е, а, значит, т'(у) конечна в некоторой окрестности У=О.
Поэтому согласно теореме ПЛ.4 функция У(у) непрерывна в окрестности нуля. Это позволяет применить теорему П1.4.3. При этом следует учесть, что для рассматриваемого здесь отображения (2ЛО) по сравнению со случаем, рассмотренным в теореме 1П.4.3, пространства Х и У поменялись местами. Применение теоремы Ш.4.3 показывает, что существует такой вектор уе, что У(0) = й'.(О, О, 1) =П„(у,',0,1)+ ~0, у,'~~ )П,(уа, О, 1)+ (О, ув) где учтено, что в формуле (4.5), фигурирующей в теореме П1.4.3, следует заменить хв на ув, у* на (хв, х',)= = (О, 1), а хе на У=О. Итак, существует такой вектор ув, что У(0) = П.
(у'„О, 1) ~П. (ув, О, 1). Учитывая формулы (2Л2) — (2.14), получаем т (О) = 'р ( ув) = = 1Б1(Ь(х, — уе): халР) ~) ф( — ув), — у*~)0, (2.15) причем, так как ф ( — У,) = У (0) — ' конечное число, то Ув ~~0. Теорема 2.5. Если существует такая точка х1 ыР, что /;(х1) (0 дла всех 1 1, ..., т и 1т(0) =.. ш1(7е(х): хе= лт) есть конечное число, то существует такой вектор ув ~ О, что Р(0) = ф(Уе) = 1Б1(Ь(х, У',): хан Р). (2.16) В частности, если хс — точка минимума функции 1е(х) на множестве М, то Ре(хо) ~< В(х Уо) хан Р.
(2.17) тев 148 ГЛ, гч. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ Доказательство получается из формулы (2Л5), если * Э заменить в ней — уо на уо н — Уо на Уо. Последнее утверждение теоремы следует из того, что по определению хо и У(0) (см. формулу (2Л1)) ~о(хо) = У(0). Теорема 2.6. Пусть существует такая точка х1~ шР, что )о(х1) (О, (=1, ..., и. Тогда для того, чтобы точка хо была точкой минимума 4ункции го(х) на мнохсестве М, задаваемом формулой (2.9), необходимо и достаточно, чтобы нашелся такой вектор уо еиП,чтобьо Ь(хо, уо)(Л(х, у ), хек д, (2Л8) уо ~~0 уо уо(хо) = О Д о к а з а т е л ь с т в о.
Согласно предыдущей теореме т существует такой вектор у, ен К, уо ) О, что выполняется неравенство (2.17). Но так как хо ~вМ, то хо она и й(хо) ~ О. Поэтому (( ', У*) = Уо(хо)+ Х У,' У (хо)<У(хо)<~(х„уо). Таким образом, У(хо) = ~(хо Уо) (2.19) Х уо У~(хо) = О. о=о Так как У', )О, ~о(хо)(0, то из последнего равенства вытекает уо~*~о(хо) = 0 ( = 1, ..., и. (2.20) Из равенств (2.20) и соотношений (2Л9), (2Л7) получается последнее из условий (2.18), чем доказана необходимость условий теоремы. Покажем их достаточность.
Пусть хонМ и условия (2.18) выполнены. Тогда (о (х) >)о (х) + Х Уо Л (х) = гет = л (х Уо) ~ ~т (хо Уо) = )о (хо) для всех х~М, т. е. хо — точка минимума. $ 3. неовходпъгьгн условия экстгемуз!А 449 3 а и е ч а н и е. Достаточность условий теоремы 2.6 показана без предположений о выпуклости функции ),(х), 4=О, ..., т.
Допустим теперь, что 7о(х), 1=0, ..., т,— непрерывные функции. Первое из условий (2.18) означает, что хо — точка минимума функции А(х, у,) по х на выпуклом множестве Р. Так как у, )Ои 7о(х) — выпуклые непрерывные функции, то Р(х, у,) — выпуклая непрерывная функция. Согласно теореме 2.2 функция Ь(х Уо) достигает своего минимума на Р в точке хо тогда и только тогда, когда доА (хо| Уо) П Ко (хо) ~ И Но по теореме П.3.8 д~Т~(хо уо) =Но(хо)+ Х уо*д71(хо) о=1 поэтому существует такой вектор хо еи Ко(хо),что о~ хоепд~о(хо)+ Х уо д~о(хо) (2.21) Включение (2.21) есть необходимое и достаточное условие того, что точка хо доставляет минимум функции Р (х, у,) на Р.
Таким образом, справедлива Т е о р е м а 2.7. Пусть выполнены условия теоремы 2.6 и 9х), 1=0, 1, ..., т,— непрерывные выпуклые функции. Точна хо есть точна минимума Функции уо(х) на мнохсвствв М тогда и только тогда, когда существуют оо Э такие точки уо ен К и хо я Ко (хо), что выполнено включение (2.21) и уо*~о(хо) = О, у*,') О, 1= 1,..., т. Определение 21. Вектор уо'~Оназывается вектором Куна — Таннера, если выполняется соотношение ш1(7о(х): хек М) = ш1(Р(х, у,"): хеп Р).
Теорема 2.5 дает условия, гарантирующие существование такого вектора. Свяжем теперь условие существо- 150 ГЛ. 1У ВЫПУКЛОЕ ПРОГРАММИРОВАННЕ вания этого вектора со свойствами функции у'(у) в окрестности нуля. Т е о р е м а 2.8. Вектор У э является вектором Куна— Таккера для задачи выпуклого программирования тогда и только тогда, когда — Уь ен др(0). Доказательство. По определению — уэ ендр(0) тогда и только тогда, когда Г(у))У(0)+(у, — у',), т.
е. когда 1П1[эт(у) + (у, у,)) = У(0). Подставим в эту формулу выражение (2.11) для У(у). Получим 1п11П1(1э(х)+(у, у,*): ~1(х)(у1, 1= 1,...,1п, хек Ю) = У(0). (2.22) Нетрудно заметить, что если у'ь «О для некоторого 1=1, ..., т, то в левой части соотношения (2.22) получим значение, равное — . Так как У(0) конечно, то этот ь случай исключается. Поэтому у, ) О,и левая часть формулы (2.22) приобретает вид 1п(~~е(х) + Д 11(х) уэ: я~й~ = 1П1(Ь(х, уь): хаий). х ! 1=1 х ь Итак, — уь ы де)т(0)тогда и только тогда, когда 1П1 (Ь (х, у"): х еи л)) = )т (0), т. е. когда у, есть вектор Куна — Таккера. Все предыдущее изложение велось в предположении существования такой точки х11вР, что 1',(х1) «О, 1= 1, ..., т.
Вместо этого теперь предположим, что функции 1;(х) непрерывны. Рассмотрим множество Мс = (х1 9х) «0), Х = О, 1, ..., т. Пусть хе1иМь По теореме П.3.18 возможны следующие случаи: 1 2. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 151 1) точек х, для которых ~~(х) < О, не существует; тогда согласно теореме 2.1 О ~ духо), так как хо ж М, и, значит, О Яхо) <7,(х), т.
е. хо — точка минимума функции Цх). 2) существует точка х, в которой ~~(х) < О; тогда О, если ~0(хо) < О, Км, (хо) = (2 23) — соп дно(х ), если ~о(х ) = О. Пусть хо — точка минимума функции 70(х) на множестве М, где М задано формулой (2.9). Так как М= П М; ())7, то по теореме 2.4 получаем, что существуют такиеточки х; ы Км,.
(хо) хо ы Ко (хо), хо ее Но (хо) о н число Ло Зо О, чтоЛ х;, 1= 1, ..., т, н х* не равны нулю одновременно и Лоха = Х хо + х ° .(2.24) Если теперь при некотором х 9х) <О для всех $, то верна формула (2.23). Положим хо = — Лхо Ло~»О *о~дУо(хо) (2.25) ХОО = Х01 Ф Ло хоо — — х*, Ф хоо ее д~о (х,), х* ы КВ (хо). причем Л,~О, ~олько если У~(хо) = О, и Л»*=О, если г;(хо) <.О, т. е. ЛА(хо) О, 1=1, ..., т.
(2.26) Заменяя хо,..., хо, в соотношении (2.24) их выражениями (2.25), получаем Лохоо + Лгхоо + ° ° ° + (2.27) Ло~о, Л,1,(,)=О, 1=0,...,т, 152 ГЛ. 1Ч. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ При этом среди чисел Х~ есть отличные от нуля, таккак не все Х, х;, х равны нулю. ь Если же ДлЯ некотоРого 1г точек х, ДлЯ котоРых 71,(х) < О, не существует, то, как сказано выше, Ош ен д~1,(хь).
Полагая х,',ь = О, Х;, = 1 и Х; О, 1чь1с, х*= =О, получим, что соотношения (2.27) также выполнены. Тем самым доказана Теорема 2.9. Пусть функции Дх), 1=0, ..., т, выпуклы и непрерывны. Тогда для того, чтобы точка хе доставляла минимум )с(х) на множестве М=(х: ~,(х) ( О, 1=1, ..., и, хтлР), необходимо, чтобы нашлись не все равные нулю числа )ь, 1=1, ..., т, такие, чтобы при некоторых х ен д11(хь) выполнялись соотношения Х Х1х еБ Кй (х ) 1=О где Х; > О, )ьД(хе) = О, 1 = О,..., и. Теоремы 2.6, 2.7 и 2.9 допускают дальнейшую детализацию, если конкретизировать способ задания множества Р. Теорема 2.10. Пуств 7,(х), 1=0, 1, ..., тп,— выпуклые собственные функции, причем 11 (х) = (х, х1 ) — а1 для 1=й+1, ..., и. Пусть Р— выпуклое множество, г)1)ош); — Р, 1= 1, ..., и, и существует такая точка х11н 1нг1Р, что 1;(х1) ( О, 1=1, ..., й.
Тогда для того, чтобы точка хд была точкой минимума функции 1г(х) на множестве М=(х: Дх)(0, 1=1, ..., и, хшР), необходимо и достаточно, чтобы нашелся такой вектор ь ы уь ~ Л, что выполнены соотношения (2 18). Доказательство. Пусть у" ен м у* = (у1 ° ° °, уь) ь Х(х, у*) = (ь(х)+ ~ у;71(х), 1=1 Ре=(х: Д(х) (О, г=й+1, ..., и, х1иР). % 3, неовходимые услОВия экстгемуыА ~ьз Так как Р с: П г1 6ош ~1, о=о о * то функция Х (х, уо) непрерывна на Р относительно т сдвинутого подпространства, содержащего П и' йош ~О 1=О Если вести рассуждения для этого подпространства, то на основании теоремы 2.2 получим, что существует такой вектор хо ен д„Х(хо, у,), что хо я КВ,(хо). Но очевидно, что КВ, (хо) = КВ (хо) П КВ, (хо) где КВ, (х,) — конус, соответствующий множеству Р, = (х: ~1(х) = (х, х,') — оз1~0, 1= У+1,..., и!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
