Lection 10

ЛЕКЦИЯ 10	1

Лекция 10

МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

Рассмотрим задачу

f(x) → inf; x X = En;

(1)

ãäå f(x) C1(En). Согласно определению дифференцируемой

функции

f(x + h)

−

f(x) =< f′(x); h > +o(h; x)

(2)

ãäå

lim o(h; x)

h

−1 = 0

|

h

|→

0

|

|

Åñëè f′(x) = 0, то при достаточно малых

|

h

|

главная часть

̸

приращения (2) будет определяться величиной < f′(x); h >. В силу неравенства Коши-Буняковского

−|f′(x)| · |h| 6< f′(x); h >6 |f′(x)| · |h|;

причем если f′(x) ≠ 0, то первое неравенство превращается в равенство только при h = f′(x), а левое неравенство только при h = − f′(x), ãäå = const > 0. Отсюда ясно, что при f′(x) ≠ 0 направление наибыстрейшего возрастания функции f(x) в точке x совпадает с направлением градиента f′(x), à

направление наибыстрейшего убывания с направлением антиградиента −f′(x).

Это замечательное свойство градиента лежит в основе ряда итерационных методов минимизации функций. Одним из таких методов является градиентный метод.

Градиентный метод

можно по-

2	ЛЕКЦИЯ 10

Этот метод, как и все итерационные методы, предполагает выбор начального приближения некоторой точки x0 . Общих правил выбора начальной точки x0 в градиентном методе нет (впрочем, как и в других методах). В тех случаях, когда из геометрических, физических или каких-либо других соображений может быть получена априорная информация об области расположения точки (или точек) минимума, то начальное при- ближение x0 стараются выбрать поближе к этой области.

Итак, начальная точка x0 выбрана. Тогда градиентный метод заключается в построении последовательности {xk} по правилу

xk+1 = xk + kf′(x); k > 0; k = 0; 1; ... :

(3)

Число k из (3) называется длиной шага (èëè шагом градиентного метода). Åñëè f′(xk) ≠ 0, òî k > 0 можно выбрать так, чтобы f(xk+1) < f(xk). В самом деле, из (2) имеем

( )

f(xk+1) − f(xk) = k −|f′(xk)|2 + o( k) k−1 < 0

при всех достаточно малых k > 0.

Åñëè f′(xk) = 0, òî xk стационарная точка. В этом случае процесс (3) останавливается и, при необходимости, проводится дополнительное исследование поведения функции в окрестности точки xk для выяснения того, является ли точка xk îïòè- мальной точкой или нет. В частности, если f(x) выпуклая функция, то в стационарной точке всегда достигается минимум.

Существуют различные способы нахождения величины k в методе (3). В зависимости от способа выбора k

лучить различные варианты градиентного метода. Рассмотрим несколько наиболее употребительных на практике способов выбора k .

ЛЕКЦИЯ 10	3

1. Íà ëó÷å x = xk − f′(xk); > 0, направленном по антиградиенту введем функцию одной переменной

gk( ) = f(xk − f′(x));	> 0;
è k определим из условий
gk( k) = inf gk( );	k > 0:	(4)
>0

Метод (3), (4) принято называть методом наискорейшего спуска. Ïðè f′(xk) ≠ 0 (согласно формуле g′(t) =< f′(x + + h); h >; g′′(t) =< f′′(x + h)h; h >; 0 6 t 6 1) имеем

gk′ (0) = −|f′(xk)|2 < 0

поэтому inf в (4) может достигаться только при k > 0. Приведем пример, когда величина k , определяемая в (4), суще- ствует и может быть выписана в явном виде.

Пример. Дана квадратичная функция
f(x) =	1	< Ax; x > − < b; x >;	(5)
	2

ãäå A = (aij) симметричная положительно-определенная матрица порядка n×n, b вектор из En . Можно показать, что эта функция сильно выпукла, и ее производные вычисляются

по формулам
f′(x) = Ax	−	b; f′′(x) = A:

Поэтому метод (3) в данном случае будет выглядеть так:

xk+1 = xk − k(Axk − b); k = 1; 2; ... :

Таким образом, градиентный метод для функции (5) представляет собой хорошо известный итерационный метод решения системы линейных алгебраических уравнений Ax = b.

4	ЛЕКЦИЯ 10

Определим k из условий (4). Пользуясь формулой

f(u + h) − f(u) =< Au − b; h > +12 < Ah; h >

имеем

				2
gk( ) = f(xk) − |f′(xk)|2			+		< Af′(xk); f′(xk) >; > 0:
				2
Ïðè f′(x		) = 0 условие
	k	̸
	gk′ ( ) = −|f′(xk)|2 + < Af′(xk); f′(xk) >= 0
äàåò
k =		|f′(xk)|2	=		|Axk − b|2	> 0:
	< Af′(xk); f′(xk) > < A(Axk − b); Axk − b >
Поскольку функция gk( )			выпукла, то в найденной точке k

эта функция достигает своей нижней грани при > 0. Метод скорейшего спуска для функции описан.

Однако точное определение величины k из условий (4) не всегда возможно. Кроме того, нижняя грань в (4) при некотором k может и не достигаться. Поэтому на практике ограни- чиваются нахождением величины k , приближенно удовлетво- ряющей условиям (4). Здесь возможен, например, выбор k èç условий

	∞
gk 6 gk( k) 6 gk + k; k > 0;	∑
	k = < ∞			(6)
	k=0
или из условий
gk 6 gk( k) 6 (1 − k)gk(0) + kgk;	0 <		6 k 6 1:
				(7)

Величины k; k из (6), (7) характеризуют погрешность выполнения условий (4): чем ближе k ê íóëþ èëè k ê 1, òåì

ЛЕКЦИЯ 10	5

точнее выполняются условия (4). При поиске k из условий (6), (7) можно пользоваться различными методами минимизации функций одной переменной.

Замечание. Антиградиент −f′(xk) указывает направление быстрейшего спуска лишь в достаточно малой окрестно- сти точки xk . Это означает, что если функция f(x) меняется быстро, то в следующей точке xk+1 направление антигра- диента −f′(xk+1) может сильно отличаться от направления −f′(xk). Поэтому слишком точное определение величиныk из условий (4) не всегда целесообразно.

2. На практике довольствуются нахождением какого-либоk > 0, обеспечивающего условия монотонности: f(xk+1) < < f(xk). С этой целью задаются какой-либо постоянной > 0

и в методе (3) на каждой итерации берут k = . При этом для каждого k > 0 проверяют условие монотонности, и в случае

его нарушения k = дробят до тех пор, пока не восстановится монотонность метода. Время от времени полезно менять ,

пробовать увеличить с сохранением монотонности.

3. Åñëè f(x) C1(En) и градиент f′(x) удовлетворяет условию

|f′(u) − f′(v)| 6 L|u − v|; u; v En;

причем L = const известна, то в (3) в качестве k можно взять любое число, удовлетворяющее условиям

2

0 < "0 6 k 6 L + 2";

ãäå "0; " положительные числа, являющиеся параметром метода. В частности, при " = L=2; "0 = 1=L, получим метод (3) с постоянным шагом k = 1=L. Отсюда ясно, что если константа

6	ЛЕКЦИЯ 10

L большая или получена с помощью грубых оценок, то шаг k

â(3) будет маленьким.

4.Возможен выбор k из условия

f(xk) − f(xk − kf′(xk)) > " k|f′(xk)|2; " > 0

(9)

Для удовлетворения условия (9) сначала обычно берут некоторое число k = > 0, одно и то же на всех итерациях (например, k = 1), а затем при необходимости дробят его, т.е. изменяют по закону

k = i ; i = 0; 1; ... ; 0 < < 1

до тех пор, пока впервые не выполнится условие (9) (в лите-

ратуре такой способ определения k часто называют выбором шага по Армихо).

Допустим, что какой-либо способ выбора k â (3) óæå выбран. Тогда на практике итерации (3) продолжают до тех пор, пока не выполнится некоторый критерий окончания сче- та. Здесь часто используются следующие критерии: ( " > 0 заданное число)

1)|xk+1 − xk| 6 ";

2)|f(xk+1) − f(xk)| 6 ";

3)|f(xk+1)−f(xk)| 6 ";

|xk+1−xk|

4)|f(xk+1) − f(xk)| + |xk+1 − xk| 6 ";

5)|f′(xk+1)| 6 ";

6)иногда заранее задают число итераций,

7)возможны различные сочетания этих и других критериев.

К этим критериям окончания счета нужно относиться крити- чески, т.к. они могут выполняться и вдали от искомой точки

ЛЕКЦИЯ 10	7

минимума. К сожалению, надежных критериев окончания сче- та, которые гарантировали бы получение задачи (1) с требуемой точностью, и применимых к широкому классу задач, пока нет.

Сходимость метода скорейшего спуска

В теоретических вопросах, когда исследуется сходимость метода, предполагается, что процесс (3) продолжается неограниченно и приводит к последовательности {xk}. Здесь возникают вопросы, будет ли полученная последовательность {xk} минимизирующей для задачи (1), будет ли она сходиться к множеству точек минимума

		inf f(x)	}
	X = {x En | f(x) = f = En
или, иначе говоря, выполняются ли соотношения
	lim f(xk) = f ;	lim (xk; X ) = 0		(11)
	k→∞	k→∞
Äëÿ	положительного ответа	на эти вопросы	íà	функцию
f(x)	накладываются дополнительные (кроме условия f(x)

C1(En)) более жесткие ограничения.

Далее рассматриваются вопросы сходимости для метода скорейшего спуска, когда в (3) величина k выбирается из условия (6).

Теорема 1. Пусть f = inf f(x) < ∞; f(x) C1(En).

x En

Тогда последовательность {xk}, полученная методом (3); (6) при произвольном начальном приближении x0 такова, что

lim f′(xk) = 0. Если при этом множество

k→∞

M (x0) = {x En | f(x) 6 f(x0) + };

8 ЛЕКЦИЯ 10

где взято из (6); ограничено, то

lim (xk; S ) = 0;

k→∞

ãäå

S = {x M (x0) | f′(x) = 0}

множество стационарных точек функции f(x) íà M (x0).

Теорема 2. Пусть выполнены все условия теоремы 1 и, кроме того, f(x) выпукла на En . Тогда для последователь- ности {xk}, определяемой условиями (3); (6) имеют место соотношения (11). Если, кроме того, в (6)

{ k} = O(k−2);

то справедлива оценка
0 6 f(xk) − f 6 c0k−1;	co = const > 0:	(14)

Теорема 3. Пусть f(x) C1(En); f(x) сильно выпукла на En . Тогда для последовательности {xk}, получаемой из

(3); (6) при любом начальном приближении x0 , справедливы соотношения (11): Åñëè ïðè ýòîì { k} = O(k−2), то имеет место оценка (14): Åñëè K = 0; k = 0; 1; 2; ..., то верна более сильная, чем (14) оценка

0 6 f(xk) − f 6 (f(x0) − f )qk;

|xk − x |2 6 2 (f(x0) − f )qk; k = 0; 1; 2; ... ;

ãäå x точка минимума f(x) íà En , q = 1 − =L; 0 6 q < 1,> 0 константа из критерия

f(x) сильно выпукла < f′(u) − f′(v); u − v >> |u − v|2: