Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

приблизительно пропорционально n3, что представляет собой большую величину уже при относительно небольших значениях n.

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

Основная итерационная формула метода имеет вид

где ηk – матрица, аппроксимирующая обратную матрицу Гессе, а λk – шаг, который выбирается путем минимизации функции в

направлении (− ηk f (xk )).

Кстати, формула (1.14) является общей для градиентных методов и метода Ньютона. В методе наискорейшего спуска роль ηk играет единичная матрица, а в методе Ньютона – обратная

xk = xk +1 − xk ,

gk = f (xk +1) − f (xk ).

Вкачестве начального значения η0 для организации рекуррентного процесса (1.15) принимается η0 = E , где E –

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

71

направлению. Доказательство этого может быть дано лишь для квадратичной функции

f (x) = a + x тb + 12 x тQx

с положительно определенной матрицей Гессе Q .

Оказывается, что роль матрицы Ak состоит в том, чтобы обеспечить сходимость матрицы ηk +1 к обратной матрице Гессе Q−1 , а роль матрицы Bk в том, чтобы обеспечить положительную определенность матрицы ηk +1 и в пределе исключить влияние произвольного задания матрицы η0 .

Действительно,

η0 = E ,

η1 = E + A0 − B0 ,

η2 = η1 + A1 − B1 = E + ( A0 + A1 ) − (B0 + B1 ),

kk

ηk +1 = E + ∑ Ai − ∑ Bi .

i =0 i =0

В случае квадратичной функции, сумма матриц Ai ( i =1, k ) при

k = n −1 равна обратной матрице Q−1 , а сумма матриц Bi равна

матрице E . Это легко доказать, если в начале показать с помощью математической индукции, что вырабатываемые методом Девидона векторы направлений x0 , x1 , …, xn−1 образуют множество Q-

сопряженных векторов.

Данный метод можно рассматривать как один из вариантов метода сопряженных направлений. Он решает задачу минимизации квадратичной функции за конечное число шагов, не превосходящее n.

n−1

Покажем, что ∑ Ai = Q−1 . Из соотношений (1.15), учитывая,

i=0

что f (x) = Qx + b , получим:

72

gk = f (xk +1 ) − f (xk ) = Q(xk +1 − xk ) = Q xk .

Принимая во внимание последнее выражение, можно записать:

то все слагаемые в формуле (1.16), кроме j-го слагаемого, равны нулю.

Таким образом, получаем:

n−1

Также нетрудно доказать, что ∑Bi = E .

i=0

Метод переменной метрики, так же как и метод сопряженных направлений, требует, чтобы нахождение минимума функции на данном направлении осуществлялось очень точно. В противном случае направления поиска не будут Q -сопряженными.

Если сравнить метод переменной метрики с методом сопряженных градиентов, то оказывается, что первый обеспечивает существенно более быструю сходимость, чем второй, но в большей мере подвержен влиянию ошибок вычислений. Поэтому часто используют метод переменной метрики со следующей модификацией: через конечное число шагов (обычно n ) осуществляют обновление матрицы ηk , т.е. полагают ηk = E , и

процесс начинается, как бы, сначала.

На рис. 1.26 приведена блок-схема метода переменной метрики с периодическим обновлением матрицы ηk .

73

Контрольные задачи

Ниже представлены контрольные задачи по методам поиска экстремума функций многих переменных. В работе [60] приведены решения данных задач.

Задача 1. Найти минимум функции

f (x) = 4(x1 − 5)2 + (x2 − 6)2 .

Поиск минимума осуществить с использованием метода Розенброка. В качестве начальной точки положить: x0 = (8, 9)T , значение ε = 0.6 для

остановки алгоритма. Составить блок – схему алгоритма. Задача 2. Найти минимум функции

f (x) = 4(x1 −5)2 + (x2 − 6)2 .

Поиск минимума осуществить с использованием метода Пауэлла. В качестве начальной точки положить: x0 = (8, 9)T , значение ε = 0.1для

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

Задача 3. Найти минимум функции

f (x) = 4(x1 −5)2 + (x2 −6)2 .

Поиск минимума осуществить с использованием метода наискорейшего спуска. В качестве начальной точки положить: x0 = (8, 9)T , значение ε = 0.1для остановки алгоритма. Составить блок – схему алгоритма. Сравнить полученные результаты с результатами решения данной задачи методом Розенброка и методом Пауэлла.

Задача 4. Найти локальный минимум функции

f (x) = 2x12 + x2 x1 + x2 2 .

Поиск минимума осуществить с использованием градиентного метода

результатами решения данной задачи при различных значениях величины шага по координатам аргументов x1, x2 .

Задача 5. Найти локальный минимум функции

f (x) = 2x12 + x2 x1 + x2 2 .

Поиск минимума осуществить с использованием метода наискорейшего спуска с оптимизацией величины шага по направлению спуска, число итераций M =10 . В качестве начальной точки положить: x0 = (0.5, 1)T Сравнить полученные результаты с результатами решения данной задачи при использовании градиентного метода с постоянным шагом.

75