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