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

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

Метод Ньютона [2] является прямым обобщением метода отыскания корня уравнения ϕ(x) = 0 , где ϕ(x) – функция

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

0 = ϕ(xk +1 ) ≈ ϕ(xk ) + ϕ′(xk )(xk +1 − xk ) .

Тогда при определенных условиях можно улучшить приближение к значению корня следующим образом:

xk +1 = xk − ϕ′(xk ) .

ϕ (xk )

Нас интересует n-мерная задача оптимизации, сводящаяся фактически к определению корня уравнения f (x) = 0 . Разложение в ряд Тейлора в этом случае дает:

0 = f (xk +1 ) ≈ f (xk ) + Q(xk )(xk +1 − xk ) ,

где Q(xk ) – матрица Гессе. Отсюда

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

при условии, что существует обратная матрица Q−1 (xk ) . Эта

формула и определяет метод Ньютона минимизации функции. Если функция квадратичная

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

где Q – положительно определенная матрица то, исходя из произвольной начальной точки x0 с помощью полученной выше формулы можно получить следующую точку:

x1 = x0 − Q−1 (b + Qx0 ) = −Q−1b .

Эта точка является точкой минимума квадратичной функции. Таким образом, для квадратичной функции метод Ньютона оп-

ределяет точку минимума за один шаг.

66

1.3.3.2. Сходимость метода Ньютона

На сходимость метода Ньютона большое влияние оказывает матрица Гессе. Одной из причин расходимости метода является то, что матрица Гессе не является положительно определенной. В этом

случае функция будет увеличиваться в направлении Q−1 (xk ) f (xk ) ,

а не уменьшаться. Кроме того, матрица Гессе на протяжении всего процесса должна быть невырожденной, так как необходимо существование обратной матрицы.

Если матрица удовлетворяет этим условиям и, кроме того, является ограниченной и удовлетворяет условию Липшица, то

существует некоторая окрестность точки минимума x* , такая, что для любой начальной точки x0 из этой окрестности метод Ньютона сходится с квадратичной скоростью:

Таким образом, для сходимости метода начальная точка x0 должна выбираться достаточно близко к искомой точке минимума x* .

Подводя итог, можно следующим образом сформулировать достоинства и недостатки метода.

Недостатки:

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

сходимость метода зависит от выбора начальной точки x0 . В

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

Достоинства:

вблизи точки минимума метод обеспечивает более быструю сходимость, чем градиентные методы;

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

Ниже приводятся некоторые модификации метода Ньютона, направленные на устранение указанных выше недостатков.

67

1.3.3.3.Метод Ньютона с регулировкой шага

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

xk +1 = xk − ρk Q−1 (xk ) f (xk ) ,

где 0 < ρk ≤1 (обычному методу Ньютона соответствует ρk =1 ).

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

Существуют два способа выбора параметра ρk . Первый способ заключается в следующем:

1) выбирается ρk =1 и вычисляется точка x = xk + pk , где pk = −Q−1 (xk ) f (xk ) ;

2)вычисляется f (x) = f (xk + pk ) ;

3)производится проверка неравенства

f (x) − f (xk ) ≤ (ερk < f (xk ), pk >) , 0 < ε < 12 ,

4) если это неравенство выполняется, то в качестве искомого значения ρk берем ρk =1 . В противном случае производится

дробление ρk до тех пор, пока неравенство не выполнится.

При втором способе значение ρk выбирается из условия минимума функции в направлении движения:

f (xk − ρk Q−1 (xk ) f (xk )) = min f {xk − ρQ−1 (xk ) f (xk )} .

ρ≥0

Преимущество данного способа модификации метода Ньютона состоит в том, что метод сходится при любом выборе начального приближения x0 . Скорость сходимости при этом остается

квадратичной, трудоемкость каждой итерации увеличивается. Однако при первом способе выбора параметра ρk трудоемкость каждой итерации несколько увеличивается.

68

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

Замечания. Как было отмечено в п. 1.3.3.2, на сходимость метода Ньютона большое влияние оказывает матрица Гессе. Если она не является положительно определенной, то метод расходится. Если она положительно определенная (т.е. выпуклая f (x) ), то метод сходится в

окрестности точки минимума.

Определить, является ли матрица положительно определенной можно, используя либо критерий Сильвестра, либо собственные числе матрицы Гессе. Матрица будет положительно определенная, если все угловые миноры матрицы положительны (критерий Сильвестра) или все собственные числа матрицы положительны.

В качестве примера рассмотрим следующие задачи. Задача 1. Рассмотрим функцию

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

Проверить является ли для данной функции матрица Гессе положительно определенной?

Решение. Градиент функции имеет вид:

f (x) = 4x1 + cos(x1 + x2 ) . 2x2 + cos(x1 + x2 )

Следовательно, согласно критерию Сильвестра Q(x) –

положительно определенная матрица.

Задача 2. Проверить положительную определенность матрицы Гессе функции:

f (x) = 4x12 − x22 − 2x1x2 + 6x1 − x2 − 2 .

Решение. Легко установить, что матрица Гессе данной функции будет:

По критерию Сильвестра матрица Гессе не является положительно определенной, так как её главный определитель

= −16 − 4 = −20 < 0 .

Проверим полученный результат, используя собственные числа матрицы Гессе:

Как видим, не все собственные числа положительны. Следовательно, матрица Гессе – не положительно определенная. Метод Ньютона расходится.

1.3.4. Метод переменной метрики (метод Девидона)

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

70