Ф.П. Васильев - Методы оптимизации (1125241), страница 71
Текст из файла (страница 71)
При 7"'(х ) ф 740 согласно формуле (2.б.1) имеем д„'(0) = — [7"'(хь)[з < О, поэтому нижняя 236 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $ и ГРАДИЕНТНЫЙ МЕТОД 237 /(х) = я(Ах, х) — (Ь, х), (5) /'(х) = Ах — Ь; /л(х) = А )/'(и) — /'(и)) ( 5 ~)и — и~, и, и Е Б", хл+, — — хл — а,(Ах, — Ь), Ь =О, 1, \ я (8) 0 ( з < а, ( 2/(7 + 2«), )У (лл))~ )Ал — Ь!з (АУ'(*ь),У'(хл)) (А(А*« - Ь),лхг - Ь) > (9) (10) ~., 'ал =оо> Е ал < "«' а,>0, Ь=0,1, грань в (4) может достигаться только при а, > О, Приведем пример, когда величина а, определяемая условием (4), существует и может быть выписана в явном виде. П р и м е р 1. Пусть дана квадратичная функция где А — симметричная положительно определенная матрица порядка и х и, Ь вЂ” вектор из л>".
Выше было доказано, что эта функция сильно выпукла и ее производные вычисляются по формулам Поэтому метод (3) в данном случае будет выглядеть так Таким образом, градиентный метод для функции (5) представляет собой хорошо известный итерационный метод решения системы линейных алгебраических уравнений Ах = Ь. Определим а„из условий (4). Пользуясь формулой (4.2.10), имеем дь(а) = 7(хл) — а)1'(х„))'+ (а'/2)(А/'(х,), ~" (х )) а > О. ПРи 7'(хл) фО Условие д,,'(а) = — )7"'(х„))'+ а(А/(х„), У(хл)) — О „а Поскольку функция д„(а) выпукла, то в найденной точке ал эта функция достигает своей нижней грани при а >О. Метод скорейшего спуска для функции (5) описан.
Однако точное определение величины а, из условий (4) не всегда возможно. Кроме того, нижняя грань в (4) при некоторых й может и не достигаться. Поэтому на практике ограничиваются нахождением величины а„, приближенно удовлетворяющей условиям (4). Здесь возможен, например, выбор а„из условий д„,(дл(а„)<д„.+Ью б >О, 2,' бл — — Ь<оо, (б) л=о или из условий дл„~ (д„(ал) ( (1 — Л„)дл(0) + Л д „О ( Л ( Л„( 1. (7) Величины б„Л„из (б), (7) характеризуют погрешность выполнения условия (4): чем ближе ь„к нулю или Л, к единице, тем точнее выполняется условие (4). При поиске ал из условий (б), (7) можно пользоваться различными методами минимизации функций одной переменной (например, методами гл.
1). Следует также заметить, что антиградиент ( — /'(х,)) указывает направление оыстрейшего спуска лишь в достаточно малои окрестности точки х,. Это означает, что если функция /(х) меняется быстро, то в следующей точке х„, направление антиградиента ( — /'(х„,,)) может сильно отличаться от направления ( — /'(х„)).
Поэтому слишком точное определение величины а, из условий (4) не всегда целесообразно. 2) На практике нередко довольствуются нахождением какого-либо а > О, обеспечивающего условие монотонности: /(х„ „,) < /(х„). С этой целью задаются какой-либо постоянной а > 0 и в методе (3) на каждой итерации берут аь = а. При этом для каждого Ь > 0 проверяют условие монотонности, и в случае его нарушения а„ = а дробят до тех пор, пока не восстановится монотонность метода.
Время от времени полезно менять а, пробовать увеличить а с сохранением условия монотонности. 3) Если функция /(х) й Сь'(Е ), т. е. /(х) е С'(Л"), и градиент /'(х) удовлетворяет условию причем константа 5 известна, то в (3) в качестве а„может быть взято любое число, удовлетворяющее условиям где зщ з — положительные числа, являющиеся параметрами метода. В частности, при з = 5/2, ел =1/5 получим метод (3) с постоянным шагом а, = 1/5. Отсюда ясно, что если константа 7 большая или получена с по. мощью слишком грубых оценок, то шаг а„в (3) будет маленьким.
Метод (3), (8) подробнее рассмотрим в следующем параграфе. 4) Возможен выбор а, из условия 194; 374; 603); > (хл) > (хл — ал> (хл)) ~ )зал)> (хл)/ з > О. Для удовлетворения условия (9) сначала обычно берут некоторое число а, = а > 0 (одно и то же на всех итерациях; например, а„= 1), а затем при необходимости дробят его, т.
е. изменяют по закону а„= Л'а, ( = О, 1..., 0< Л < 1, до тех пор, пока впервые не выполнится условие (9). Такой способ определения а„в литературе часто называют выбором шага по Армихо 194]. 5) Возможно априорное задание величин а„из условий Например, в качестве а можно взять а, =с(й+ 1) ', где с =сопя(> О, а число а таково, что 1/2 < а < 1. В частности, если а = 1, с = 1, то получим а„=(й+1) ', Ь =О, 1,...
Такой выбор (а„) в (3) очень прост для реализации, но не гарантирует выполнения условия монотонности /(х„„) ( /(хл) и, вообще говоря, сходится медленно. Более подробно о методе (3), (10) см. ниже в й 3. 6) В тех случаях, когда заранее известна величина /, =1п1 (х) > — оо, в (3) и" можно принять = (Пхл) — И)/'(хл)! ' — это абсцисса точки пересечения прямой / = /, с касательной к кривой / = д„(а) = /(х, — ау'(х„)) в точке (О, д„(0)). Допустим, что какой-либо способ выбора а„в (3) (например, один из перечисленных выше способов) уже выбран. Тогда на практике итерации (3) 239 238 Гк 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ ч 1.
ГРАдиентный метОд продолжают до тех пор, пока не выполнится некоторыи критерии окончания счета. Здесь часто используются следующие критерии: (х„— хь„,( < г, или (/(х,) — /(х„,)! < г, или )/'(х,)) < г, или < г, или ~/(х,) — /(х, „)!+ !хс. — х, с! < г, !Л*ьч с) — у(*ьй где г > 0 — заданное число. Иногда заранее задают число итераций; возмож- ны различные сочетания этих и других критериев. Разумеется, к этим кри- териям окончания счета надо относиться критически, поскольку они могут выполняться и вдали от искомой точки минимума.
К сожалению, надежных критериев окончания счета, которые гарантировали бы получение решения задачи (1) с требуемой точностью, и применимых к широкому классу задач, пока нет. Сделанное замечание о критериях окончания счета относится и к другим излагаемым ниже методам, В теоретических вопросах, когда исследуется сходимость метода, предпо- лагается, что процесс (3) продолжается неограниченно и приводит к после- довательности (х„). Здесь возникают вопросы, будет ли полученная после- довательность (х„) минимизирующей для задачи (1), будет ли она сходиться к множеству точек минимума Х. = ( х е Е, /(х) = /„= !п1 /(х)/ или, иначе говоря, выполняются ли соотношения 1!ш /(х„) =/„Нш р(х„, Х„) =О, (11) Для положительного ответа на эти вопросы на функцию /(х), кроме усло- вия /(х) е С'(Е ), приходится накладывать дополнительные более жесткие ограничения.
2. Подробнее рассмотрим эти вопросы для метода скорейшего спуска, когда в (3) величина а, выбирается из условия (6). Теорема 1. Пусть /, =!п1/(х) > — со, /(х) Е С' '(Е"), Тогда по- следовательность (х„), полученная методом (3), (6), при произвольном начальном приближении хь такова, что !!ш /'(х„) = О. Если при этом множество М„(х ) =(хе Е": /(х) < /(х,)+ б), гдг б взято из (6), огра- ничено, то !!ш р(х„, Я„)=0, гдг Я, =(х ЕМ (х ): /'(х)=0) — множество стационарньсх точек функции /(х) на М,(хь).
Доказательство. Если при некотором й >0 окажется, что /'(х,) = =О, то из (3), (6) формально получаем х„= х„, =... и утверждения тео- ремы становятся тривиальными. Поэтому будем считать, что /'(хь) Ф 0 при всех й = О, 1,... Так как /(х„,,)=дс(а„)< !и! д„(а)+б„</(х„— а/'(х„))+б при всех а>0, то из неравенства (2,6.7) при у=х,„х=х„— а/'(х„) имеем /(х ) — /(х ч, ) > /(х ) — /(х„— а/'(х„)) — б > > а!/с(х„)!з — Еаз)/'(х„))з/2 — б„> а(1 — а5/2)!/'(х„)!з — б при всех а >0 и й = О, 1,... Следовательно, /(х„) — /(х„, ) > шах а(1 — аЬ/2)(/'(х,)(з — б, = аьь = (1/(2Ь)))/'(х,)/' — Б„й = О, 1,... (12) Отсюда получаем /(хь.,с) </(х„)+ Б„й =О, 1,...
Так как /(х„) > /„> — оо, й =О, 1,..., то из леммы 2,6.2 и (13) следует существование предела !пп /(х„) > /,. Тогда !!сп (Г(х„) — /(х„,)) = 0 и из (12) будем иметь !!ш /'(х„) =О. Наконец, пусть множество М,(х,) ограничено. Суммируя неравенства (13) по й от 0 до т — 1, получим /(х )</(х;,)+ ), 'б„</(хь)+Б, т=1,2,..., (13) т. е. (х ) е М,(х ). По теореме Больцано — Вейерштрасса ограниченная последовательность (х,) имеет хотя бы одну предельную точку. Пусть х, — произвольная предельная точка (х„) и (хя ) — ~ х„. Пользуясь непрерывностью /'(х), отсюда имеем !пп /'(х„) = /'(х,) =О, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
