XIV Аттетков и др. Методы оптимизации (1081420), страница 31
Текст из файла (страница 31)
Далее для определенности примем, что это конкретное направление исчерпывающего спуска из двух возможных векторов ~р всегда задает вектор р . Отметим, что для произвольной системы линейно независимых векторов рз е Б'.", у = 1, и, .можно построить., используя процесс, аналогичный процессу ортогонализации Грама--- Шмидта, систему векторов, сопряженных относительно положительно определенной матрицы Я (систему Я-ортогонаяьных векторов).
Выбирая разные системы С„1-ортогональных векторов, мы получаем разные методы сопряженных направлений. 1 Теорема 4.8. Точку минимума функции ~(х) = — Ях, х) с положительно определенной матрицей Я можно найти не более 207 4.а. Сопряженные напраеяення спуска чем за гг итераций, определяемых рекуррентным соотношением х ' = х ' +асар", Й =1, и, где р" Е Кп — векторы, сопряженные относительно матрицы О, если на Й-й итерации задавать значение же по формуле исчерпывающего спуска (4.62) ~ Из рекуррентного соотношения для х получим в ае+~гг (4.63) Вычислим градиент 8тас1~(х) = Ях минимизируемой функции Дх) в точке х: бг а ~ О+~ г=! Умножая обе части последнего равенства скалярно на вектор рь и учитывая (4.60), находим ®х~,р ') = (Ях~, р )+~гсг(г,)р'гр ) = (Ях~, р ) +гсаЩр',р ).
Отсюда следует равенство (4.62), поскольку в случае исчерпывающего спуска в направлении р~ в соответствии с (4.58) имеем Ях",р") =О. Согласно лемме 4.5, векторы р' б К", 4 = 1, и, линейно независимы и их количество равно размерности линейного пространства. Поэтому они образуют базис в Кгг. Значит, любой вектор в Б'." можно разложить по системе векторов р'г г' = 1, и. В частности, имеет место представление (4.64) 208 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУ СЛОВНОЙ МИНИМИЗАЦИИ с некоторыми коэффициентами йг Так как функция ((ж) сильно выпуклая, то необходимым и достаточным условием достижения ек> наименьшего значения в точке а* является равенство 6гас1 ('(а') = Ц,в' = О.
Тогда из (4.64) имеем Умножая это равенство скзлярно на вектор р~ и учитывая (4.60), получаем — (сарж", рл) = бя Яр~, рв). Отсюда следует, что бь = хы к =1., и. Таким образом, коэффициенты разложения в (4.64) совпадают со значениями хь на первых и итерациях. Поэтому точку х' можно найти не более чем за и итераций вида т~ =:в~ 1+жир", к = 1, п, что равносильно (4.64). ~ Замечание 4.5.
Число итераций при поиске точки х' может быть меньше п. Дело в том, что при выборе начальной точки возможна такая ситуация, что (Я.в~, р ) = 0 для одного или нескольких номеров я. В этом случае из (4.62) следует, что на к-й итерации хь = 0 и поэтому в~ = т~ 1, т.е. й-я итерация, по существу, не проводится. Замечание 4.6. Используя (4.64) при Ь; = нп г' = 1,п, и (4.62), с учетом равенства Я = Я и правил выполнения матричных операций можно написать Поскольку в рассматриваемом случае ж* = О, то при произволь- ном выборе точки х" приходим к выводу, что (4.65) т.е. система векторов р', г = 1, и, сопряженных относительно положительно определенной матрицы ф позволяет достаточно просто построить матрицу ~1 ', обратную к ф В данном 209 Вопросы и задачи случае Цх = 8гас1 ? (х ) и поэтому можно заключить, что и итераций, проводимых при помощи (4.62) и (4.63), эквивалентны одной итерации х' = хо — Я '8гас1~(хо) метода Ньютона, но требующей предварительного нахождения матрицы Я 1, например, используя (4.65).
Однако система сопряженных векторов р', 1 = 1, и, заранее обычно не известна, и ее строят тем или иным способом последоватсльно в процессе проведения итераций (см. 5 и 6). В частности, такой путь используют при решении системы линейных алгебраических уравнений Ця = — с с положительно определенной матрицей 11, поскольку эта задача эквивалентна задаче минимизации квадратичной функции Р(и) вида (4.48). 1Г Рассмотренные вышо подходы к решению задачи минимизации квадратичной функции служат основой для построения многочисленных итерационных алгоритмов безусловной минимизации неквадратичных целевых функций. Наиболее употребительные из этих алгоритмов рассмотрены ниже (см.
5 и 6). Вопросы и задачи 4.1. Перечислите методы численного решения задач многомерной безусловной минимизации в зависимости от наибольшего порядка производных целевой функции, вычисление которых предусмотрено в этих методах. 4.2. Дайте опредепение релаксационной последовательности (х ) точек х~ Е К". Каковы особенности методов спуска,что является характеристикой их скорости сходимости? Как проводить оценку эффективности методов спуска? Перечислите алгоритмы, обладающие свойством квадратичной сходимости, на примере решения задачи минимизации сильно выпуклой квадратичной функции.
4.3. Дайте определение векторов рз Е Кп,. ? = 1, п, сопряженных относительно симметрической матрицы Я порядка п. 210 4. ЧИСЛЕННЫЕ МЕТОЛЫ БЕЗУ СЛОВНОЙ МИНИМИЗАЦИИ Покажите, что если Ц вЂ” положительно определенная матрица, имеющая в различных собственных значений, то собственные векторы этой матрицы, .отвечающие различным собственным значениям, являются сопряженными относительно Я. 4.4. Проанализируйте на примере поиска минимума квадратичной функции с положительно определенной матрицей ф имеет ли значение тот порядок, в котором выбираются направления исчерпывающего спуска в методе сопряженных направлений. Можно ли осуществлять поиск минимума квадратичной функции в одном и том же направлении более одного раза? 4.5.
Решите задачу минимизации функции 1(лмжз) = т1+ + яз — 8(ж1+жз), используя различные стратегии поиска по сопряженным направлениям, описанные в 4.5, и выбирая в качестве начальной точки (О, 1) и (О, 0). Установите,. влияет ли выбор начальной точки на количество итераций при поиске точки минимума.
Сравните полученные результаты с вычислениями по методу наискорейшего спуска и методу Ньютона. Можно ли с применением этих методов получить точку минимума при указанных начальных точках за конечное число итераций? Если да, то чему равно это число итераций? Дайте графическую иллюстрацию полученных результатов. 5. АЛГОРИТМЫ МЕТОДОВ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ Если ограниченная снизу целевая функция 1'(х), х Е К", является дифференцируемой на множестве л'.", то алгоритм поиска точки х' ее минимума можно построить, используя информацию, по крайней мере, о градиенте этой функции. Волос широкие возможности построения таких алгоритмов возникают в случае, когда целевая функция дважды дифференцируема, что позволяет использовать ео матрицу Гессе.
В этой главе применительно к минимизации дифференцируемых и дважды дифференцируемых функций рассмотрены алгоритмы методов первого и второго порядков соответственно. Общей чертой этих алгоритмов является построение реяаксационной последовательности 1х ) точек х Е К", получаемых при выполнении каждой к-й итерации, а различие состоит в используемой информации о целевой функции и ее производных. 5.1.
Алгоритмы метода градиентного спуска Направление спуска в методе градиентного спуска совпадает с направлением антиградиента минимизируемой целевой функции 1(х), дифференцируемой в К", а элементы релакео; ционной последовательности 1хь) строят при помощи рекуррентного соотношения вида (4.43) хь =х~ '+мьЯо~ =ха ' — хьвгад11х~ '), ня >О, к Е Ы, где ш = — огай~(х ) антиградиент целевой функции в точке х~ ~. При этом говорят, что из точки х~ на й-й итерации алгоритма происходит спуск с шагом спуска нь~ю~~. На первой итерации (й = 1) спуск начинают из выбранной начальной 212 оч МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ псоики хо. Различие алгоритмов метода градиентного спуска состоит в способе выбора значения мы Сначала рассмотрим способ выбора этого значения, характерный для метода дробления шага и обеспечивающий выполнение на каждой Й-й итерации неравенства ,У(х" ') — Т" (х ') > созга ~со ~~, (5.1) где со Е (О, 1), гарантирующего сходимость последовательности (~ис~~) к нулю (см.
4.3). Если на Й-й итерации не выполнено это неравенство при некотором начальном значении зсь = зсо, то процедуру дробления шага проводят в соответствии с формУлой зса — ьссзсо, где м б (О, 1) — заданный постоЯнный ыоэффициенпз дробления шага, а с номер этапа дробления, на котором неравенство (5.1) будет выполнено. В целом алгоритм с использованием дробления шага можно представить следук1щим образом. Выбираем начальную точку хо и параметр точности поиска ез > О в условии ~и~~~ < ез прекращения итераций, а также значения м и зсо. В неравенстве (5.1) обычно принимают со = 1/2. Вычисляем значение )'(хо) целевой функции Т" (х) в точке х, полагаем Й = 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}
