Метод градиентного спуска с дроблением шага

⇐ ПредыдущаяСтр 4 из 4

Метод градиентного спуска является одним из самых распространенных и самых простых методов решения задачи безусловной оптимизации. Он основан на свойстве градиента функции, согласно которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиградиента – с направлением наискорейшего убывания функции. При решении задачи безусловной минимизации за направление спуска из точки x ⁽ ^m ⁾выбирается p⁽^m⁾ = –g(x⁽^m⁾) = –f '(x⁽^m⁾). Таким образом, итерационная процедура (2.20) для этого метода имеет вид

x⁽^m⁺¹⁾ = x⁽^m⁾ – a⁽^m⁾g(x⁽^m⁾). (2.24)

Для выбора шага a⁽^m⁾ можно использовать процедуру дробления шага, которая состоит в следующем. Произвольно фиксируют начальное значение шага a⁽^m⁾ = a⁽^m ^–¹⁾ = a. Если в точке x⁽^m⁺¹⁾, вычисленной в соответствии с (2.24), выполняется неравенство

f(x⁽^m⁺¹⁾) > f(x⁽^m⁾),

то шаг дробится, например, пополам, т.е. полагается a⁽^m ⁺¹⁾ = 0.5a⁽^m ⁾.

Применим метод градиентного спуска с дроблением шага для минимизации квадратичной функции

f(x) = (Ax , x) + (b, x) + c

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

Алгоритм 2.1 (Алгоритм метода градиентного спуска с дроблением шага для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + + с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c , i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например, x= (0, 0, … , 0)^T, начальный шаг a и погрешность вычислений e > 0. Вычислить f ( x ).

Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно

g = (g₁, g₂, … , g_n)^T,

g_i = + b_i, i = 1, …, n.

Шаг 3. Для заданной точности вычислений e проверить выполнение критерия окончания вычислений.: ||f '(x)|| < e , Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x^* = x = (x₁, x₂, … , x_n)^T. В противном случае перейти к шагу 4 для продолжения итерационного процесса.

Шаг 4. Вычислить

y = (y₁, y₂, … , y_n),

y_i= x_i– a g_i, i = 1, …, n.

Шаг 5. Вычислить f(y).

Шаг 6. Если f(y) < f(x), то положить x = y , f(x) = f(y) и перейти к шагу 2, иначе – перейти к шагу 7.

Шаг 7. Положить a = и перейти к шагу 4.

Пример 2.3.

Найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.01.

Матрица этой квадратичной функции имеет вид:

2 0

A= 0 4 , b = (– 4, – 4)^T.

Критерий Сильвестра для функции f(x) выполнен:

D₁= 2 > 0, D₂ = 2 × 4 – 0 × 0 = 8 > 0.

Следовательно, функция f(x) имеет минимум.

Возьмем начальное приближение x⁽⁰⁾ =(x , x )^T = (0, 0)^T, положим e = 0.01и будем вести вычисления в соответствии с алгоритмом 2. 1.

Шаг 1. Полагаем x= (0, 0)^T, начальный шаг a = 0.6 и погрешность вычислений e =0.01. Вычисляем f(x) = 0.

Шаг 2. Вычисляем g = f '( x ) = Ax + b, или покоординатно

g = (g₁, g₂)^T,

g₁ = – b₁ = 2×0 + 0×0 – 4 = –4,

g₂ = – b₂ = 0×0 + 4×0 – 4 = –4,

Шаг 3. Проверяем выполнение критерия окончания вычислений.

||f '(x)|| = = > e. Переходим к шагу 4.

Шаг 4. Вычисляем

y = (y₁, y₂)

y₁= x₁– a g₁ = 0 – 0.6×(–4) = 2.4.

y₂= x₂– a g₂ = 0 – 0.6×(–4) = 2.4.

Шаг 5. Вычисляем f(y) = y + 2y – 4y₁ – 4y₂ = –1.920.

Шаг 6. Так как f(y) < f(x), то полагаем x = y = (2.4, 2.4)^T , f(x) = f(y) = –1.920 и переходим к шагу 2.

Результаты последующих итераций приведены в табл. 2.1.

Таблица 2.1

N	a	x₁	x₂	g₁	g₂	f(x)
1 2 3 4 5 6 7 8	0.6 0.6 0.6 0.3 0.3 0.3 0.3 0.3	0 2.4 1.920 1.968 1.987 1.995 1.998 1.999	0 2.4 -0.960 1.392 1.022 1.016 0.997 1.001	-4 0.8 -0.160 -0.064 -0.026 -0.010 -0.004 -0.002	-4 5.600 -7.840 1.568 -0.324 0.063 -0.013 0.003	0 -1.920 1.690 -5.692 -5.988 -5.999 -6.000 -6.000

Из табл. 2.1 видно, что на третьей итерации значение функции возросло по сравнению с предыдущим. Поэтому значение шага стало в два раза меньше, a = 0.3.

Вычисления прекращаются после 8-ой итерации, так как требуемая точность достигнута (||f '(x)|| = » 0.004 < 0.01).

Таким образом, x^* » (1.999, 1.001)^T и f(x^*) » –6.000.

Нетрудно убедиться, что существует точное значение точки минимума: x^* = (2, 1)^T и f(x^*) = 6.

Метод наискорейшего спуска

В методе наискорейшего спуска величина шага a⁽^m⁾из (2.24) находится в результате решения задачи одномерной минимизации

j⁽^m⁾(a) = f(x⁽^m⁾ – a g(x⁽^m⁾)) ® min, a > 0. (2.25)

На рис. 2.3 изображена геометрическая иллюстрация этого метода. Из начальной точки x⁽⁰⁾ перпендикулярно линии уровня f (x) = f (x⁽⁰⁾) в направлении p⁽⁰⁾ = –g⁽⁰⁾ спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча x⁽⁰⁾ – a g⁽⁰⁾ значение функции f. В найденной точке x⁽¹⁾ этот луч касается линии уровня f(x) = f(x⁽¹⁾). Затем из точки x⁽¹⁾ проводят спуск в перпендикулярном линии уровня направлении p⁽¹⁾ = –g⁽¹⁾ до тех пор, пока соответствующий луч не коснется в точке x⁽²⁾ проходящей через эту точку линии уровня и т. д.

Рис. 2.3

Для квадратичной функции f(x) = (Ax , x) + (b, x) + c с симметричной положительно определенной матрицей A эту задачу можно решить аналитически. Величина шага a⁽^m⁾, удовлетворяющая условию (2.25), равна (см., например, в [1])

a⁽^m⁾ = (2.26)

Опишем алгоритм метода наискорейшего спуска для квадратичной функции.

Алгоритм 2.2 (Алгоритм метода наискорейшего спуска для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + + с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c , i = 1, … , n; j = 1, … , n . Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например, x= (0, 0, … , 0)^T и погрешность вычислений e > 0.

Шаг 2. Вычислить g = f '( x ) = Ax + b, или покоординатно

g = (g₁, g₂, … , g_n)^T,

g_i = + b_i, i = 1, …, n.

В противном случае перейти к шагу 4 для продолжения итерационного процесса.

Шаг 4. (Шаги 4 – 7 используются для вычисления величины шага a⁽^m⁾по формуле (2.26)

Вычислить

B₁= (g, g) = .

Шаг 5. Вычислить

Ag = (A₁, A₂, … , A_n)^T, где

A_i = , i = 1, …, n.

Шаг 6. Вычислить

B₂= (Ag, g) = .

Шаг 7. Вычислить

a = .

Шаг 8. Положить

x = x – a g(x)или покоординатно x_i = x_i – a g_i, i = 1, …, n. Перейти к шагу 2.

Пример 2.4.

Как и в примере 2.3, найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.01. В примере 2.3. было установлено, что функция f(x) имеет минимум. Найдем этот минимум методом наискорейшего спуска.

Шаги 1 – 3 совпадают с шагами 1 – 3 примера 2.3.

Шаг 1. Полагаем x= (0, 0)^Tи погрешность вычислений e =0.01. Вычисляем f(x) = 0.

Шаг 2. Вычисляем g = f '( x ) = Ax + b, или покоординатно

g = (g₁, g₂)^T,

g₁ = + b₁ = 2×0 + 0×0 – 4 = –4,

g₂ = + b₂ = 0×0 + 4×0 – 4 = –4.

Шаг 3. Проверяем выполнение критерия окончания вычислений.

||f '(x)|| = = > e. Переходим к шагу 4.

Шаг 4. Вычисляем

B₁= (g, g) = = 32.

Шаг 5. Вычисляем

Ag = (A₁, A₂)^T, где

A₁= = 2×(–4) + 0×(–4) = –8,

A₂= = 0×(–4) + 4×(–4) = –16.

Шаг 6. Вычисляем

B₂= (Ag, g) = = (–8)×(–4) + (–16)×(–4) = 96.

Шаг 7. Вычисляем

a = = = .

Шаг 8. Полагаем

x₁= x₁– a g₁ = 0 – ×(–4) = ,

x₂= x₂– a g₂ = 0 – ×(–4) = .

Перейдем к шагу 2 для следующей итерации.

Результаты последующих итераций приведены в табл. 2.2.

Таблица 2.2

N	a	x₁	x₂	g₁	g₂	f(x)
1 2 3 4 5 6 7	0.333 0.333 0.333 0.333 0.333 0.333 0.333	0 1.333 1.778 1.926 1.975 1.982 1.997	0 1.333 0.889 1.037 0.988 1.004 0.999	-4 -1.333 -0.444 -0.148 -0.049 -0.016 -0.005	-4 1.333 -0.444 0.148 -0.049 0.016 -0.005	0 -5.333 -5.926 -5.992 -5.999 -6.000 -6.000

Вычисления прекращаются после 7-ой итерации, так как требуемая точность достигнута (||f '(x)|| = » 0.002 < 0.01).

Таким образом, x^* » (1.997, 0.999)^T и f(x^*) » –6.000.

Можно показать, что на m-ой итерации, m > 1, будут получены значения:

g^(m)= (1, (–1)^m)^T, a^(m) = , x^(m) = x^* – (2, (–1)^m)^T.

Существует точное значение точки минимума: x^* = (2, 1)^T.

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

До сих пор в итерационной процедуре градиентного спуска

x⁽^m⁺¹⁾= x⁽^m⁾+ a⁽^m⁾p ⁽ ^m ⁾

мы предполагали, что движение к минимуму функции производится в направлении антиградиента, p ⁽ ^m ⁾ = –g ⁽ ^m ⁾ . Для некоторых функций направление антиградиента в точке x⁽^m⁾ может значительно отличаться от направления к точке минимума x^*. В результате траектория приближения к точке минимума может иметь зигзагообразный характер. Метод сопряженных градиентов в существенной степени избавлен от этого недостатка. Этот метод основан на понятии сопряженных направлений. Будем рассматривать задачу минимизации квадратичной функции

f(x) = (Ax , x) + (b, x) + c

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

Направления p⁽⁰⁾, p⁽¹⁾, … , p⁽^m^–1) называются взаимно сопряженными относительно матрицы A, если (Ap⁽^k⁾, p⁽^l⁾) = 0 для всех k ¹ l.

В основе метода сопряженных градиентов лежит итерационный процесс:

x^(m+1)= x^(m)+ a^(m)p^(m), m = 0, 1, …; p⁽⁰⁾ = –g⁽⁰⁾ = –f^'(x⁽⁰⁾).

Величина шага a⁽^m⁾ так же, как и в методе наискорейшего спуска, выбирается из условия одномерной минимизации функции j⁽^m⁾(a) = f(x⁽^m⁾+ a⁽^m⁾p⁽^m⁾),

Направления p⁽^m⁾ находят по следующему правилу:

p⁽⁰⁾ = –g⁽⁰⁾ = –f^'(x⁽⁰⁾),

p^(m+1) = –g^(m+1) + b^(m) p^(m), n ³ 1,

b⁽^m⁾ = ,

g⁽^m⁾ = Ax⁽^m⁾ + b,

где

p⁽^m⁾ = p ( x⁽^m⁾) – вектор сопряженных направлений;

g⁽^m⁾= g(x⁽^m⁾) – вектор направлений градиента;

x⁽^m⁾ = (x , x , … , x ) – m-ое приближение.

Алгоритм 2.3 (Алгоритм метода сопряженных градиентов для квадратичной фун кции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c , i = 1, … , n; j = 1, … , n, Выбрать произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T, например, x⁽⁰⁾= (0, 0, … , 0)^T и погрешность вычислений e > 0.

Шаг 2. Вычислить

p⁽⁰⁾ = – g⁽⁰⁾ = –(Ax⁽⁰⁾ + b),

Покоординатно:

p⁽⁰⁾ = (p , p , … , p )^T,

p = – g = – , i = 1, …, n.

Далее вычисления производятся в цикле по m = 0, 1, … до тех пор, пока не будет выполнен критерий окончания вычислений.

Шаги 3 – 6 реализуют вычисление величины шага a⁽^m⁾

Шаг 3. Вычислить

B = (g⁽^m⁾, p⁽^m⁾) = .

Шаг 4. Вычислить

Ap^(m) = (A , A , … , A )^T, где

A = , i = 1, …, n.

Шаг 5. Вычислить

B = (Ap^(m), p^(m)) = .

Шаг 6. Вычислить

a⁽^m⁾ = – .

Шаг 7. Вычислить

x⁽^m⁺¹⁾ = x⁽^m⁾ +a⁽^m⁾p⁽^m⁾, или покоординатно

x^(m+1) = (x , x , … , x )^T,

x = x + a^(m)p , i = 1, …, n.

Шаг 8. Вычислить

g⁽^m⁺¹⁾ = Ax⁽^m ⁺¹⁾ + b, или покоординатно

g^(m+1) = (g , g , … , g ),

g = , i = 1, …, n.

Шаг 9. Для заданной точности вычислений e проверить выполнение критерия окончания вычислений.: ||f '(x⁽^m⁺¹⁾)|| = ||g⁽^m⁺¹⁾)|| < e , Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x^* = x⁽^m⁺¹⁾ = (x , x , … , x )^T, f^* = f(x^*). В противном случае перейти к шагу 10 для продолжения итерационного процесса.

Шаги 10 – 12 реализуют вычисление нового вектора сопряженного градиента p⁽^m⁺¹⁾.

Шаг 10. Вычислить

С = (Ap⁽^m⁾, g⁽^m⁺¹⁾) = .

Шаг 11. Вычислить

b ⁽ ^m ⁾ = .

Шаг 12. Вычислить

p⁽^m⁺¹⁾ = – g⁽^m⁺¹⁾ + b ⁽ ^m ⁾ p⁽^m⁾, или покоординатно

p^(m+1) = (p , p , … , p ),

p = – g + b ^(m) p , i = 1, …, n.

Шаг 13. Перейти к шагу 3 при m = m+1.

Пример 2.5.

Найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.1.

Как было показано ранее, эта функция имеет минимум в точке x^*= (2, 1)^T.

Матрица этой квадратичной функции имеет вид:

2 0

A= 0 4 , b = (– 4, – 4)^T.

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

Шаг 1. Возьмем начальное приближение x⁽⁰⁾ =(x , x )^T = (0, 0)^T, положим e = 0.01.

Шаг 2. Вычисляем

g⁽⁰⁾ = (g , g )^T,

g = = 2×0 + 0×0 – 4 = –4,

g = = 0×0 + 4×0 – 4 = –4,

g⁽⁰⁾ = (–4, –4)^T,

p⁽⁰⁾ = (p , p )^T = (4, 4)^T,

1- ая итерация, m = 0.

Шаг 3.

B = (g⁽⁰⁾, p⁽⁰⁾) = – (g⁽⁰⁾, g⁽⁰⁾) = – = –(16 + 16) = –32.

Шаг 4.

Ap⁽⁰⁾ = (A , A ),

A = = 2×4 + 0×4 = 8,

A = = 0×4 + 4×4 = 16.

Шаг 5.

B = (Ap⁽⁰⁾, p⁽⁰⁾) = = 8×4 + 16×4 = 96.

Шаг 6.

a ⁽⁰⁾ = – = – = .

Шаг 7.

x⁽¹⁾ = x⁽⁰⁾ +a ⁽⁰⁾ p⁽⁰⁾,

x⁽¹⁾ = (x , x ),

x = x + a ⁽⁰⁾ p = 0 + ×4 = ,

x = x + a ⁽⁰⁾ p = 0 + ×4 = .

Шаг 8.

g⁽¹⁾ = Ax⁽¹⁾ + b, или покоординатно

g⁽¹⁾ = (g , g )^T,

g = = 2× + 0× – 4 = – ,

g = = 0× + 4× – 4 = .

Шаг 9. Проверяем выполнение критерия окончания вычислений.:

||f '(x⁽¹⁾)|| = ||g⁽¹⁾)|| = = > e .

Переходим к шагу 10.

Шаг 10.

С = (Ap⁽⁰⁾, g⁽¹⁾) = = 8×(– ) + 16× = .

Шаг 11.

b ⁽⁰⁾ = = = ×.

Шаг 12. Определяем новое направление

p⁽¹⁾ = – g⁽¹⁾ + b ⁽⁰⁾ p⁽⁰⁾, или покоординатно

p⁽¹⁾ = (p , p ),

p = – g + b ⁽⁰⁾p = + ×4 = ,

p = – g + b ⁽⁰⁾p = – + ×4 = – .

Шаг 13. Перейдем к шагу 3 при m = 1. Начало новой итерации.

2- ая итерация, m = 1.

Шаг 3.

B = (g⁽¹⁾, p⁽¹⁾) = = – × + ×( – ) = – .

Шаг 4.

Ap⁽¹⁾ = (A , A ),

A = = 2× + 0×( – ) = ,

A = = 0× + 4×( – ) = – .

Шаг 5.

B = (Ap⁽¹⁾, p⁽¹⁾) = = × – ×( – ) = .

Шаг 6.

a ⁽¹⁾ = – = .

Шаг 7.

x⁽²⁾ = x⁽¹⁾ +a⁽¹⁾ p⁽¹⁾,

x⁽²⁾ = (x , x ),

x = x + a⁽¹⁾p = + × = 2,

x = x + a⁽¹⁾p = + ×( – ) = 1.

Шаг 8.

g⁽²⁾ = Ax⁽²⁾ + b, или покоординатно

g⁽²⁾ = (g , g )^T,

g = = 2×2+ 0×1 – 4 = 0,

g = = 0×2+ 4×1 – 4 = 0.

Шаг 9. Проверяем выполнение критерия окончания вычислений.:

||f '(x⁽²⁾)|| = ||g⁽²⁾)|| = = 0 < e .

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

Таким образом, полученное значение точки минимума x^* равно точному значению x^* = (2, 1)^T и f(x^*) » –6.000.

Решение найдено за два шага.

Метод покоординатного спуска

Пусть нужно найти минимум функции f(x₁, x₂, … ,x_n). Основная идея метода покоординатного спуска состоит в последовательной минимизации функции f(x₁, x₂, … ,x_n) сначала в направлении координатной оси x₁, затем в направлении координатной оси x₂ и т. д. После окончания минимизации в направлении координатной оси x_n цикл повторяется. Метод покоординатного спуска не требует вычисления производных функции f(x₁, x₂, … ,x_n), поэтому целесообразно использовать критерии окончания вычислений в виде (2.21) или (2.22).

Опишем сначала алгоритм метода покоординатного спуска в общем виде.

Алгоритм 2.4 (Алгоритм метода покоординатного спуска).

Шаг 1. Выбрать произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T, например, x⁽⁰⁾ = (0, 0, … , 0)^T и погрешность вычислений e > 0. Вычислить f (x⁽⁰⁾ ).

Шаг 2. Положить j =1.

Шаг 3. Рассмотреть функцию f(x₁, x₂, … ,x_n) как функцию одной переменной x_j, а все остальные переменные зафиксировать. Найти x , решив задачу одномерной минимизации, т.е. найти f(x₁, x₂, … ,x_n).

Шаг 4. Если j < n, то положить j = j + 1 и перейти к шагу 3. В противном случае перейти к шагу 5.

Шаг 5. Найдено очередное приближение x⁽¹⁾ = (x , x , …, x ). Проверить критерий окончания вычислений || x⁽¹⁾ – x⁽⁰⁾|| < e или |f(x⁽¹⁾) – f(x⁽⁰⁾)| < e. Если критерий окончания вычислений выполнен, то положить x^* = x, f^* = f(x^*) и закончить вычисления. В противном случае положить x⁽⁰⁾ = x⁽¹⁾ , f^*(x⁽⁰⁾) = f(x⁽¹⁾) и перейти к шагу 2.

На рис. 2.4 изображена геометрическая иллюстрация циклического покоординатного спуска.

Рис. 2.4

Применим метод покоординатного спуска для квадратичной функции f(x) = (Ax , x) + (b, x) + c с симметричной положительно определенной матрицей A .

Выберем произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T. Рассмотрим функцию f(x₁, x , … , x ) как функцию одной переменной x₁, а все остальные переменные зафиксируем. Найдем значение x₁ = x , при котором достигается f(x₁, x , … , x ).

При этом необходимо, чтобы

= 0.

Это условие можно записать в следующем виде:

a₁₁x₁ + + b₁= 0,

x = – ( + b₁).

Затем рассмотрим функцию f(x , x₂, x … , x ) как функцию одной переменной x₂, а все остальные переменные зафиксируем. Найдем значение x , при котором достигается f(x , x₂, x … , x ). Пусть на очередном j-ом шаге функция f(x₁, x₂, … ,x_n) рассматривается как функция одной переменной x_j, а все остальные переменные зафиксированы. Значение x_j, определяется из условия f(x , x , … , x , x_j, x , …, x ). При этом необходимо, чтобы

= 0.

Это условие можно записать в следующем виде:

+ b_j = 0.

Отсюда

x = – ( + b_j). (2.27)

В результате n шагов будет получено первое приближение x⁽¹⁾ = (x , x , …, x ). Затем итерационный процесс может быть продолжен. Опишем алгоритм этого процесса.

Алгоритм 2.5 (Алгоритм метода покоординатного спуска для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c , i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например, x⁽⁰⁾ = (x , x , … , x )^T и погрешность вычислений e > 0. Вычислить f(x⁽⁰⁾).

Шаг 2. В цикле по m = 0, …

В цикле по j =1, … , n вычислить

x = – ( + b_j).

Если верхний предел суммирования окажется меньше нижнего, то положить S = 0. Положить x⁽¹⁾ = x = (x , x , … , x )^T.

Шаг 3. Проверить выполнение критерия окончания вычислений:

||x⁽¹⁾ – x⁽⁰⁾|| = < e ,

или

|f(x⁽¹⁾) – f(x⁽⁰⁾)| < e.

Если критерий окончания вычислений выполнен, то положить x^* = x⁽¹⁾, f^*_min = f(x^*) и закончить вычисления. В противном случае положить x⁽⁰⁾ = x⁽¹⁾, f(x⁽⁰⁾) = f(x⁽¹⁾) и перейти к шагу 2.

Пример 2.6.

Как и в предыдущих примерах, найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.1.

2 0

A = 0 4 ,

b = (– 4, – 4)^T.

Как было показано ранее, эта функция имеет минимум в точке x^*= (2, 1)^T.

Применим метод покоординатного спуска.

Шаг 1. Возьмем начальное приближение x⁽⁰⁾ =(x , x )^T = (0, 0)^T, положим e = 0.01. Вычислим f (x⁽⁰⁾) = 0.

Шаг 2. Полагаем m = 0.

При j = 1 вычисляем x по формуле (2.27):

x = – ( + + b₁).

Первая сумма равна нулю (верхний предел суммирования меньше нижнего), поэтому

x = – (a₁₂x + b₁) = – (0×0 – 4) = 2;

При j = 2 вычисляем x по формуле (2.27):

x = – ( + + b₂).

Вторая сумма равна нулю (верхний предел суммирования меньше нижнего), поэтому

x = – (a₂₁x + b₂) = – (0×2 – 4) = 1;

Итак, x⁽¹⁾= (2, 1)^T, т.е. найденное приближение совпадает с точным решением. Очевидно, f(x⁽¹⁾) = –6.000.

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

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

Метод Ньютона использует информацию о производных первого и второго порядка. Поэтому он относится к градиентным методам второго порядка.

Метод Ньютона для функции многих переменных является обобщением метода Ньютона для одномерного случая (разд. 1.8)

Пусть дана дважды непрерывно дифференцируемая функция n переменных f(x) = f(x₁, x₂, … ,x_n) и начальная точка x⁽⁰⁾ = (x , x , … , x )^T.

Разложим функцию f(x) в ряд Тейлора в точке x⁽⁰⁾ как функцию многих переменных и ограничимся тремя членами:

f(x)=f(x⁽⁰⁾) + (2.28)

Пусть x⁽^m⁾ приближенное значение точки минимума, полученное на m-ом шаге итерационного процесса. Разложение (2.28) будет иметь место и для точки x⁽^m⁾, а именно

f(x)=f(x⁽^m⁾)+ (2.29)

или в векторной форме

f(x) » f(x^(m)) + (g(x^(m)), (x – x^(m)) + (G(x^(m))(x – x^(m)), (x – x^(m))), (2.30)

где G(x⁽^m⁾) – матрица Гессе (матрица вторых производных) функции f(x) в точке x⁽^m⁾.

Из соотношения (2.29) видно, что в окрестности точки x⁽^m⁾ поведение функции f(x) может быть приближенно описано квадратичной функцией с точностью до величины порядка o(||x – x⁽^m⁾||)²

Необходимое условие минимума – равенство нулю в точке минимума первой производной функции f(x), т. е.

f ^'(x) » g(x^(m))+ G(x^(m))(x – x^(m)) = 0. (2.31)

Умножим (2.31) на G^–1(x⁽^m⁾):

G^–1(x⁽^m⁾)g(x⁽^m⁾)+ (x – x⁽^m⁾) = 0.

Следовательно,

x = x⁽^m⁾ – G^–1(x⁽^m⁾)g(x⁽^m⁾).

Пусть точка минимума x^*»x⁽^m⁺¹⁾. Тогда

x⁽^m⁺¹⁾ = x⁽^m⁾ – G^–1(x⁽^m⁾)g(x⁽^m⁾). (2.32)

Формула (2.32) является расчетной формулой метода Ньютона.

Для квадратичной функции матрица Гессе есть матрица квадратичной формы, равенство (2.31) является точным, и решение (точка минимума) находится за одну итерацию. В общем случае метод Ньютона обеспечивает , как правило, быструю сходимость. Недостатком метода Ньютона является необходимость на каждой итерации вычисления матрицы Гессе и обратной к ней матрицы. Кроме того, если начальная точка выбрана недостаточно близко к точке минимума x^*, то последовательность x⁽⁰⁾, x⁽¹⁾, …, x⁽^m⁾, … может расходиться. Для избежания подобной ситуации используется обобщенный метод Ньютона, со следующей расчетной формулой:

x^(m+1) = x^(m) – a^(m)G^–1(x^(m))g(x^(m)). (2.33)

Формула (2.33) есть расчетная формула метода спуска (см. формулу (2.18)) с направлением в точке x⁽^m⁾, определяемым вектором p⁽^m⁾= G^–1(x⁽^m⁾)g(x⁽^m⁾), и с шагом a⁽^m⁾.

Величина шага a⁽^m⁾ может быть выбрана из условия одномерной минимизации функции j⁽^m⁾(a) = f(x⁽^m⁾ – a⁽^m⁾G^–1(x⁽^m⁾)g(x⁽^m⁾).

Формулу (2.32) также можно рассматривать как формулу спуска с шагом a⁽^m⁾= 1.

Опишем теперь алгоритм метода Ньютона.

Алгоритм 2.6 (Алгоритм метода Ньютона).

Шаг 1. Выбрать произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T, например, x⁽⁰⁾= (0, 0, … , 0)^T и погрешность вычислений e > 0.

В цикле по m =0, …, пока не будет выполнен критерий окончания вычислений,

Шаг 2. Вычислить g(x⁽^m⁾)и G(x⁽^m⁾).

Шаг 3. Вычислить G^–1(x⁽^m⁾).

Шаг 4. Вычислить x⁽^m⁺¹⁾ = x⁽^m⁾ – G^–1(x⁽^m⁾)g(x⁽^m⁾).

Вычисления продолжить до тех пор, пока не будет выполнен критерий окончания вычислений:

||x⁽^m⁺¹⁾ – x⁽^m⁾|| = < e ,

или

|f(x⁽^m⁺¹⁾) – f(x⁽^m⁾)| < e.

Если критерий окончания вычислений выполнен, то положить x^* = x⁽^m⁺¹⁾, f^* = f(x^*) и закончить вычисления.

В случае, когда f(x) – квадратичная функция, матрица Гессе есть матрица квадратичной формы и не зависит от x (G(x⁽^m⁾) = A). Для этого случая получим следующий алгоритм.

Алгоритм 2.7 (Алгоритм метода Ньютона для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c , i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например, x= (0, 0, … , 0)^T и погрешность вычислений e > 0.