Лабораторная_работа_оп_методам_оптимизации_2

1.

0.1
Основная идея метода
Метод градиентного спуска — это итерационный алгоритм первого порядка
для нахождения локального минимума дифференцируемой функции. Основная идея заключается в движении в направлении, противоположном
градиенту функции.
0.2
Алгоритм
Для минимизации функции f (x) алгоритм состоит из следующих шагов:
1. Выбираем начальное приближение x0
2. Для k = 0, 1, 2, . . . выполняем:
xk+1 = xk − αk ∇f (xk )
где αk > 0 — размер шага на k-й итерации
0.3
Применение к квадратичной функции
Для нашей функции:
f0 (x) =
1 T
x Ax + bT x
2
градиент имеет вид:
∇f0 (x) = Ax + b
Тогда итерационная формула градиентного спуска принимает вид:
xk+1 = xk − αk (Axk + b)
1
Аналитическое решение для трёхмерного случая
1.1
Постановка задачи
Минимизировать функцию:
f0 (x) =
1 T
(x Ax) + b · x
2
где:
x1
x = x2 ,
x3
a11
A = a21
a31
a12
a22
a32
a13
a23 ,
a33
b1
b = b2
b3
Матрица A - симметричная положительно определённая.
1

2.

1.2
Разложение функции в координатной форме
Распишем квадратичную форму:
xT Ax = x1
x2
a11
x3 a21
a31
a12
a22
a32
a13
x1
a23 x2
a33
x3
Умножение матрицы на вектор:
a11 x1 + a12 x2 + a13 x3
Ax = a21 x1 + a22 x2 + a23 x3
a31 x1 + a32 x2 + a33 x3
Домножаем слева на xT :
xT Ax = x1 (a11 x1 +a12 x2 +a13 x3 )+x2 (a21 x1 +a22 x2 +a23 x3 )+x3 (a31 x1 +a32 x2 +a33 x3 )
Раскрываем скобки:
xT Ax = a11 x21 +a12 x1 x2 +a13 x1 x3 +a21 x1 x2 +a22 x22 +a23 x2 x3 +a31 x1 x3 +a32 x2 x3 +a33 x23
Учитывая симметричность матрицы (aij = aji ):
xT Ax = a11 x21 + a22 x22 + a33 x23 + 2a12 x1 x2 + 2a13 x1 x3 + 2a23 x2 x3
Линейная часть:
b · x = b1 x1 + b2 x2 + b3 x3
1.3
Итоговое выражение функции
f0 (x) =
1.4
1
(a11 x21 +a22 x22 +a33 x23 +2a12 x1 x2 +2a13 x1 x3 +2a23 x2 x3 )+b1 x1 +b2 x2 +b3 x3
2
Вычисление градиента
Частные производные:
По x1 :
1
∂f0
= (2a11 x1 + 2a12 x2 + 2a13 x3 ) + b1 = a11 x1 + a12 x2 + a13 x3 + b1
∂x1
2
По x2 :
∂f0
1
= (2a12 x1 + 2a22 x2 + 2a23 x3 ) + b2 = a21 x1 + a22 x2 + a23 x3 + b2
∂x2
2
По x3 :
∂f0
1
= (2a13 x1 + 2a23 x2 + 2a33 x3 ) + b3 = a31 x1 + a32 x2 + a33 x3 + b3
∂x3
2
2

3.

1.5
Градиент в матричной форме
∂f
0
a11 x1 + a12 x2 + a13 x3 + b1
1
∂x
∂f0
a21 x1 + a22 x2 + a23 x3 + b2 = Ax + b
=
∇f0 (x) = ∂x
2
∂f0
a31 x1 + a32 x2 + a33 x3 + b3
∂x3
1.6
Нахождение стационарной точки
Условие минимума:
∇f0 (x) = 0
⇒
Ax + b = 0
Ax = −b
x∗ = −A−1 b
1.7
Матрица Гессе
Вычисляем вторые производные:
∂ 2 f0
= a11 ,
∂x21
∂ 2 f0
= a12 ,
∂x1 ∂x2
∂ 2 f0
= a13
∂x1 ∂x3
∂ 2 f0
= a21 ,
∂x2 ∂x1
∂ 2 f0
= a22 ,
∂x22
∂ 2 f0
= a23
∂x2 ∂x3
∂ 2 f0
= a31 ,
∂x3 ∂x1
∂ 2 f0
= a32 ,
∂x3 ∂x2
∂ 2 f0
= a33
∂x23
Матрица Гессе:
∂2f
0
∂x21
2
∂ f0
H(f0 ) =
∂x2 ∂x1
∂ 2 f0
∂x3 ∂x1
1.8
∂ 2 f0
∂x1 ∂x2
∂ 2 f0
∂x22
∂ 2 f0
∂x3 ∂x2
∂ 2 f0
∂x1 ∂x3
a11
2
∂ f0
a21
=
∂x2 ∂x3
a31
∂ 2 f0
∂x23
a12
a22
a32
a13
a23 = A
a33
Вывод
1. Стационарная точка: x∗ = −A−1 b
2. Матрица Гессе совпадает с матрицей A
3. Так как A положительно определённая, точка x∗ является точкой минимума
4. Градиентный спуск: xk+1 = xk − α(Axk + b)
2
Результаты вычислений
3

4.

Рис. 1: Результаты работы градиентного спуска
4