Ф.П. Васильев - Методы оптимизации (1125241), страница 101
Текст из файла (страница 101)
МЕТОД ШТРАФНЫХ ФУНКЦИЙ 339 338 Гл. 5, мптоДБ! минимизйции ФУнкций многих пВРВМВнных (44) 7. Пусть Х = (х с Е"; д(х) < О), где д(х) — непрерывная функция на Е". Доказать, чю для того, чтобы множество Х было ограниченным и ограничение д(х) < 0 было корректным на е", необходимо и достаточно, чтобы множество хэ — -(х е е": д(х) < б) было ограниченным хотя бы при одном Ь > О. 8. Пусть Хо — выпуклое замкнутое множество из Е", функцив д(х) выпукла и полунепре- Рывна снизУ на Хо, и пУсть множество М(С) = (х Е Хо. д(х) < С) непУсто и огРзничено пРи некотором С. Доказать, что тогда ограничение д(х) < 0 корректно на Хо (см.
теорему 4.2.17). 9. Рассмотреть задачу: 1(х) =х — >си[; хСХ =(х ЕЕ', д(х) =хаев]х)<0), з >О. Доказать, что здесь выполняется неравенство (36) с М = 1>св, Т = 1. Установить существование седловой точки функции Лагранхса. Выполняются ли здесь условия теорем 4.9,2, 4.9,4? Ю. Применить метод штрафных функций к задаче (43), получив оценки скорости сходимо- сти метода, и сравнить их с оценками из теорем 5, 6. П. Применить метод штрафных функций к задаче: 1(и) = х + (1 — хд) ->[и1; а Е Х = 2 2 = [и = (х, д) Е Е>; д(и) = х — а= 0), исследовать его сходимость при различных значениях параметра а, 12.
Доказать, что множество Х = (х Е Евс д((х) = (ау, х) — Ь( = О, т = 1,, в], где а>, ..., а, — ЛИНЕЙНО НЕЗаВИСИМЫЕ ВЕКтОрЫ Из Е", Ь' Е К, яВЛяЕтея КаррЕКтНЫМ На Ев И НЕраВЕН- ство (36) выполняется с 7 = 1, М= в([А~(ААт) ((], А — матрица размера в х и, строками которой являются векторы ас, .. о а,. У к а з а н и е воспользоваться результатами приме- ра 4.4.3. 13. Пусть задача (1), (8) удовлетворяет условиям теоремы 4.9.2, причем х )о Х,. Доказать, что тогда Х„= (х с Хо. 'Ф(х) = Ф„), где Ф(т) = 1и 4 2 гпах] 0; — ' >, Ф, = !и[Ф(х).
14. Пусть в задаче (1), (8) 7, > — со, Х„~ и(, пусть функция Ф(х, А) = 7(т) + АФ(х), где штрафная функция Р(х) определена формулой (9) при р >О, пусть Ф„(А) = !п[ Ф(х, А), ве Хо А >О. Для того чтобы 1ип Ф,(А) =,[ы необходимо и достаточно, чтобы задача (1), (8) А 4- * имела согласованную постановку на Хе (определение 2) и существовало число Ао > О, что Ф„(Ае) > -сю, Доказать [! 8]. !5.
Пусть в задаче (1), (8) Хо — выпуклое замкнутое множество, функции [(х), д,(х),... ..., д (т), [д + ((х)),..., (д,(х)! выпуклы на Хе, 1„>-со, пусть функции Ф(т, А), Ф (А) взяты из уп™ра>кненйя 14 при р > 1. Для того чтобы 1!ш Ф,(А) = 1ы необходимо и достаточно, чтобы А ->оо * задача (1), (8) имела согласованную постановку на множестве Хо.
Доказать [18]. 16. Доказать, что согласованная постановка задачи (!), (8) на множестве Хо равносильна тому, что функция 1>(с) = ш1 У(х), где Х(с) =(хе Хо. д,+(х) < сг, 4 = 1, .. о в), полуне* Е Х(о) прерывна снизу при с; — >+О, с = 1,..., в. 17. Привести пример задачи минимизации, для которой существует точная штрафная функ- ция (определение 4), дифференцируемая любое конечное число раз.
У к а з а н и е; рассмо. треть задачу: у(т) ж 0 — > (и[, х Е Х = (х с Хо — — Е: д(х) = — х < О), взять Р(х) = (шах(-х; 0))у Ур>0. 18. Показать, что если в лемме 5 условие (42) выполняется ие на всем множестве Хо, а лишь на множестве Хв из (15), то метод штрафных функций может не сходиться. У к а з а н и е: рассмотреть задачу из примера 4; взять Р(х) =шах(]х); 0) = [х]. 19. Пусть Иг — открытое выпуклое множество, функции [(х), д((х), т = 1,..., и>, выпук- лы на Иг, д;(х) = (а(,х) — Ь, с = сп Е !,..ч в; Хо — выпукло, замкнуто и Х> с Иг, пусть в задаче (!),(8) 1„ > -сю, Х, р' ЯГ.
Доказать, что для того чюбы функция Лаграюка задачи (1), (8) имела седловую точку, необходимо и достаточно, чтобы неравенство (21) выполнялось с показателем»=!. Указание: необходимость см, в лемме 1; для доказательства достав точности пРименить теоРемы 6, 4.6.4 к задаче Ф(х, А) = 1(х)+ А А, дд(т) — > !и[, хЕ Хе. [83, 2-е издание]. с=! 20. Пусть каноническая задача линейного программирования У(х)=(с,х)->!и1, хеХ=(хЕЕ": т>0, Ах=Ь), Ь ЕЕ"', Ь>0, '4"., ь*с ' имеет решение.
Докажите, что задача (44) равносильна следующей канонической задаче д(з) =< с, х > +М(и .(-... 4- и~) — > !и1, зЕЯ=(в=(и,х)сЕ хЕ"; и>0, х>0, и+Ах=Ь) (45) при всех достаточно больших М > 0 (М.метод [179; 259; 374; 471; 775]). Убедитесь, что л .—. =(Ь, 0) — угловая точка множества Я. Указание: рассмотрите задачу: У (з)=(с, х)->ш1, 1 з Е Я! — — (з =(а, х) АО, и+ Ах = Ь, и =0), равносильную (44), ограничение и =0 учтите с помощью штрафной функции Р(в) = ]и((, а > 0 и, пользуясь леммой 1 и теоремой 6 при р= и=1, еь — — О, А, = А[> (Л*), с= Л' — решение двойственной к (44) задачи, установите, что Р(в) — точная штрафная функция.
21. Пусть Х, — множество решений задачи (1), (8), Х,(А) — множество решений задачи Ф(х, А) = у(т) 4- АР(т) — > !и[, х с Хо, где функция Р(х) взята из (9), Ф,(А) = си[ Ф(х, А), вСХ !ип Ф,(А) =Д. Можно ли тогда утверждать, что !и1 [х — д[ — >О при А ->+со. А ю * с х„у с х, (А ) У к а ванне: рассмотреть задачу [!8]: [(т)=шах(о>(х', х ); т(1-х', хз))-хз — >си[, хе х = =(х=(х', хз, тз, хв) СЕ4, д,(т)=т'<О, ~(х)=т(х, х!)-аз <О, д (т)=ы(х4, хз) — х'<О), ./2 2 где и(сч о) = у и + о с и — функция Белоусова — Андронова [84]; штрафную функцию взять з равной Р(т) = А (свах(дс(х); 0)); показать, что задача выпукла, Д =О, Х, = (х Е Е(; х( = 2 3 О ~ВО) Ф(!) [ Ь(24( !(2 Х(!) ( Е4.
! ! 2 2 3> 1 4 ( (хэр 1 + —, х >--+,0< 2 < — ); убедиться, что 1!ш Ф (А) =О, йш !и1 [х— 8(' 2 2( ' 2А А * А оо*ЕХ.,уЕХ,(А) — д] =+оо. Другие примеры, другие типы сходимости Х,(А) к Х„исследованы в [! 8-20]. 22. Применить метод штрафных функций к задаче; 1(м) = и — > !и[, и Е У =(и Е Уос д(м) = 2 (. — 4 < 0), где Уо — — (и с Е: и > -а], 0 < а <+со Показать, что ири 0 < а <+оо задача ! -1-и имеет сильно согласованную постановку (в (21) взять в = т = 1, с! — — >„1 + а(, 7 = — ).
Чю 2 ' будет при а= Есо? Проверить, что условия лемм 5.15.1, 5.15.4 не выполняются при всех а, 0 < а < -(-оо. 9 16. Доказательство необходимых условий экстремума первого н второго порвдков с помощью штрафных функций 1. Начнем с необходимых условий первого порядка †дад другое и, по. видимому, более простое доказательство правила множителей Лагранжа, отличное от изложенного в $ 4,8 и не опирающееся на теорему отделимости и теорему о неявных функциях, для задачи 1'(х) †«10[, х Е Х> ([) Х=-[ШЕХО:д(Х)<0, 2=[,...,>П; д((ш)=0, 2'=т+[,..чэ).
(2) Как и в $4.8, введем функцию Лагранжа задачи ([), (2) л,(х, Л)=Ле[(х)+ Я,' Л(Я,(ш), хЕХ~, с=! Л=(Л„...,Л,), Л,>О,...,Л„>О. (3) ТеоРема [. ПУсть Хо — выпУклое замкнУтое множество из Ж", фУнкЦии ['(х), дс(х), 2 = 1,..., з, опдеделень( но Х . ПУсть п — точка локального минимума в задаче ([), (2), пусть функции 1(ш], д,.(х), 2=[, 340 Гл. б. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ >;е 4 !6. ДОКАЗАТЕЛЬСТВО НЕОБХОДИМЫХ УСЛОВИЙ ЭКСТРЕМУМА 341 лх"й* " ..., з, непрерывно дифференцируемы в некоторой окрестности 0(е, в)Г! П Х, точки и. Тогда существуют числа Ло, Л„..., Л„такие, что л =(лщ...,л,)ФО, л,>о,л, >О,...,л >О, (4) (С (в, Л), х — е) > 0 Чх Е Хо, (5) Л,. да(в) = О, а = 1,..., ап. (б) Как видим, в этой теореме на задачу (1), (2) наложены более жесткие ограничения, чем в теореме 4.8.1, что связано со способом доказательства, использующим штрафные функции.
Множество всех Л, удовлетворяйощих условиям (4) — (б), как и выше, будем обозначать через Л(е) — это конус Лагранжа. В $4.8 было замечено, что конус А(и) выпуклый, а конус Л(е)(> 0 (ОЕ замкнутый, Д о к а з а т е л ь с т в о теоремы 1. Введем функцию до(х) = Т(х)+~х — е!з, хЕХо, множество И',хчХоГ!Я(е, Т), где о(е, У)=~хЕБ": !х — в)<Т), Т>0. Так как в — точка локального минимума функции Е(х) на Л, то можем считать число Т столь малым, что Т < ! и Е(х) > Е(в) Чх е Х и о(в, Т), Рассмотрим вспомогательную задачу минимизации д(х) — а!п1, хЕИе=ТхЕИЕ: д(х)<0, а=1,...,тп; д (х) = О, а ах аг! + 1,..., а) (7) Так как д (х) > Е'(х) > Е'(е) при всех х Е И', х Ф в, причем до(в) = Е'(е), то ясно, что е — единственное решение задачи (7) и д, = !п! д (х)= е Иа = 7'(е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
