4. МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ

Методы спуска и их различные модификации, методы случайного поиска (п. 5), которые используют только значения функции, называются методами 0-го порядка. Они обычно имеют весьма малую скорость сходимости. Поэтому разработан ряд методов оптимизации, которые используют первые и вторые производные целевой функции (методы 1-го и 2-го порядка).

Прежде чем рассмотреть такие методы, введем ряд обозначений и напомним некоторые определения.

Вектор n -мерного пространства Rn будем обозначать столбцом:

x1

u = ... ; тогда uT = [x1,..., xn ].

...

xn

Будем говорить, что функция f : Rn → R непрерывно дифференцируема в

точке x Rn , если производные					∂f (x)	, i =1,...,n	существуют и непрерывны. То-
					∂x
					i
гда градиент функции f			в точке x определяется как:
f (x)=	∂f (x)	,...,	∂f (x)	T .			(4.1)
			∂x
	∂x
	1		n

Будем говорить, что функция f (x) непрерывно дифференцируема в от-

крытой области D Rn , если она непрерывно дифференцируема в любой точке из D .

Пусть f : Rn → R непрерывно дифференцируема на некоторой открытой выпуклой области D Rn . Тогда для x D и произвольного ненулевого прира-

щения p Rn			производная по направлению p =[p1,..., pn ]T от функции f (x) в
точке x , определяемая как
	∂f (x)	≡ lim		f (x + εp) − f (x)	,
				ε
	∂p		ε→0

существует и равна f (x)T p , где символом '•' обозначено скалярное произведение.

Иначе можно записать

∂f (x)	T	n	∂f (x)
	= f (x)	p = ∑		pi .	(4.2)
∂p			∂x
		i=1	i
					26

Будем говорить, что
функция	f : Rn → R					дважды непрерывно дифференцируема в x Rn , если про-
изводные		∂2 f (x)			, 1	≤ i, j ≤ n , существуют и непрерывны.
		∂x	∂x	j
		i
Гессианом (матрицей Гессе) функции f в точке x											называется матрица
размера n ×n , и ее (i, j) -й элемент равен
							∂2 f	x
Hij	= f (x)ij					=	(		)	, 1≤ i, j ≤ n .	(4.3)
							∂x ∂x
							i		j

Пусть f : Rn → R дважды непрерывно дифференцируема в открытой области D Rn .

Тогда для любого x D и произвольного ненулевого приращения p Rn

вторая производная по направлению						p от функции f в точке x , определяемая
как
	∂2 f (x)		∂∂f	(x +εp)−	∂f (x)	(x)
					∂
		≡ lim	p		p		,
	∂p2			ε
		ε→∞

существует и для нее выполняется равенство:

∂2 f (x)	= pT f (x)p .	(4.4)
∂p2

Пусть A – действительная симметричная матрица размером n ×n . Будем говорить, что A положительно определена, если для любого ненулевого вектора

u Rn выполняется неравенство

uT Au > 0 .

Матрица A положительно полуопределена, если uT Au ≥ 0 для всех u Rn . Для того чтобы точка x* была локальной точкой минимума f (x) необхо-

димо выполнение равенства f (x* )= 0 . Достаточное условие, кроме того, требует положительной определенности f (x* ), а необходимое – по крайней мере, положительной полуопределенности f (x* ).

Далее будем полагать, что f (x) , f (x), f (x), существуют и непрерывны.

Все описываемые ниже методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

27

xk+1 = xk + λk s(xk ),

где xk – текущее приближение к решению x* , λk – параметр, характеризующий

длину шага, sk – направление поиска в n -мерном пространстве.

Рассмотрим метод первого порядка, использующий первые производные.

4.1. Градиентные методы

Градиент функции в любой точке x показывает направление наибольшего локального увеличения f (x) . Поэтому при поиске минимума можно попробо-

вать двигаться в направлении, противоположном градиенту в данной точке, то есть в направлении наискорейшего спуска. Такой подход приведет к итерацион-

ной формуле, описывающей метод градиентного спуска: xk+1 = xk −λk f (xk ) или

xk+1 = xk −λk			f (xk )		= xk −λk sk ,
			f (xk )

где f (xk ) – норма градиента и, соответственно, sk – единичный вектор.

(В качестве нормы вектора u можно выбрать так-называемую Гауссову норму

u = u12 +... +un2 .)

В зависимости от выбора параметра λ траектория спуска будет существенно различаться.

При большом значении λ траектория будет представлять собой колебательный процесс, а при слишком больших λ процесс может расходиться.

При малых λ траектория будет плавной, но и процесс будет сходиться медленно.

Параметр λk можно принимать постоянным или выбирать различным на каждой итерации. Иногда на каждом k -ом шаге параметр λk выбирают, произ-

водя одномерную минимизацию вдоль направления sk с помощью какого-либо одномерного метода. Обычно такой процесс называют методом наискорейшего спуска, или методом Коши.

Если λk определяется в результате одномерной минимизации, то есть λk = arg minλ f (xk + λsk ), то градиент в точке очередного приближения будет

ортогонален направлению предыдущего спуска (рис. 19).

28

Рис. 19. Иллюстрация к градиентным методам

Одномерная оптимизация вдоль направления sk улучшает сходимость метода, но одновременно возрастает число вычислений функции f (x) на каждой

итерации. Кроме того, вблизи экстремума норма f (x) близка к нулю и схо-

димость здесь будет очень медленной.

Эффективность алгоритма зависит от вида минимизируемой функции. Так, для функции f (x)= x12 + x22 метод Коши сойдется к минимуму за одну итерацию

при любом начальном приближении, а для функции f (x)= x12 +100x22 сходи-

мость будет очень медленной.

Вообще, эффективность этого метода на овражных рельефах весьма пло-

хая.

Этот метод используется очень редко.

4.2. Метод Нюьтона

Построим квадратичную модель функции в окрестности точки xk , разложив ее в ряд Тейлора до членов второго порядка:

fˆ (xk + p)= f (xk )+ f T (xk )p + 12 pT f (xk )p .

(4.5)

Найдем точку xk+1 = xk + sk из условия минимума квадратичной модели (4.5). Необходимым условием этого минимума будет fˆ (xk+1 )= 0 . Имеем:

fˆ (xk + sk )= 0 = f (xk )+ f (xk )sk

и это приводит к следующему алгоритму:

на каждой итерации k решить систему уравнений

29