Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 63
Текст из файла (страница 63)
В этом случае процесс (3) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки и, для выяснения того, достигается ли в точке и„минимум функции 1(и) или не достигается. В частности, если 1(и) — выпуклая функция, то согласно теореме 4.2.3 в стационарной точке всегда достигается минимум. Существуют различные способы выбора величины а, в методе (3). В зависимости от способа выбора а, можно получить различные варианты градиентного метода. Укажем несколько наиболее употребительных на практике способов выбора а,„ 262 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [ГЛ О 1) На луче (иовЕ": и=ид — аУ (ид), а~О), направленном по антиградиенту, введем функцию одной переменной Уд(а) У(и„— аУ'(ид)), а>0, н определим сод из условий Уд (ад) = 1п1 Уд (я) = Уд„ад ) О.
(4) аво Метод (3), (4) принято называть методом скорейшего спуска. При У'(ид) т-0 согласно формуле (2.3.1) Уд(О) = — [У'(пд) [о <О, поэтому нижняя грань в (4) может достигаться лишь при со,) О. Приведем пример, когда величина а„определяемая условием (4), существует и может быть выписана в явном виде. П р и м е р 1. Пусть дана квадратичная функция У(и) = — (Аи, и) — (Ь, и), (5) где А — симметричная положительно определенная матрица порядка п Х п, Ь вЂ” вектор из Е".
Выше было показано, что эта функция сильно выпукла и ее производные вычисляются по формулам У'(и)=Аи — Ь; У" (и)=А. Поэтому метод (3) в данном случае будет выглядеть так: ид.„=ид — ад(Аид — Ь), й О, 1, ... Таким образом, градиентный метод для функции (5) представляет собой хорошо известный итерационный метод решения системы линейных алгебраических уравнений Аи = Ь. Определим ад из условий (4). Пользуясь формулой (4.2ЛО), имеем Уд(а) У(и,) — а[У'(ид) Р+(а'/2) <АУ'(ид), У'(пд) >, со ~ О.
Р При У'(пд) ФО условие Уд(а) = — )У'(ид))'+ а(АУ (ид), У'(и,) > 0 дает ) У.(и ))д ) Аи Ь|о (АУ'(ид),,Г(ид)> (А(Аид — Ь), Аид — Ь) Поскольку функция Уд(со) выпукла, то в найденной точке ад эта функция достигает своей нижней грани при а> О. Метод скорейшего спуска для функции (5) описан.
Однако точное определение величины ад нз условий (4) не всегда возможно. Кроме того, нижняя грань в (4) при некоторых й может и не достигаться. Поэтому на практике ограничиваются нахождением величины ад, приближенно удовлетворяющей условиям (4). Здесь возможен, например, выбор сод из условий Уди(~~д([зд)((Удо+ бд, бд~)0, ~ ба= б<ос, (6) д-о 263 ГРАДИЕНТНЫЙ МЕТОД $0 или из условий (9) /а,(/ь(аь) ((1 — ЛА)/А(0) + Лд/„„0(Л~(ЛА~(1. (7) Величины 6„, Л, из (6), (7) характеризуют погрешность выполнения условия (4): чвм ближе 6, к нулю или Л, к единице, тем точнее выполняется условие (4).
При поиске аз из условий (6), (7) можно пользоваться различными методами минимизации функций одной переменной (например, методами гл. 1). Следует также заметить, что антиградиент ( — 1'(и„)) указывает направление быстрейшего спуска лишь в достаточно малой окрестности точки и„. Это означает, что если функция 1(и) меняется быстро, то в следующей точке иь„ направление антиградиента ( — 1 (и,+,)) может сильно отличаться от направления ( — 1'(и,)). Поэтому слишком точное определение величины а, из условий(4) не всегда целесообразно. 2) На практике нередко довольствуются нахождением какого-лнбо а, > О, обеспечивающего условие монотонности: 1(и„+,) < < 1(и„). С этой целью задаются какой-либо постоянной а > О и в методе (3) на каждой итерации берут а,=а. При этом для каждого й > 0 проверяют условие монотонности, и в случае вго нарушения а„=а дробят до твх пор, пока не восстановится монотонность метода.
Время от времени полезно пробовать увеличить а с сохранением условия монотонности. 3) Если функция 1(и)~Сгл(Е"), т. е. 1(и)шС'(Е"), н гра- диент 1'(и) удовлетворяет условию У'(и) — 1'(Р)! < Ии — Р!, и, о ш Е", причем константа Х известна, то в (3) в качестве а, может быть взято любое число, удовлетворяющее условиям 0 < е, < а„< 2/(Х + 2е), (8) где е„с — положительные числа, являющиеся параметрами метода. В частности, при е = Х/2, е, = 1/Х получим метод (3) с постоянным шагом а, 1/Е. Отсюда ясно, что если константа Х большая или получена с помощью слишком грубых оценок, то шаг а„в (3) будет маленьким.
Метод (3), (8) подробнее рассмотрим в следующем параграфе. 4) Возможен выбор аь из условия [11, 19, 56) 1(иА)-1(и,— а 1'(и,)) > еа,!1'(и) Р, е > О. (9) Для удовлетворения условия (9) сначала обычно берут некоторое число а, = а > 0 (одно и то же на всех итерациях; например, а„=1), а затем при необходимости дробят его, т. е. изменяют по закону а, = Л*а (в = О, 1, ..., 0 < Л < 1) до тех пор, пока впервые не вьшолнится условие (9).
264 мвтоды минимизации Фтпкции многих пзгкмкнных ~гл. з 5) Возможно априорное задание величин сз, из условий СО О аь>0, Й=О 1,...; ~~.", аз= со, ~~ а~а<со. м=а а=в (10) Например, в качестве а„можно взять а,=с(я+1), где с= сопз1> О, а число а таково, что 1/2(а(1. В частности, если а 1, с 1, то получим а, (я+1) ' (Й= О, 1, ...). Такой выбор (а„) в (3) очень прост для реализации, но не гарантирует выполнениЯ УсловиЯ монотонности У(ивы)(У(и„) и, вообще говоря, сходится медленно.
Более подробно о методе (3), (10) см. ниже в $3. 6) В тех случаях, когда заранее известна величина Хз = = Ы У (и) ) — со „в (3) можно принять Ев ссь = (Х(иь) — Хз) ~ Х (иь) ) где з, б, ( — заданные числа. Иногда заранее задают число итераций; возможны различные сочетания этих н других критериев. Разумеется, к этим критериям окончания счета надо относиться критически, поскольку они могут выполняться и вдали от искомой точки минимума. К сожалению, надежных критериев окончания счета, которые гарантировали бы получеяие решения задачи (1) с требуемой точностью, и применимых к широкому классу задач, пока нет. Сделанное замечание о критериях окончания счета относится и к другим излагаемым ниже методам.
В теоретических вопросах, когда исследуется сходимость метода, предполагается, что процесс (3) продолжается неограниченно и приводит к последовательности (и,). Здесь возникают вопросы, будет ли полученная последовательность (и,) минимизирующей для задачи (1), будет ли она сходиться к множеству точек минимума У,„=~ияяЕ", Х(и) = Х = ш1Х(и)), вп илн, иначе говоря, выполняются ли соотношения 1!ш Х(иа) Хз, Иш р(ид,6' ) = ОГ а.+ао з-+со (11) — это абсцисса точки пересечения прямой У= Хз с касательной к кривой Х =Яа) = Х(и„ вЂ” аУ'(и„)) в точке (О, ~,(0)).
Допустим,что какой-либо способ выбора аь в (3) (например, один из перечисленных выше способов) уже выбран. Тогда на практике итерации (3) продолжают до тех пор, пока не выполнится некоторый критерий окончания счета. Здесь часто испольауются следующие критерии: !и,— и,+Д ~е, или У(и„) — у(и,+,)! (6, или У'(и„)! ~ "(, ГР»диентныи метод Для положительного ответа на эти вопросы на функцию о(и), кроме условия Х(и)он С' (Е"), приходится накладывать дополни- тельные более жесткие ограничения. 2.
Подробнее рассмотрим зги вопросы для метода скорейшего спуска, когда в (3) величина а, выбирается из условия (6). ТеоРема 1. ПУсть Хо =1п1Х(и)) — оо, г(и) шСч'(Е"). ло Тогда последовательность (и„), полученная методом (3), (6), при произвольном начальном приближении и, такова, что 11шХ'(и») = = О. Если при этом мнолсество М, (и,) = (и ш Е": о (и) < 1(ио) + 6), где 6 взято из (6), ограничено, то Ишр(и»,Яо)=0, где Я » = (и ~ Мо(и ): У'(и) = О) — множество стационарных точек функции Х(и) на Мо(ио). Доказательство. Если при некотором )о>0 окал<ется, что У'(и»)=0, то из (3), (6) формально получаем и, и»+,=...
и утверждения теоремы становятся тривиальнымн. Поэтому бу- дем считать, что,1'(и„)ч»0 при всех (о=О, 1, ... Так как Х(и»+о) =- 1»(а») ( 1п17»(а) + 6»в-.У(и» вЂ” аУ'(и»))+ 6» при всех а>о а ~ О, то пз неравенства (2.3.7) при о = и„, и = и„— аГ(и,) имеем 1(и») — У(и»о,) > о(и») — У(и» вЂ” аП (и„) ) — 6» ~ > а!У'(и„) !' — Та'(П(и») !'/2 — 6, > а(1 — аУ2) !Г(и,) !о — 6» при всех а ~ 0 и (с = О, 1, ...
Следовательно, Х (и») — Х (и»+о) ) шах а (1 — аЛ(2) ! Г (и») (о — 6» = а>о = (1Я2Е)) ! У' (и») )о — 6» 7с = О, 1,, (12) Отсюда получаем ,~(и»о~)~~3(и»)+6», к=О, 1, (13) Так как У(и»))Х ) — оо ()с=0,1, ...), то из леммы 2.3.2 и (13) следует существование предела 11ш Х (и») ) Уо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
