Ф.П. Васильев - Методы оптимизации (1125241), страница 88
Текст из файла (страница 88)
Поэтому дальнейший поиск точки х, имеет смысл проводить в гиперплоскости Г,. Для этого нужно найти какое-либо направление ры параллельное гиперплоскости Г,. Можно искать ры например, в виде 294 г, ь, методы минимизАцни Еунхций многиХ ПереМеииых пусть (4) (5) (6) (.4Рг,Р.) =О, о фУ', 0< й д < 1о— (7'(хг),рз?=О, О< у'< Ь < й, (Г(х), Г~(х))=0, 1~~р 0~~6 г <~ Условие параллельности р, гиперплоскости Г, дает равенство (Ар„р,) = =(АР„У(х,) — Роро) =О, . '. Ро=(Аро, Г(х ))/(Ар ро).
Поскольку Г(х) ф О, то р, фО. В самом деле, если бы р, =О, то Г(хг) = Р ро и согласно (3) тогда ? Г(х)?о = Ро(ро, 7(х)) =0 — противоречие с условием Г'(х,) ~ О. Йз р, ф 0 следует, что Ар, ф О. Положим х,= х, — о,р„о, >О, где величину о, будем определять из условия д,(о,) = ппп д,(о), д,(о) = Г(х, — ор,). С учетом равенств (3) имеем д,'(0) = (7(х~) Р~) =(7(х~) — 7(х1)+ РоРо) = = — ? Г'(х,)?о < О, поэтому о, > О, Тогда д,'(о,) =0= (Г'(х, — о,Р,), — Р,) = — (7'(хо), Р,) =О.
Заметим, что Г'(х ) — 7'(хо) = А х, — Ь вЂ” Ах, + Ь = о, АР,. Тогда в силу (3) и выбора р, получаем (У'(хо)~ У'(хо)) = (Г'(хг) Ро? = (7'(х1) % АР~ Ро) =О. Отсюда следует равенство ( 7 ( ,), г' ( ,)) = (,Г ( ,), р, + Роро) = о. Таким образом, первые две итерации метода сопряженных направлений для задачи (1) описаны. Показано, что (7'(х,), ро) =(7'(х,),7'(хо)) =О, (Ар, р,) =(Ар, р ) =О, (~'(хо), р,) = (~'(хо), р ) = (~'(хо), ~'(х,)) = (7'(х ), г'(хо)) =О.
Кроме того, заметим, что векторы Ар,, Ар, линейно независимы. В самом деле, если 7оАР + о, Ар, = О, то, умножая это равенство скалярно сначала на р, затем на рп получим 7, = 7, =О. Можем считать, что 7"'(х,) ф О, иначе х, = х, — задача (1) решена. Теперь у нас есть основание сделать следующее индуктивное предпо- ложение: пусть при некотором й > 2 уже найдены точки х,х„ ..., х,, х, = хг — ог рг, Ь = О, 1,, й — 1, где р,.
= Гг(х ) — Р,.рг, фО, Рг =(7'(хг), Арг,?((Арг „р,), а величины ог > 0 определены из условий д.(о )=т!пдо(о), дг(о) =7(х,. — орг), Ь =0,1,..., й — 1; гг~ог $9. метОд сопряженных нАпРАВлений 295 и, кроме того, пусть 7'(х,) ~ О, Ь = О, 1,..., й, и система векторов (Аро, Ар„..., Ар„) линеййо независима. Тогда множество Го=(х'Е":(АР. *- .„)=О, о=01 й 1) представляет собой гиперплоскость (аффинное множество — см. пример 4.1.5) размерности и — й. Поскольку из (5) следует (Ар,, х„— х,) = (р,, Ах„— Ахг„,) = (р,, ~'(х„) — 7'(хг „,)? =0 для всех Ь =О, 1,..., й — 1, то х„ е Г„.
Замечательно то, что х, е Г„, так как согласно (2), (5) (Арг, х, — х,) = (Арг, А 'Ь вЂ” х,) = (рг, Ь вЂ” Ахг„,) = = (р,, — Р(хг„,)) = О, о' = О, 1,..., й — 1. Поэтому дальнейший поиск точки х„целесообразно продолжать в гнперплоскости Г„. Для этого нужно найти направление р„, параллельное Г„ т. е. удовлетворяющее условиям (Арг, р ) = О, о = О, 1,..., й — 1. Будем искать ро в виде Заметим, что Ро =Г( о) — Рор (7) ,7'(хг) — 7" (хг„,) = Ах, — Ах, = огАР,, Ь = О, 1,..., й — 1. (8) Из (4), (6), (8) следует (Арг, р„) = (Ар,, Г'(хо) — Рг р„,) = (Ар„у'(хо)?— — Ро(Арг, р,) = (7'(хг) — Г'(хг,,), 7'(х„))о,.
' =0 для всех Ь = О, 1,..., 1о — 2 при лгобом выборе Р„в (7), Поэтому для параллельности направления р„ гиперплоскости Г„ остается удовлетворить равенству (Аро „ро) =О. Отсюда имеем (АР„„У'(х„) — Роро,) = = (Ар„ъ г'(х„)) — Ро (Ар„„р„,) = 0 или Р„= (Арь „7"'(х,)?7(АР, „р„,). ' ' (9) Заметим, что р„~ О, ибо в противном случае 7'(х„) = Р„р„ъ и тогда в силу (5) имеем ?Г'(х„)~'=Р„(Г'(х„), р„,) =О, что противоречит индуктивному предположению, Итак, учитывая выбор направления ро и равенства (4), имеем (Арг,р) =О, 1 фу', 0< о, у'< й. (10) Следующее (й + 1)-е приближение будем искать в виде хо о ~ = хо — оорю оь ~ 10, (1 1) где о„ определяется из условия д„(оо) = ппп до(о), д„(о) = Г(х„— ор ). (12) Поскольку до(о) — сильно выпуклая функция, то величина о, существует и единственна.
С учетом предположений индукции и формулы (7) имеем д„'(0) = (7'(х„), — р, ) = ( 7'(х„), — 7'(х„) + Р„р„, ) = — ? 7'( х„) /' < О. 297 $9. МЕТОД СОПРЯУКЕННЫХ НАПРАВЛЕНИЙ 296 Гл. з. метОДы минимизАЦии ФУнкЦий мнОГих пеРеменных Это значит, что а > 0 и д„'(а„) = 0 = (~'(хь„,), -рь) иаи (~'(х„,), р ) =О. (13) Отсюда нетрудно получить явное выражение дзя а, В самом деле, 0 = (У'(х„„,), р„) = (Ах„, — Ь, р ) = = (Ах„— а„АР, — Ь, рс) = (У'(х„), рь) — а„(АЄЄ). Так как р, ф О, то (Ар„, р,) Ф 0 и из последнего равенства вытекает Далее, заметим ~'(х„) — У'(хо+,) = Ах„— Ах„, = а„АР„, Отсюда и из (4), (5) имеем Ц'(х,,), р,.) = (1'(х„) — а, Ар„ро) = О, г = О, 1,..., й — 1.
Собрав все равенства (5), (13), (15), получим (у'(х,), ру) = О, 0 < о' < г < уо + 1. Из предположения индукции и равенств (16) следует (7'(х„+,), у'(х,)) = (Г'(х „,), ро + (7,р,,) = О, г = 1,..., )о, (УУ(х„„,), ~'(хо)) = (У'(х, „,), Р ) = О. (15) (16) Отсюда и из (6) имеем (у '(х,.), у'(ху)) = О, г ф у', О < (, у' ( уо + 1. Наконец, покажем, что система (Ар,..., Ар,,) линейно независима. В самом деле, если ТоАро+-~,АР, +...+ у,АР =О, то, умножая это равенство на ру скалярно, с учетом (10) получим уу(Арон ру) = О, у' =О, 1,..., й.
Так как ру фО, то (Арсп р ) > 0 и последние равенства возможны лишь при Ту = О, Тем самым все этапы индукции проведены, следующее (й + 1)-е приближение х„, построено. Если 7"(х„х,) = О, то х„„, = х, — решение задачи (1) найдено. пели же 7"'(хь..) ~0, то согласно индукции процесс можно продолжать дальше. Метод сопряженных направлений для задачи (1), заключающийся в построении последовательности (х,) по правилу (11), где а,, р. определяются из (7), (9), (12) (или (14)), ро = у"(хо), описан. Название этого метода объясняет следующее Оп редел е н не 1.
Векторы'Р„рп..., Р„называются соиряхсенньсми относительно матрицы А или А-ортогональными, если (р,, р,) = 0 при всех ( фу, 0 < (, у'( й. Нетрудно' видеть, что для квадратичной задачи (1) метод сопряженных направлений закончится за конечное число итераций нахождением точки х,.
В самом деле, векторы 7'(хо),у'(х,),...,7"'(х„),..., получаемые этим ме- толом, обРазУют оРтогональнУю системУ: (У'(х,.), У'(х.)) =О ( ~ ' Однак~ в и-мерном пространстве не может быть более и ненулевых взаимно оптогональных векторов. Следовательно, найдется номер й, 0 < й < и такои, что у'(х,) = О. Тогда х„= х„— решение задачи (1). 2. Перейдем к рассмотрению задачи ,Г(х) — ~1п(; х Е Х:— Е", (17) где функция 7(х) Е С'(Е"), причем в отличие от задачи (1) здесь 7(х) не предполагается квадратичной. Так как формула (9) содержит матрицу А, характеризующую квадратичную функцию (1), то описанный выше метод сопряженных направлений (7), (9), (1!), (12) не может быть непосредственно применен для решения задачи (17).
Поэтому сначала формулу (9) приведем к виду, не содержащему матрицу А. С учетом равенств (6), (8) числитель и знаменатель дроби (9) можно преобразовать так: (Ар У'(хь)) = (Г(х — ) У'(хо) Г(х )) " = (Г( 'о)~ (АР„„Р,,) = (Уо(х„,) — Уо(х,), Р„,)а,, ', = (Уо(хь,) Рь,)а„', = = (7'(х,,) Г'(х,) — фь,Р„) а„', = ~ 7'(х„,)(оа Тогда формула (9) запишется в виде (у (хо), у (х, ) — у'(х,)) ~ую( ))2 э (18) или (21) (22) где )ДхК) ( (19) )у'(хь )) Кроме того, вспоминая, чтодля функции(1) А =ух(х,), формулу(9) о о представить еще и в такой форме: (уо(х )р„п у (х )) (20) (У (хо)РО Р РС 1) Для квадратичной функции (1) все три формулы (18) — (20) дают одну и ту же величину,9„.
Но если функция 7(х) отлична от квадратичной, то из этих формул будут йолучаться, вообще говоря, различные значения Д,. В результате, отправляясь от соотношений (7), (11), (12), (18)-(20), при- дем к следующему описанию метода сопряженных направлений для зада- чи (17). Пусть х — некоторое начальное приближение.
Будем строить по- следовательность (хо) по правилам х, +, — — х — а рю )о = О, 1,..., Ро = ~ (хо) Рс. = У (хь) )второ — 1 величина а„определяется условиями а > О, д„(сх,) = ппп д„(а), д„(а) = У(хо — ссре), (23) хро а у)„в (22) вычисляется по одной из формул (18), (19) или (20). Отметим, что в варианте (20)-(23) метода сопряженных направлений требуется, что- бы 7(х) е С'(Е"), и поэтому на практике он применяется очень редко н лишь в тех случаях, когда матрица уо(х) вычисляется достаточно просто. э 9. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ 298 Гл. 5.
МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ ." пг Так как в задаче (17) квадуатичность функции не предполагается, то нельзя ожидать, что описанныи метод сопряженных направлений за конечное число итераций приведет к точке минимума функции 1(х) на .Е". Далее, точное определение величины сгь из условий (23) возможно лишь в редких случаях, поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Как показывает практика, эти погрешности, накапливаЯсь, могУт пРивести к томУ, что вектоРы (Рь) пеРестают Указывать направление убывания функции, и сходимость метода может нарушиться.
Чтобы бороться с этим явлением, метод сопряженных направлений время от времени обновляют, полагая в (22) (32 =О. Обозначим множество тех номеров й > 1, при которых принимается )уь =О, через 1,. Номера й Е 1 называются моментами обновления метода. Если метод используется без обновления, то 1,= и. На практике часто берут 1, = (л, 2п, Зп,..., где и-размерность рассматриваемого пространства. Возможны и другие правила выбора моментов обновления. Кстати, если 1, = (1, 2, 3,...), то метод (21) — (23) превратится в метод скорейшего спуска.
Если функция 1(ж) не является квадратичной, то для описанного метода сопрязкенных направлений равенства (5), (6), вообще говора, не выполняются. Однако, тем не менее, и я общем случае при любом выборе моментов обновления справедливы равенства (1'(х„„), рь) =О, (1'(хь), рь) = (1~(хь)(~, й = О, 1, (24) В самом деле, при Ь = 0 имеем 7)г —— 1'(ж!), поэтому (1'(жо), и!) = (1'(хо)(2, Из условий (23) при в =0 в случае ао >0 следует до (ого) =(1 (то — аэро),-ро) =-(1 (ж!), Ро) =О. Если же ао— - О, то х, =хо и 0(до (0)= — (1 (то), ро)= — (1 (хо)! <О, так что 1 (хо) =1 (х!)=О, (1 (х!), Ро) =О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
