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