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