Методичка по курсовым и лабораторным работам, страница 5

= a_ik.

Это означает, что для квадратичной функции (2.14) матрица Гессе не зависит от x и равна A.

Пример 2.1.

Дана квадратичная функция

f(x) = 2x – 2x₁x₂ + 3x₁x₃ +x – 2x₂x₃ + 4x + x₁ – x₂ + 3x₃ +5.

Запишем матрицу A, вектор b и коэффициент c:

4 -2 3 1

A = -2 2 -2 , b = -1 , c = 5.

3 -2 8 3

Найдем первые производные f(x):

= 4x₁–2x₂ +3x₃+1, = –2x₁+2x₂ – 2x₃ – 1, = 3x₁–2x₂ +8x₃ + 3.

Найдем вторые производные f(x):

= 4, = = –2, = = 3, = 2, = = –2, = 8.

Легко убедиться, что матрица Гессе равна A.

Пример 2.2.

f(x) = sinx₁ + е + x₁x₂.

Найдем первые производные f(x):

= cosx₁ +x₂, = е + x₁.

Найдем вторые производные f(x):

= – sinx₁, = = 1, = е .

Матрица Гессе равна

– sinx₁ 1

1 е .

2.4. Методы спуска

Методы спуска – группа методов, широко применяющихся для решения задачи минимизации функции многих переменных f(x) = f(x₁, x₂, … x_n). Основная идея методов спуска состоит в построении минимизирующей последовательности {x^(m)}, m = 0, 1, 2, … по алгоритму:

x^(m+1) = x^(m) + a^(m)p^(m), (2.18)

где x^(m) = (x , x , … , x ) – m-ое приближение к точке минимума, p^(m) – ненулевой вектор, называемый направлением спуска, a^(m) – положительное число, называемое шагом спуска. Различие конкретных методов спуска состоит в способе выбора p^(m), a^(m).

Опишем общую схему методов спуска. Пусть x^(m) = (x , x , … , x ) –приближение к точке минимума, полученное в результате m-ой итерации.

1. В точке x^(m) находят направление спуска p^(m) из условия, чтобы при всех достаточно малых a выполнялось неравенство

f (x^(m) + ap^(m)) < f(x^(m)), (2.19)

т.е. значение функции уменьшалось.

2. Вычисляют шаг спуска a^(m), так, чтобы выполнялось неравенство

f (x^(m) + a^(m)p^(m)) < f(x^(m)),

3. За очередное приближение к точке минимума берут

x^(m+1) = x^(m) + a^(m)p^(m). (2.20)

4. Проверяют выполнение критерия окончания итераций. Если критерий выполняется, то итерации прекращают и полагают x^* » x^(m+1). В противном случае итерации продолжаются.

На практике часто используют следующие критерии окончания итераций:

||x^(m+1) – x^(m)|| < e, (2.21)

|f(x^(m+1)) – f(x^(m))| < e, (2.22)

||f '(x^(m))|| < e, (2.23)

где e – заданное положительное число (допустимая погрешность).

Последовательность точек x⁽⁰⁾, x⁽¹⁾, …, x^(m), …называют траекторией спуска.

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

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

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

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

f(x^(m+1)) > f(x^(m)),

то шаг дробится, например, пополам, т.е. полагается a^{(m +1)} = 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

Из табл. 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.

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

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

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

На рис. 2.3 изображена геометрическая иллюстрация этого метода. Из начальной точки x⁽⁰⁾ перпендикулярно линии уровня f (x) = f (x⁽⁰⁾) в направлении p⁽⁰⁾ = –g⁽⁰⁾ спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча x⁽⁰⁾ – ag⁽⁰⁾ значение функции 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)