Другая модификация метода Ньютона

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

X_jm+i+1 = x_jm+i – a_jm+i· (f ''(x_jm)) ^–1·f '(x_jm+i),

a_jm+i ≥ 0, k = jm + i, j = 0, 1, 2, …, i = 0, 1, …, m –1.

Здесь m > 0 – целое число, определяющее количество шагов через которое происходит обновление матрицы вторых производных f ''(x). Этот метод занимает промежуточное положение между методом Ньютона и его модификацией I.

Схема модификации II метода Ньютона.

Метод сопряженных градиентов

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

Два вектора x и y называют Н - сопряженными (или сопряженными по отношению к матрице Н) или Н - ортогональными, если

(x, H·y) = 0. (9)

Сопряженность можно считать обобщением понятия ортогональности. В самом деле, когда Н = Е, х и у в соответствии с уравнением (9) ортогональны. Рассмотрим квадратичную функцию n - переменных

f (x) = a + (x, b) + ½ (x, H·x). (10)

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

Чтобы воспользоваться этим методом минимизации квадратичной функции (10) нужно знать n - взаимно сопряженных направлений S₀, S ₁, …, S _n-1. Эффективность таких направлений – самостоятельная проблема. Существует много взаимно сопряженных направлений S₀, S ₁, …, S _n-1 и способов их построения. Ниже излагается метод сопряженных градиентов Флетчера - Ривса, в котором выбор Н - сопряженных направлений осуществляется совместно с одномерной минимизацией f (х) по α..

Метод Флетчера – Ривса.

Этот метод использует последовательность направлений поиска, каждая из которых является линейной комбинацией антиградиента в текущей точке и предыдущего направления спуска. Метод изменяется к квадратичной целевой функции f (x) = a + (x, b) + ½ (x, H·x).

При минимизации ее методом Флетчера - Ривса векторы S_k вычисляются по формулам

S₀ = – f ' (x ₀), S _k = – f '(x _k ) + β _k-1·S _k-1 , при k ≥ 1.

Величины β _k-1 выбираются так, чтобы направления S _k , S _k-1 были Н – сопряженными.

Точка х _k-1 , определяется в результате минимизации функции f (х) в направлении S _k, исходящем из точки x _k, т.е.

х _k+1 = x _k + α _k·S _k, где α _k доставляет минимум по α _k функции f (x _k, α ·S _k).

Итак, предлагаемая процедура минимизации функции f (x) выглядит следующим образом. В заданной точке x₀ вычисляется антиградиент

S₀ = – f ' (x ₀). Осуществляется одномерная минимизация в этом направлении и определяется точка x ₁. В точке x ₁ сново вычисляется антиградиент – f ' (x ₁). Так как эта точка доставляет минимум функции f (x) вдоль направления S₀ = – f ' (x ₀), вектор f ' (x ₁) ортогонален f ' (x ₀). Затем по известному значению f ' (x ₁) по формуле (11) вычисляется вектор S ₁, который за счет выбора β ₀ будет Н – сопряженным к S ₀. Далее отыскивается минимум функции f (х) вдоль направления S ₁ и т.д.

Это и есть окончательный вид алгоритма Флетчера-Ривса. Как было замечено ранее, он найдет минимум квадратичной функции не более чем за n шагов.

Минимизация неквадратичной целевой функции.

Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x₀ на x_n+1, а счет заканчивается при ||f '(x_k+1)|| £ ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.

Схема алгоритма для неквадратичных целевых функций.

Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых β _k = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.