Ф.П. Васильев - Методы оптимизации (1125241), страница 94
Текст из файла (страница 94)
Поэтому эти методы часто называют локальными методами, На практике для решения многоэкстремальных задач локальные методы обычно используются следующим образом; на множестве зада!от некоторую сетку точек и, выбирая в качестве начального приближения точки этой сетки, с помощью того или иного локального метода находят локальные минимумы функции, а затем, сравнивая полученные результаты, определяют ее глобальный минимум. Однако ясно, что такой подход к решению многоэкстремальных задач весьма трудоемок и не всегда приводит к цели.
Поэтому представляют большой интерес методы поиска глобального минимума в многоэкстремальных задачах. Перейдем к изложению одного из методов покрытий, которые служат для решения многоэкстремальных задач с целевой функцией, удовлетворяющей условию Липшица. Ограничимся рассмотрением задачи минимизации на параллелепипеде: У(х) ч!п1, хЕП=(х=(х',..., х"): а; < хг < Ьг, а =1,..., п), (1) где а,, Ь, — заданные числа, а! < Ь,, а функция 7(х) удовлетворяет условию ~у(х) — 7(у)~ < Х )х — у) !Ух, у е П, (2) где ? = сопз! > О, !х — у) = шах !хг — уг1 В правой части (2) можно было !<гсп поставить любую другую норму !х — у)„1 < р < оо, например, евклидову норму ~х — у~, как это мы неоднократно делали выше, когда требовали условие Липшица от функции или ее производных.
В силу эквивалентности норм в 316 г . з, методы минимизАцни фунКЦИИ' многих пеРЕМЕННИХ $13. МЕТОД ПОКРЫТИЯ В МНОГОМЕРНЫХ ЗАДАЧАХ 317 й — й,.! (4) 1 Л" условие Липшица в любой норме может быть сведено к виду (2), А норма !х — у! здесь привлекает нас тем, что такие множества, как параллелепипед, куб удобно описывать с помощью именно такой нормы. Так, например, множество (х ЕЛ"; !х — х„! < !й/2)=(хЕЛ": )х' — х!!()й/2, й =1,..., и) представляет собой куб с центром в точке х, ребром длины Ь и с гранями, параллельными осям координат. Именно такими кубами мы будем покрывать параллелепипед П. Кроме того, использование нормы ( ( позволит нам изложить многомерный вариант метода покрытий для решения задачи (1) также просто, как в одномерном случае (см. 9 1,7, п. 4).
На параллелепипеде П введем сетку Пй, состоящую из точек х! =(х,.', хй,..., х! !..., х,"), ~'-я координата х! которых при каждом 1 = 1,, и образована по йравилу (ср, с 9 1.7): ь х,'=а.+2, хе=х!'+йй, ..., х,'„,=х, +йй, ..., х,',, = х, + (гп, — 2)!й, х„, = ппп(х, + (пй — 1) Ь; 6,.), где )й = — — шаг метода, а натуральное число гпт определяется условием 2й Ь х, < Ь,. — — < х! +(гпз — 1)А.
В качестве приближения нижней грани /, в Ь задаче (1), можно взять величину пнп/(х! ! ) =Рй, которую можно найти п, с помощью простого перебора всех значений функции /(х) по точкам сетки П„. Справедлива Теорема 1. Для любой функции /(х), ддовлетворяюйцей условию (2), справедлива оценка /, <Рй </+е. (3) Доказательство. Кубы П! ! =(хЕЛ".
)х — х„! ) <!й/2) с центрами х„., Е П„покрывают весь йараллелепипед П. Это означает, что для любой точки х Е П найдется куб П !, содержащий эту точку, Отсюда и из (2) имеем: /(х) >/(х, й ) — Ь!х — х, ~ >Є— Л вЂ” = Р!, — е 'гхЕП. Переходя здесь к нижней'грани по х Е ййй, приходим к оценке (3). Метод простого перебора предполагает, что в каждой точке сетки Пй вычислены значения функции /(х), которые в определенном порядке пере- бираются с целью определения величины Р„. Однако, как и в одномерном случае, нетрудно указать более эффективные способы определения вели- чины Рй, которые, вообще говоря, не предполагают вычисления значений функций /(х) во всех точках сетки П„ и перебора всех точек этой.
сет- ки. Опишем один из таких методов последовательного перебора. На пер- вом шаге выбирается произвольная точка о, е Пй, вычисляется значение /(о!) и полагается Р! = /(о!). Допустим, что в точках о„ ою ..., ий сетки Пй уже вычислены значения функции /(о ),..., У(о ) и найдена величина Р, = ппп /(о!)=ш!п(Рй !;/(ой)), й > 2. Через о,. обозначим ту из точек !.!кй и ... о, в которой Рй =/(о, ).
Далее, возьмем любую из точек ой ! еПй, !! ° ! "й йй о ой ко орая в предыдущих шагах не исключалась из рассмотрения и в кот р " еще не вычислялось значение функции /(х). Вычислим значение /(ой,) )и величину Рй „= ш!п(Рй; /(ой !)) = ппп /(о,). Имеются две возможно- сти: либо Рй„! =/(ой !) < Р;, либо Р,, = Р, </(ой !). В первом случае, когда Рй ! < Р„полагаем оз =ой„, и из дальнейшего перебора исключаем точку о! и вместе с нею все точки х! ! е Пй, для которых а Заметим, что некоторые из этих точек могли оказаться исключенными из перебора уже на предыдущих шагах. Для нас важно лишь то, что среди исключенных точек заведомо нет таких, в которых значение функции /(х) было бы меньше, чем Рй Р В самом деле, У(оз ) = Рй > Р,й Р ДлЯ остальных исключенных точек х! й, не зная значения /(хй, ), можем сказать, что /(х„! ) — Рй,! — — /(х,, ) — /(о, )+Рй — Рй „, > — Л)х,, — о! !+Р— Рй„! >О в силу (2) и (4). Рассмотрим вторую возможность: Ф„„= Р„< У(о,. ).
Тогда полагаем о. = о. и из дальнейшего перебора исключаем точку о, вместе йй ~ йй йй! с точками х, , Е П„, для которых !х! ! — ойй!( < (5) Нетрудно убедиться, что и в этом случае в исключенных точках значения функции не могут быть меньше Рй Р В самом деле, здесь /(х!, )— — Рй „=/(х! ! ) — Рй =/(х„. ! ) — /(ой „,)+/(ойй!) — Рй > — Ь)х! — ой !)+У(о„!) — Рй >0 в силу (2) и (5). Общий шаг метода описан. Так как на каждом шаге метода берется новая точка сетки П„, которая еще не исключалась из перебора и в которой значение функции /(х) еще не вычислялось, то ясно, что на каком-то шаге описанного процесса перебора такая новая точка не найдется и процесс закончится за АГ шагов, Ж < т! пй, ...
т„, перебором точек оо ..., о, сетки Пй и определением величины Р, = ш!и /(о!) = ш!и/(х! ! ) = Рй. В силу теоремы 1 величина !я!ей ' п„ Р„ удовлетворяет неравенствам (3). П Как и в одномерном случае, нетрудно привести примеры, когда изложенный метод покрытий может превратиться в метод простого перебора точек сетки Пй. В то же время ясно, что если величины Рй — Рйй„ /(вй„!) — Рй в (4), (5) достаточно большие, то многие точки сетки П„ будут исключены из перебора без вычисления в них значения функции. Различные модификации метода покрытий на классе функций (2), обобщения этого метода на более сложные области, чем параллелепипед, на многокритериальные задачи, а также другие методы поиска глобального минимума читатель может найти, например, в !286; 309; 493; 526; 590; 591; 661; 662; 671], 9 14. Метод модифицированных функций Лагранжа 1.
Рассмотрим задачу /(х) — + !и1; х Е Х = (х Е Л" ! х Е Хт д(х)<0, й'=1,...,т, д(х)=0, й=т+1,...,е), (1) где /(х), д,(х),..., д,(х) — заданные функции на множестве Хх Пусть /„> > — оо, Х, фи. Для выпуклой задачи (1) при различных дополнительных 318 Гл.
З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ предположениях в $4.9 было установлено, что найдутся множители Ла, гранжа Л'=(Л;,, Л,*): Л*ЕЛ,=(Л ЕЕ*: Л, )О,..., Л )0) такие, что пара (х„Л"), где х, Е Х„образует седловую точку функции Лагранжа 5(х, Л) =7(х)+ Я Л,.д,(х), х Е Хю Л Е Лю (2) «=! Ь(х„Л) < Ь(х.«Л') =7„< Х (х, Л'), х Е ХФ Л Е Ло. (3) Была также доказана справедливость обратного утверждения: если (х„, Л*) Е Хо х Л, является седловой точкой функции (2), то х, Е Х„.
Основываясь йа этих фактах, можно предложить различные методы решения задачи (1), сводящиеся к поиску седловой точки функции Лагран>ка. Например, здесь естественным образом напрашивается итерационный процесс, представляющий собой метод проекции градиента по каждой из переменных х и Л (спуск по переменной х и подъем — по Л): т. е х„«, = Рх (х„— с«л5„(хл«Лл))« (4) Лл+« = Рл (Лл + глл7л(хл, Ль)) = Рл (Лл + оьд(х )), Ь =О, 1,, (5) где Однако, как оказалось, сходимость перечисленных методов удается доказать лишь при довольно жестких ограничениях на данные задачи (1), Приведем простейший пример выпуклой задачи, когда метод (4), (5) не сходится к седловой точке функции Лагранжа.
П р и м е р 1. Пусть ~(х) ш О, Х = (х Е Е'. д(х) = х = О). Тогда Г"„= О, Х, = (ОТ. ФУнкциЯ ЛагРанжа Ь (х, Л ) = Г(х)+ Лд(х) = Л х на Ха х Л = Е' х х Е' имеет седловую точку (О, 0). Процесс (4), (5) здесь имеет вид хл „, = х„— г«„Лл, Л,, = Л„+ глл хл, й = О, 1... Поскольку хлз,, + Л„', = (х„'+ Лл«)(1+ ал«) > хл«+ Лл«, «« =О, 1,..., то ясно, что при любых (х, Л ) ~0 и л|обом выборе длины шага с«„> 0 этот процесс расходится. 5,(хл, Л,) = (Х „, (х, Л),..., Ь„. (х, Л)), л л(х, Л = (л л (х, Л),..., л л (х, Л)) = (д,(х),..., д,(х)) = д(х); длину шага а„в (4), (5) можно выбирать из тех же соображений, как это делалось выше в $2. Заметим, что проекция любой точки Л Е Е' на множество Ла вычисляется просто по формулам Р„(Л) = (р,„..., !л,), где !л« =шах(Л,,О), « =1,..., т, |л,. =Л;, « =т+1,...,ж Вместо, (4) возможно использование других итерационных процессов, таких, как метод Ньютона и др.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
