Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 83
Текст из файла (страница 83)
Отсюда и из условия (3) следует .У(и) ~) ) и' (и») — Х ) и — и» ( ) ш»п Х (и») — е или Х (и) ) ш»п У (и») — е 1а»ачь 1~»~ФИ для всех и »и П. Переходя в левой части этого неравенства к нижней грани по и»н ХУ, будем иметь О( (шуп Х(и») — Хе(е для каждой функции У(и)'и»,У(Х). Это значит, что для описанного метода р„выполняется неравенство (4), что и требовалось. Однако покрывать множество ХУ шарами не очень-то удобно.
Гораздо проще и удобнее покрывать мноя»ество (2) параллелепипедами или кубами. Заметим, что шар Я(и», Л) содержит в себе и-мерный куб 'г'» = (и= (и1,...„и"): и» вЂ” Ь(иу -.и»»+ Ь, у = — 1,...,и), Ь = Л»» и- е/(ХУп) / 1 п» с длинои ребра 2Ь и с центром в точке и» = (и», ..., и»). Пользуясь этим обстоятельством, нетрудно покрыть параллелепипед (2) кубами следующим образом. Возьмем точки 1 1 »» 1 и»,»„=(и»,...,и;...и»„0 11=1,...,т, у=1,...,п, (5) где у-е координаты й„ ..., и',„у образованы по правилу и'; = а; + Ь (21 — 1), 1 = 1,..., т; — 1, и'. = шш(Ь;; а;+ Ь(2т; — 1)), а номер т, определяется условием и' .,(Ьу — Ь(ау + Ь(2т; — 1) = и' ., + 2Ь.
Тогда кубы »У» ..,;„с длиной ребра 2Ь=2ВУ'»'и и с центром в точке и» ., »„(1=1, ..., т», у=1, ..., п) покроют параллелепипед (2). Так как куб У», „;„принадлежит шару Я (и» ...;„, Л)„ 350 методы минимизАции ФункциЙ многих пегеменных [Гл, з — прямоугольник на плоскости а1. Введем обозначения Р, = ппп (г „Х(и1)...., Х(и,) ), В =з/Х, Ь=В/У2= е/(ХУ2), В1=В+(Х(и ) — г1)/Х,, Ь1 = В/У2, 1= 1, 2, ..., (6) где точки и„ и„ ... будут выбираться последовательно по правилам, указанным ниже; в качестве г', пока можем взять р, = =Х(и,), а вопрос о других, более удобных способах выбора В, будет обсужден ниже. Сначала последовательно определим точки и„...,и,„, и1=(и,', и,'), 1=1, ...,т„ 1' где и1 = а1 + Ь, 1 и' = ш1п(Ь;, 1 иьз1 = и1+ Ь+ Ьь 1 = 1,, т1 — 2' 1 1 (7) и' 1 + Ь + Ь 1), и', = а.
+ Ь, номер т, находится из условий и' <Ь, — Ь<Р1 1+ Ь+ Ь Затем положим 01 = ппп (Ь„...,й ) и введем прямоугольник ПФ = (и = (и1, и'): а,< и <Ь„а,<и'<и1 + д Так как система отрезков [и( — Ь, и1+ Ь1! (1 = 1,..., т,) покрывает отрезок (а„Ь1), то прямоугольник ХХ~, будет принадлежать 1' то объединение шаров Я(и1Р„„1„,В) (1,=1, ..., т„у=1, ..., и) покроет параллелепипед (2). Тогда, как было показано выше, метод р„, заключающийся в выборе точек (и„..., и ), т = = т,т,... по правилу (5), решает задачу (1) — (4) на классе функций 1Х(Х).
3. Рассмотренный выше метод (5) относится к так называемым пассивным методам — в нем все точки и1, ..., и задаются одновременно до начала вычислений значений функции. Между тем, если точки ио ..., и выбирать последовательно и при выборе очередной точки и1 как-то учитывать результаты вычислений в предыдущих точках и„..., и1 „то шансы найти величинуХз с той же точностью е >О за меньшее число вычислений, чем в описанном пассивном методе (5), имеются. Следуя 1139], опишем один такой последовательный метод, одномерный вариант которого был изложен в 3 1.7 (см. метод (1.7.3)).
Для простоты и наглядности этот метод сначала изложим для случая и = 2, когда ХХ = (и =(и', и'): а, ~ и' < Ь„а, < и' ~ Ь,) МЕТОД ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА 5 121 объединению прямоугольников П 1= (и= (иг,ие): о11 — Ь(и1(ц,'+ Ь1, и', — Ь = а, < и'( У1, + 11 1, т1, 1= 1,...,т,. Х(и)>Рт — е при всех ие= П П П. (8) Коли П~ П, то отсюда получим 0(Р— Х„(~е — задача 1' (1) — (4) решена. Допустим, что П12 Пт,. Тогда последовательно введем точки (1 21 ит „.; = ~~от+1, из), 1 1 и +„...,и„,, 1=1,...,т,— т„ где 1 Рт -~-1 — а1 + )н от +1+1 = от +1 +Й+Йт +и 1 — 11 ° ° ° в11 в11 от = п11п1Ь;, и,, + Й + Й,,), 1'2 = о1 + Й + 12т11 а номер т, определяется условиями ита -1( Ь вЂ” Й ~ ~ит1-1 +Ь+Ьт1-1.
Положим д = ш1п(Ь +„...,Ь,) и введем прямоугольник П = (и = (и1, и'): а, < и < Ь„оз — Й < и' (~ из + д~ ), принадлежащий объединению прямоугольников П„„1= (и = (и1, и'): и,„е; — Ь((и <от+1 + Ь,„еи 1 1 1 о, — Й(из(У, + дт ), 1 = 1, ..., т, — т1. Так как Ь(11 <Ь1 (1= 1,...,т1), то для любой точки и = 1 = (и1, из) е П, 1 имеем ~ и' — У1 ~~(Ь; =В1/'е'2, ) из — о, '~ (В1/У2, так что ) и — и1 ( = (( и' — У1 (1+ ~ ие — У21 ~2)пз(В1. Это значит,что П,д принадлежит шару Я(иь В,) (1=1, ...
т,). Отсюда следует, что прямоугольник Пт, покрывается системой шаров Я(ио В1) (1=1, ..., л1,). Возьмем произвольную точку и~ П,„П П. Тогда найдется шар Я(ио В1), содержащий зту точку, т. е. !и — и,~ ~В1. Отсюда, учитывая условие (3) и обозначения (6), получим Х(и)~)У(и1) — 1 ~и — и1~)У(и;) — ЬВ1 = Р1 — е)Р— е или 352 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [ГЛ. 5 Кан И ВЫШЕ, дОКаЗЫВаЕМ, ЧтО 11т,[С: Я(ит +итгт+1) (1= 1, ..., т1 — т,), и, кроме того, Х(и)>Р— з при всех иее11 И Г. Поскольку Г,>Е,,ТО объединяя последнюю оценку для Х(и) с оценкой (8), имеем где Е =Е () п,Е,=п, Если ([~ Е, то из (10) следует 0(à — У (е — задача (1) — (4) решена. Если же 77[;" Е,, то процесс продолжаем дальше.
ПУСТЬ ТОЧКИ и1 ит И ВЕЛИЧИНЫ Г 1 Г т йт дт Уже пайДены, пРЯмоУгольник Е, = Ет, () П, РассмотРен и показано, что з'( ) > Г, — Е, П Ь1 (11) Если УФ Е,, то рассматриваем точки (1 1 ит +1, . ° ., Кто+1, итд+1 = (утз+1~ з~-1)~ 1= 1,...,т,+1 — т„ где координаты Р,.[.1 вычисляются по формулам, аналогичным (7), (9), Р,"+1= Р,' + Ь+дт, Затем полагаем ат,+,—— ш[п[йт,-ь1, °" ...,Ь ~,+1), вводим прямоугольник Аналогично тому, как это делалось выше, устанавливаем, что этОт прямоугольник покрывается шарами Я (ит +и Нт~+1) (1 = 1,..., т,+1 — т,) и отсюда получаем неравенство у ( и ) > р + 1 е и ~ Ет,+1 И Ь', Ет,+, = Ет, () ~т, „, и т. д.
Нетрудно видеть, что этот процесс закончится за конечное число шагов при таком г, для которого Р -1(Ь1 — Ь~ (Р— 1+ + й + 1[т~ Р~ — ш1п ([Ь1[ Ул 1 + й + 1(т ~1 Ус Ет неРавенство (11) выполнЯетсЯ пРи всех и ы Г Из (11) следУет 0 ~ (Е, — Уа = = ш[п (Х(и1),..., Х(ит)) — У,(е длялюбойфункции У=У(и)~ ~ Е(Ь). Последовательный метод для решения задачи (1) — (4) для случая и = 2 описан. 353 МЕТОД ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА $!2] случае, когда и> 2. Кратко опишем такой метод в общем Аналогично (6) введем обозначения Р»= в»ш(Ь'»; и'(и»), ..., »(и»)), Л =е/Ь, Ь =И'»и =е!(»»и), (12) 1=1,2,..., где»» =П =[и=(и», ...,и ): а»((и1(Ь„а;(и'(а; + 1 1 1 + Ь +»» „1 = 2,..., и).
Если параллелепипед Д, не покрывает параллелепипед (2), то далев рассматриваем точки итп +1 ° итп т итп +» = ~»ттп +Ь . т Гит +»/т' 1 т ° ° . т »П2 — т»т п 1 ( 1 ' ' 1 l гдв номер т, и координаты»т',».» (» = 1, ...,т,— т,),определяются формулами (9), У~„+» — — ~У + Ь + 4... »4,+» = а;+ Ь (1 = 3, ..., и; 1=1, ..., т,— т,). Далее, полагаем»»„, =и 1 = П»»П [)»пт +1 ° ° Ьпп )»(тп = Ш1П [Ь», °, Ьпт ), дОКаЗЫВаЕМ, ЧтО Х(и))à — е, иеБЧ П (7, должая этот процесс дальше, найдем точки („1 п и,... и и +»=ти +» ...,»т +») 1=1,...,т,— т, „ где номер т, и координаты»т„, 1+» определяются по формулам, 1 аналогичным (7), (9), »тти» +» = ш(п [Ьп' опт» + й +»1пч»'т где точки и„..
и ие ... выбираются последовательно по следующим правилам. Сначала определяем точки / 1 т»1 и„..., и,, и»=(ит, ...,У»)т» =1, ...,т», 2 где номер т, и координаты и» (1=1, ..., »п»), вычисляются по формулам (7), причем величины Ь, Ь, берутся из (12), а о»» = =а;+Ь (»=2,...,и).
Полагаем»»' =ш»п[Ь„...,Ь ) и, как и выше, доказываем, что "г (и) ~ ~Ь'тп ет и е- =Вп П Пт 354 методы минимизАции Фгнкции многих пегеменных [гл, ь устанавливаем неравенство Х (и) в г' з — з, и ~ В,, П У, где Ч,=(и: а,(й<Ь„а,(й(Ь„а;(и'(аз+ Ь+ 4,)з 4,, = шш (Ь, +„..., Ь,), 4,, = шш (Ьп ..., Ь,). После это,з з го начинаем менять координату й, сначала берем ь ,+;= Р ,+ + Ь+ «(', и прн Рз,+« = а1+ Й (1 = 4,..., и) осуществляем перебор координат и', пз по описанной выше схеме до тех пор, пока при некотором тз не получим оценки Х (и) ~ )Р „— з — е, иен(Х „П (Х, Ч, =(и: а,<й(Ь„аз(й(Ь«, язв И „= ш1п (Ь„..., Ь „), а а „вЂ” минимальное среди чисел (А, полученных на последнем цикле перебора координат й, й, з з з соответствующем значению Р,+« = и, + Й+ д,, "затем берем Рз +з = Р „+ Й+ з('ы заново перебираем координаты и', и* и т.
д. Такое изменение координаты й закончится на некоторой итерации ш, установлением оценки Х (и) ) г" — е, иы сна, П У, где 9„~ =(и: а;(и~(Ь;, 1= 1,2,3; а;(и1(а~+ Далее, по такой же схеме изменяем координату й по закону й~+з — — й~+ Й+ д~~, затем — координату й и т.
д., продолжая этот процесс до тех пор, пока получившийся параллелепипед Р „ не покроет исходный параллелепипед У и не будет получена оценка Х(и)ЪР,— з, и«и У. Из атой оценки будет следовать, что О < г", — Хз < з для любой фиксированной фушьции Х = Х(и)~ну(Х). Так как на каждой итерации хотя бы од на координата увеличивается на величину, не меньшую, чем Й .
зl(ХУп), то описанным методом за конечное число вычислений значений функции Х(и)зи Ч(Ц будет определена величина Х» с требуемой точностью з ) О. Так же, как в случае функции одной переменной (см. $1.7), нетрудно привести примеры самых «плохих» функций из класса ()(Х), для которых описанный метод последовательного перебора превратится в пассивный перебор (5), и самых «хорошихэ функций из ЯЬ), для которых этот метод дает существенный выигрыш по сравнению с пассивным перебором (5). Численные эксперименты показывают (139), что перебор существенно сокращается, если в (6) или (12) принять гз Х(аз), где Х(и,) близко к Хз. Поэтому сначала полезно провести пред- з <2! МЕТОД ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА 355 варительное исследование функции /(и) на грубой сетке и получить грубую оценку для Х„, которую можно принять за Р<.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
