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