XIV Аттетков и др. Методы оптимизации (1081420), страница 30
Текст из файла (страница 30)
нахождения стационарной точки функции ~(х). В данном случае в силу положительной определенности матрицы Гессе Н = Ц в стационарной точке функция Т" (х) достигает наименьшего значения. Таким образом, исчерпывающий спуск в направлении, определяемом вектором — Я г рас1 ~(хо) = Я 1го1 и обычно называемом ньюгпоновским направлением спуска, эквивалентен итерации метода Ньютона. При этом точка минимума положительно определенной квадратичной формы может быть найдена за одну итерацию., однако для этого нужно располагать матрицей Н 1 = ~ 1, обратной к матрице ~1 квадратичной формы.
Поскольку обращение матрицы (особенно высокого порядка п) является трудоемкой задачей, представляет интерес попытка сохранить преимущество изложенного подхода, но избежать обращения матрицы 0. 201 4. вт Сопряженные направления спуска Возвращаясь к рис. 4.10 (см. также рис. 4.3), обратим внимание на то, что последовательность исчерпывающих спусков в направлении антиградиента образует зигзагообразную траекторию приближения к точке минимума, причем все соседние звенья ломаной ортогональны. Это закономерно, поскольку прямая в направлении антиградиента ш на й-й итерации является касательной к линии уровня 7(х) = ) (х ), а направление антиградиента 2п ~' на (Й + 1)-й итерации перпендикулярно этой касательной.
Но исчерпывающий спуск в направлении любого вектора р~, приводящий в точку х", даст аналогичный результат: антиградиент яп"+1 = — 8гао2 (х") в этой точке будет ортогопялеп вектору р, т.с. (ю"~', р") = — (8гас11(х"), р ) = О, а Е К (4.57) Это равносильно условию завершения исчерпывающего спуска в точке, в которой производная функции 1(х) по направлению вектора р~ равна нулю. Для функции ) (х) = — (Ях, х) соотно- 1 2 шение (4.57) принимает вид (8гас1~(х ),р") = (с,)х",р ) =О, ЙЕИ (4.58) Если известны собственные векторы у~ и у2 матрицы Я второго порядка, то при произвольной начальной точке хз = = (хе» х~~) Е Ф любаЯ послеДовательность всего ДвУх исчеР- пывающих спусков в направлениях, коллинеарных этим векторам, приводит в точку х* минимума функции Дх) двух переменных, т.е.
зигзагообразная траектория состоит всего из двух звеньев. к„ 2 х~ 2 В самом деле, пусть сначала исчерпыи" и! вающий спуск коллинеарен вектору х' у (рис. 4.11), который соответствует О х~ меньшему собственному зна тению Л~ матрицы Я (поэтому вектор д' параллелен оси, проходящей через фокусы Рис. 4.11 202 4. численные метОДы БезУслОВнОЙ минимизлЦии эллипсов, являющихся линиями уровня функции Т" (х)). При этом точка касания прямой спуска и линии уровня Т (х) = Т' (х1) будет лежать на оси симметрии, параллельной вектору уз.
Поэтому второй исчерпывающий спуск вдоль этой оси приведет в точку х*. Ясно, что такой способ нахождения точки минимума нетрудно обобщить на и-мерный случай, хотя для реализации этого способа сначала нужно будет решить громоздкую задачу на собственные значения матрицы С1порядка и. Естествен вопрос: нельзя ли избежать нахождения собственных векторов матрицы Я, но все же сократить количество итераций при поиске точки минимума? Рассмотрим этот вопрос снова на примере двумерной за- 1 дачи для квадратичной формы Т'(х) = — (Ях, х).
Выберем начальную точку х и произвольное направление спуска, определяемое вектором р1, не обязательно сонаправленным анти- градиенту и~ = — СЗх функции Т'(х) в этой точке, но соста- вляющее с ним острый угол, т.е. х а ~ " у (Ях", р') < О. Проведя из точки Р~ В~--- Х~ Г 1 р. хв в этом направлении исчер- х' Р пывающий спуск, получим точ- Р ку х на линии уровня Т"(х) = = Т" (х1) (рис. 4.12). Затем выберем точку хв, не лежащую на прямой, проходящей через х и х', но такую, что (1Зхв,р') <О, и проведем исчерпывающий спуск из точки ж в том же направлении р .
В результате получим точку касания ж~ на линии уровня Т" (х) = 1(х'). Оказывается, что для получения искомой точки минимума достаточно провести исчерпывающий спуск из точки х' (или из точки х') в направлении р~, коллинеарном вектору х' — х' (см. рис.
4.12). Убедимся в этом, показав, что точки х' = О, х' и х' лежат на одной прямой, т.е, векторы х — х* и х — х* коллинеарны. 203 4.5. Сопряженные напрааяения спуска Умножим каждый из них скалярно на ненулевой вектор Яр и, учитывая, что матрица Я симметрическая, получим (Яж, р ) и (Ят1, р').
Каждое из этих скалярных произведений является производной функции ) (ж) по направлению вектора р в точках завершения исчерпыва1ощего спуска и поэтому в соответствии с (4.58) равно нулю. Так как эти векторы порознь ортогональны ненулевому вектору, то они коллинеарны. Итак, два исчерпыва1ощих спуска по несовпадающим параллельным прямым позволяют найти направление, исчерпывающий спуск по которому приводит в двумерном случае к искомой точке минимума. Описанный способ можно немного видоизменить. Выберем направление р исчерпывающего спус- 1 ка, совпадающее с одним из векторов стандартного базиса в 1я,', например с е, и таку1о начальную точку т Е яя на линии уровня Дж) = ~(1в~) = Сщ что (Ц1в~, е ) < О (рис.
4.13). В результате исчерпывающего спуска получим точку а на линии уровня у(х) = ) (ж~) = С1 < Са. Затем положим же = а1+ те~, т ~ О. Точка т11 линии уровня ~(х) = Дт~) = Ся не лежит на прямой проведенного исчерпывающего спуска в силу ортогональности векторов е1 и е~, но число т следует выбрать так, чтобы (Яже, е') у- 'О (иначе из этой точки не удастся провести второй исчерпывающий спуск в направлении, параллельном первому направлению).
После проведения такого спуска при- Рис. 4.13 204 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУ СЛОВНОЙ МИНИМИЗАЦИИ (Яр', рэ) = О, (4.59) верным в силу того, что при р = ~(х — х ), а каждое из скалярных произведений в правой части этого равенства в соответствии с (4.58) равно нулю. Следовательно, при помощи (4.59) точку минимума х' функции ?(х) = — (Ях, х) можно найти за две итерации.
Сначала выполним исчерпывающий спуск в произвольном направлении, определяемом вектором р, из такой точки х, что Ях,. р ) ( ( О, и найдем точку х1. Затем из (4.59) определим вектор рэ и в направлении, коллинеарном этому вектору, из точки х осу- 1 ществим исчерпывающий спуск в искомую точку минимума. Подробнее остановимся на процедуре нахождения вектора р~. Прежде всего вычислим Ях1.
Если Цх' = О, то х1 искомая точка минимума.. При С,1х ф О, полагая р = ?1р — ?~х, умножая это равенство скалярно на вектор Яр и используя дем в точку х' на линии уровня ~(х) = ?(х1) = С1 ( Сщ Теперь для нахождения точки х* достаточно выполнить исчерпывающий спуск из точки х' (либо из точки х') в направлении р~, коллинеарном вектору х' — х' (см. рис. 4.13). Проверку этого утверждения можно провести аналогично предыдущему случа,ю.
Таким образом, точку минимума в двумерном случае можно найти, выполнив всего три итерации. Есть ли еще возможность уменьшить число итераций? Такая возможность основана на существующей зависимости между направлением р завершающего исчерпывающего спуска в точку х" минимума и параллельными направлениями двух предшествующих спусков, коллинеарными вектору р1. Эту зависимость можно выразить соотношением 205 4.ач Сопряжеяныс направления спуска (4.59), получаем (Цр', у1р' — Ях') = О, откуда В частном случае может быть у1 = О, и тогда рк = — Ях1 ~ О. Отметим, что р~ ф О и при у1 ~0.
Иначе Ях' =у1р1 и с учетом (4.58) мы имели бы )Ях' ~в = у1 ~Ях', р1) = О, что противоречит принятому условию ся'х~ ф О. Направление исчерпывающего спус:ка, коллинеарное вектору р, зависит от знака производной (цх', ря) минимизируемой Функции в точке х' по направлению этого вектора.
Если (Ях', р~) ( О, то спуск происходит по направлению вектора р, а если (Ях, ра) ) О, то в противоположном направлении. Векторы р1 и рк, удовлетворяющие условию (4.59), называют сопрязссенными относительно матрицы Я (или с,)-ортогональными), а направления, определяемые такими векторами, сопряэсенными направлениями. Понятие сопряженности векторов является обобщением понятия их ортогональности. Действительно, если Я = 1я, то (4.59) переходит в условие ортогональности векторов р' и р~. Дадим соответствующее определение для системы векторов в и-мерном евклидовом арифметическом пространстве Кп.
Определение 4.1. Ненулевые векторы р1 Е Ы', 1 =1, пк называют сопряженными относительно симметрической матрицы Я1 порядка и (или Я-ортогональными), если справедливы равенства (Яр', р') = О,. г, 1 = 1, гп, г' ф ). (4.60) Лемма 4.5. Система т векторов р' Е ~", 1 = 1, гп., сопряженных относительно положительно определенной матрицы (~ порядка и, линейно независима. 206 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ~ Предположим обратное. Тогда существует нетривиальная линейная комбинация этих векторов: т а р'=О, 1=1 (4.61) в которой среди коэффициентов в. есть ненулевые, например а, у'= О.
Умножим обе части (4.61) скалярно на Яр1 и с учетом (4.60) получим а, ~фр', р') = О. Но положительно определенная квадратичная форма Яр, р) для ненулевого вектора р = р' имеет положительное значение. Следовательно, в, = О, что приводит к противоречик1 и доказывает лемму. ~ Замечание 4.4. 1!сно, что изменение направления некоторых из векторов, сопряженных относительно матрицы ф на противоположное, не нарушает условия (4.61). Поэтому если система и векторов р' Е К", 1 = 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}
