И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 58
Текст из файла (страница 58)
О с н о в н о й ц и к л. Ч1. Вычислить множители Лагранжа л (хл) = (Х, (х"), ..., Ь (х")) по правилу Л (х") = [Ч1 (хл) (Ч1 (х )) ) [Чс' (х")) Ч1л (хл), где ф(хл) =(1,(хл), ..., 1„(хл)); Ч1(хл) — соответствующая си;с х и-матрица. ЧП. Вычислить й, = ппп ()ст (х ), 1 Е [1: 1]). ЧП1. Если а~ с + Ьл ~ р, то положить ал = ссл с и перейтн к шагу 1Х; если сха с + лл ~ (3, то положить схл = шах (р — Ь„ ссл с+ О) и перейти к шагу 1Х.
1Х. Вычислить множество индексов У, (хл) и векторы Чс(сал (х ), Ч~с (х")~ ! Е "тл(х ). Х. Вычислить значение и лл (х') и найти возможное направление поиска Ь (х'), решая следующую задачу найти агиш[п шах ((Чф,„(хл), Ь); — (Чсс(хл), Ь) ! Ейсл(х"П» лаз ал где 3=(й!(Ьс! 1, с=1, ..., и, ЬЕВ"). Х1. Если иссл. (х")) — з, то положить е = е/2 и перейти к шагу ХП; иначе перейти к шагу ХП1. ХП. Если а(а', то вычислить значение я~ло (хл) и прекратить вычисления, если д л (х") = О; иначе перейти к шагу 1Х. ХП1. Вычислить наименьшее целое сл ~ О такое, что 1,( +т)слй(хл))>О, 1=1..., сп; фал (х" + П лй (х )) та (х ) ~ (— Отс лз. Х1Ч.
Положить х'+' = хл+ 1)'л Ь(х'), й = Ь+! н перейти к шагу Ч!. зоз агй ппп 1Ге(х)+а ~;Г!(х), а)сс, кйх+ !! у=! (з.зт> то х есть также точка локального (глобального) минимума задачи 4. Теорема 4". Пусть выполняются все условия теоремы 4. Тогда если х решение задачи (б.37), то д о (х) = О, где у„о (х) определяется по (б.уб) при е = О. З. Аиалок метода зозмомиых вапразлеивй а задачах мвиимиаацвв почта двффереицируемых фувицвй 3 а д а ч а 5.
Найти агд ппп Ге (х) для заданной функции ксх ге ! В" -е В~ и заданного множества ограничений Хй(х)~г(х)~(0, 1=1, ..., т, хЕВ"). (з.зв1 309 Теорема 4. Пусть выполняются предположения 4 и (111) — для любого х ~ В" число линейно независимых векторов Ч /; (х), 1 ~ Е (1: т) таких, что !! (х) = 0 не превышает и, (Ы) — мйожесп!во Х~~(х1!'!(х)~0, 1=1, ..., т, хЕВ") имеет непустую внутренность, замыкание которой совпадает с Х ~. Тогда: 1) если алгоритм 4 останавливается в точке х', то у,е(х') = 0 и ~, ~!(х") = 0; /=! 2) если алгоритм 4 генерирует бесконечную последовательность (хк)» о с возрастающими значениями а, А = йы й„..., И! так, что после я! значения аа сохраняются постоянными и равными а, то любая точка накопления хе последовательности (х")к о о О, (хе) = — в'е (х') удовлетворяет условию д„-е(х') = О, ~1!(хе) = 0; / ! 3) если алгоршпм 4 генерирует бесконечную последовательность (х")к-е, для которой значения а„возрастают бесконечно часто при й = А„й„..., то последовательность (хе!)! ! не имеет точки накопления.
Теорема 4'. Пусть выполняются все условия теоремы 4, и пусть Х вЂ” компактное подмножество в Х+. Тогда существует число !х Е (О, оо) такое, ипо если х Е Х точка локального (глобального) минимума следующей задачи: найти х» — —, х,"+ — ~, ! 1, ..., и. [ Ч. Вычислить вектор ь 8(х», Ь) = — ~', (!»(х»1 ..., х»++, ..., х»)— "" С-1 — !» ~х», ..., х» — +, ..., х»)1е', где е, ! 1, ..., и — 1-й орт. Ч1. Найти вектор Ь = Ь» — решение следующей задачи линейного программирования: найти шах р при ограничениях »,в (г", Ь)+~(0; (Я~<(х»), Ь)+ (3(~0, !ЕЙ(х» а») — 1м-,Ь,~1, 1-1, ..., и. Ч11.
Найти число р,' из условия р'„тах(р(х»+ рЬ»~Х). Ч111. Вычислить шаговый множитель р„= пп!п(р', р"„). 1Х. Вычислить следующее приближение х"+' х'+ р»Ь». Х. Вычислить вектор г'+' = г'+ т» (О (х", Ь) — г'). Х1. Положить Ь = Ь + 1 и перейти к шагу 11. Теорема 5. Пусть выполнены предположен я 5 и (И) — область Х, высекаемая ограничениями !Б.дд), ограничена; ()о) — для заз!о (з.зз) Предположения 5. (») — !» — почти диффереицируемая функция) (Й) — функции (и / = 1, ..., и непрерывно дифференцируемые; Алеорип»м 6 Н а ч а л о. 1. Выбрать: начальное приближение х' ~ Х, произвольный вектор г' Е В"; положить Ь * О. Основной цикл. !1.
Найти числа р», у», и», е„, удовлетворяющие условиям теоремы 5. И1. Найти множество индексов 6' (х», а"), определяемое соотношением О(х», а») (!( — е»~($)(х»)ч.О, )* 1, ..., т). 1Ч. Вычислить хы 1 1, ..., и — независимые реализации случайных величин, равномерно распределенных на отрезках дачи б выполняются условия Слейтера; (о) — числа е», р», т», а», А = О, 1, ..., удовлетворяют следующим условиям: а»)0, а»)0, р"„)О, у»)0, й О, 1, ° ° ° ' ч~~~~ р"„* оо, ~~' (р,/а»)» ( оо1 ~ у' < оо; р 1а«у» -» 0 при й -«. оо; «-о 1໠— а»+, 1 -«-0 при й-«оо; а»-«-0 при й-~ оо; Р» з»-«.0 при й-«оо.
Тогда с вероятностью 1 предельные точки последовательности (х")» е, порожденной алгоршпмом б, принадлежат множеству Хе решений задачи б и последовательность (1» (х»))Г е почти наверное сходился. Замечание б. Если существует способ вычисления почти градиента й' (х) фУнкции 1» в точке х, то вектоР 8 (х», й) в (6.39) можно определять по формуле 0(х", й) =бе(х»), где х" — реализация случайной точки, равномерно ~аспредеаенной в и-мерном кубе со стороной а„ и центром в точке х . 6.
Стоааееачееава ааааег метода аеемеа«иа«хвапраааеаав 3 а д а ч а 6. Найти аги ш)п 1» (х) для множества Х, которое «их определяется неравенствами ~,( )(до 1Е1,; (а', х) ( Ьо 1Е 1»; 0(х,(с„1= 1, ..., п, где предположения б. («) — функции 1» и 1о «ч 1«, выпуклые и непрерывно диффереицируемы; (٠— множество Х ограничено. Стохастический аналог метода возможных направлений можно применить в тех случаях, когда либо аналитический вид целевой функции не известен, либо значения данных функций вычисляются с ошибками. Для получения направления движения й«в й-й итерации решают вспомогательную задачу линейного программирования. 311 Алгоритл» 6 Н а ч а л о.
1. Выбрать: произвольные начальные приближения х» ~ Х, г» ~ В"; начальные значения шатовых множителей р„у„, удовлетворяющие условиям теоремы 6; положительную константу сс; йо ! Е 1» — некоторые положительные числа. П. Положить Ь = О. Основной цикл. Ш. Вычислить в» = ар». 1'!!. Вычислить следующие множества индексов: 1,(х», е») = (ЕЕ1,(Ь,— е»(Л(х') Ь!); 1,(х», е») = (ЕЕ 1,(Ь! — в»<(а', х»)<Ь,); 1, (х', е») = (1 Е (1, ..., и) ! О ( х!» < е»); 1»(х», е») = (1Е (1, ..., и) ~) с! — е» < х" ( с!). Ч. Вычислить вектор Ь = Ь» — решение вспомогательной задачи линейного программирования: найти шах 6 при ограничениях !»,ь! (71! (х»), Ь) + 9,6 ( О, Е Е 1! (х», е,); (а', Ь)(0, 1~1»(х», е»); Ь, ~ О, 1Е 1, (х", г,); Ь; О, )Е1»(х», е»); — 1 < Ь! ( <1, 1Е (1, ..., и)! (г', Ь)+ 6<0. Ч1.
Вычислить следующее приближение х»+! х»+ р Ь». ЧП. Вычислить вектор Р— реализацию случайного вектора $, условное математическое ожидание которого равно Е(51(х», г»), ..., (х", г»)) =Щ»(х»)+г», где р — некоторое положительное число; 㻠— ограниченный слу- чайный вектор ошибки, измеримый относительно а-подалгебры, индуцированной величинами (х», г»), ..., (х», г»).
ЧП1. Вычислить вектор г»+! г»+ у ($» г») 1Х. Вычислить шаговые множители р»+! и у»+!, удовлет- воряющие условиям теоремы б. Х. Положить Ь = Ь + 1 и перейти к шагу 1П. Теорема 6. Пусть выполнены предположения б и, кроме того, имеют место условия: (1) — градиент функции 1» удовлетворяет условию Лини»ица 1Ц (х) — Ц,(у)(()»(х — у(, р(оо; 312 (И) — для задачи 6 выполнено условиг Слейтера) (й() — константа а такова, «по хе, й = О, 1, ..., принадлежит допустимой области Х; ((о) — ишговые множители Р„и 7», измеРимые относшпельно а-подалгебры З„, индуцираванной семейством случайных величин (хе, ге, ..., х", г") таковы, что для некоторых чисел Хо Уе[)ге[[+ 2Є— 3еУд -0 п. н; « Ерт ( оо, д~Р~ Еуо ( оо; о=о о=о ~, "Е(ус[)ге[+ Ре)1е(оо; е о Ю Е ро =, Е(И'Г!йе)(, ЕМ'( е-о Тогда последовательность (хо)е о, порожденная алгоритмом 6, такова, «по Д (хе))е о сходшпся почти наверное к 1о й п1(п 1о (х).
= «ех 7. Методы несмежных ааправлевай дла отысканвв точен локальных минамумов иеаыпуклой фувкаив ва невыпуклом множестве 3 а д а ч а 7. Найти аги пйп )о (х) для заданной функции «ел 7о: Е" -о- Е' и заданного множества Х (х(71(х) ~0, 1= 1, ..., т, хЕЛ"). Предположения 7. (1) — функции 1, (х), 1 = О, 1, ..., т — не- прерывно дифференцируемы; (11) — (п1 До (х) ) — оо. «ЯХ На каждой итерации приводимого здесь алгоритма решается (приближенно) некоторая вспомогательная задача выпуклого программирования (которая может быть заменена задачей линейного программирования).
Бесконечная последовательность приближений (хе)Г о сходится к множеству стационарных точек задачи 7, со- держащему точки, в которых выполняются необходимые условия локального минимума. Алгоритм 7 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо Е Х. 11. Выбрать величину ее из полуинтервала (О, 1). 111. Положить й = О. Ос н о в н о й ц и к л. И. Вычислить множество индексов 0'(х", ее) = (1[0(7';(х")(ее, 1~[1:т[), и положить « = «(хе, е ). Ч. Решая вспомогательную задачу, найти шах а (зяо) <Л,с1 313 при ограничениях (Ч1/(х»), й)+0<0, !бп; — (~У,(х), й)+о<О; (з.в»1 (й, й)<1, вычислить допустимые значения о, и й", ! й»1 = 1, такие, что о л 1»о(х», з»), где 0<5($»(1; о(х», е„), й(х», з») — точные решения вспомо- гательной задачи (5.40) — (5 41).
Ч1. Если а, ~ з», то перейти к шагу ЧП, если о» = О, то перей- ти к шагу Х; иначе (если 0 < о» < е, ) положить х"+' = х»; з».»~ = у„е»; й = й + 1, где 0 < у» ~ у < 1, и перейти к шагу 1Ч, ЧП. Решая задачу одномерной минимизации функции 1» (х'— — рй») на отрезке 10, ь»1, вычислить величину р„ удовлетворяю- щую условиям ~» (х' — р»й») ~ (1 — й») ~, (х») + йуом 0 < )» < й„< 1; »о» !п1 1»(х' — рй'), где ~» — длина наибольшего отрезка (х', х» — 1,»й»), принадлежа- щего множеству Х. ЧП1. Вычислить следующее приближение х'+' = х» — р,й'.
1Х. Положить з»+~ = е», й й+ 1 и перейти к шагу 1Ч. Х. Вычислить множество индексов Ч (х», 0) = (! ~ ~~ (х") = О, ! ~ (1: т)), н положить Р = о (х", 0). Х1. Найти величину о (х', О) — решение вспомогательной за- дачи (5.40) — (5.41). ХП. Если о(х', 0) = О, то положить х'= х» и прекратить вычисления; иначе перейти к шагу ХП1. ХП1. Положить х"+' = х»; в»+, — — у»е», где 0 < у»~ (у < 1: й = й + 1 и перейти к шагу 1Ч. Теорема 7. Если в»толняются предположения 7 и (И$) — функции 1, (х), » = О, 1, ...,т, аринадлеяаип классу С»а (Х) (если ф (х) ~ 5 Сга (Х), то суи!ествует число а ) 0 такое, что для любого от- резка (х, у], целиком принадлежим(его множеству Х, будет ! Ч ф (х) — Ч ф (у) /| < а ! х — у у; (йо) — сушрсо»вует такое чис- лоб)0, что(77~(х)(<бдлявсехх5Х, 1'=1, ...,т; (о)— множество Х'= (х»(о(х*, 0) =О, х'еХ) з»4 непусто (здесь а (х', 0) — решение вспомогапельной задачи (5.40)— (5.41) при ха = х', И = й (х', 0), где т[(хе 0) (1 ! 71 (хе) 0 ~Е [1 ' т[))1 (пз) — последовательность х', й = О, 1, ..., порожденная алгоритмом 7, компакп)на, то в случае бесконечной последовательности ха, й = О, 1, ..., справедливо предельное соотношение [пп [п[ [!хь — х*[=0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
