Градие́нтные ме́тоды — численные методы итерационного приближения к экстремумам функции вдоль её градиента .
Задача решения системы уравнений :
{
f
1
(
x
1
,
x
2
,
…
,
x
n
)
=
0
…
f
n
(
x
1
,
x
2
,
…
,
x
n
)
=
0
{\displaystyle \left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.}
(1)
с
n
{\displaystyle n}
x
1
,
x
2
,
…
,
x
n
{\displaystyle x_{1},x_{2},\ldots ,x_{n}}
эквивалентна задаче минимизации функции
F
(
x
1
,
x
2
,
…
,
x
n
)
≡
∑
i
=
1
n
|
f
i
(
x
1
,
x
2
,
.
.
.
,
x
n
)
|
2
{\displaystyle F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}}
(2)
или какой-либо другой возрастающей функции от абсолютных величин
|
f
i
|
{\displaystyle |f_{i}|}
невязок (ошибок)
f
i
=
f
i
(
x
1
,
x
2
,
…
,
x
n
)
{\displaystyle f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})}
,
i
=
1
,
2
,
…
,
n
{\displaystyle i=1,2,\ldots ,n}
. Задача отыскания минимума (или максимума) функции
n
{\displaystyle n}
переменных и сама по себе имеет большое практическое значение.
Для решения этой задачи итерационными методами начинают с произвольных значений
x
i
[
0
]
(
i
=
1
,
2
,
.
.
.
,
n
)
{\displaystyle x_{i}^{[0]}(i=1,2,...,n)}
и строят последовательные приближения:
x
→
[
j
+
1
]
=
x
→
[
j
]
+
λ
[
j
]
v
→
[
j
]
{\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}
или покоординатно:
x
i
[
j
+
1
]
=
x
i
[
j
]
+
λ
[
j
]
v
i
[
j
]
,
i
=
1
,
2
,
…
,
n
,
j
=
0
,
1
,
2
,
…
{\displaystyle x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2,\ldots ,n,\quad j=0,1,2,\ldots }
(3)
которые сходятся к некоторому решению
x
→
[
k
]
{\displaystyle {\vec {x}}^{[k]}}
при
j
→
∞
{\displaystyle {j\to \infty }}
.
Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений
v
1
[
j
]
:
v
2
[
j
]
:
…
:
v
n
[
j
]
{\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}}
.
Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра
λ
[
j
]
{\displaystyle \lambda ^{[j]}}
, минимизирующим величину
F
(
x
1
[
j
+
1
]
,
x
2
[
j
+
1
]
,
…
,
x
n
[
j
+
1
]
)
{\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})}
как функцию от
λ
[
j
]
{\displaystyle \lambda ^{[j]}}
. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям
λ
[
j
]
{\displaystyle \lambda ^{[j]}}
. Последний метод применим для отыскания max и min таблично заданной функции
F
(
x
1
,
x
2
,
.
.
.
,
x
n
)
{\displaystyle F(x_{1},x_{2},...,x_{n})}
.
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом:
−
∇
F
{\displaystyle -\nabla F}
:
x
→
[
j
+
1
]
=
x
→
[
j
]
−
λ
[
j
]
∇
F
(
x
→
[
j
]
)
{\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}
,
где
λ
[
j
]
{\displaystyle \lambda ^{[j]}}
выбирается:
постоянной, в этом случае метод может расходиться;
дробным шагом, то есть длина шага в процессе спуска делится на некое число;
наискорейшим спуском:
λ
[
j
]
=
a
r
g
m
i
n
λ
F
(
x
→
[
j
]
−
λ
∇
F
(
x
→
[
j
]
)
)
{\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda \nabla F({\vec {x}}^{[j]}))}
.
Основная статья:
метод градиента
Выбирают
v
i
[
j
]
=
−
∂
F
∂
x
i
{\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}}
, где все производные вычисляются при
x
i
=
x
i
[
j
]
{\displaystyle x_{i}=x_{i}^{[j]}}
, и уменьшают длину шага
λ
[
j
]
{\displaystyle \lambda ^{[j]}}
по мере приближения к минимуму функции
F
{\displaystyle F}
.
Для аналитических функций
F
{\displaystyle F}
и малых значений
f
i
{\displaystyle f_{i}}
тейлоровское разложение
F
(
λ
[
j
]
)
{\displaystyle F(\lambda ^{[j]})}
позволяет выбрать оптимальную величину шага
λ
[
j
]
=
∑
k
=
1
n
(
∂
F
∂
x
k
)
2
∑
k
=
1
n
∑
h
=
1
n
∂
2
F
∂
x
k
d
x
h
∂
F
∂
x
k
∂
F
∂
x
h
{\displaystyle \lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k}}})^{2}}{\sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h}}}{\frac {\partial F}{\partial x_{k}}}{\frac {\partial F}{\partial x_{h}}}}}}
, (5)
где все производные вычисляются при
x
i
=
x
i
[
j
]
{\displaystyle x_{i}=x_{i}^{[j]}}
. Параболическая интерполяция функции
F
(
λ
[
j
]
)
{\displaystyle F(\lambda ^{[j]})}
может оказаться более удобной.
Задаются начальное приближение и точность расчёта
x
→
0
,
ϵ
{\displaystyle {\vec {x}}^{0}\!,\,\epsilon }
Рассчитывают
x
→
[
j
+
1
]
=
x
→
[
j
]
−
λ
[
j
]
∇
F
(
x
→
[
j
]
)
{\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)}
, где
λ
[
j
]
=
a
r
g
m
i
n
λ
F
(
x
→
[
j
]
−
λ
∇
F
(
x
→
[
j
]
)
)
{\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\right)}
Проверяют условие останова:
если
|
x
→
[
j
+
1
]
−
x
→
[
j
]
|
>
ϵ
{\displaystyle \left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon }
, то
j
=
j
+
1
{\displaystyle j=j+1}
и переход к шагу 2;
иначе
x
→
=
x
→
[
j
+
1
]
{\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}}
и останов.
Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений.
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые
λ
n
{\displaystyle \lambda \quad n}
раз за один шаг.
Задаются начальное приближение и точность расчёта
x
→
0
0
,
ε
{\displaystyle {\vec {x}}_{0}^{0},\quad \varepsilon }
Рассчитывают
{
x
→
1
[
j
]
=
x
→
0
[
j
]
−
λ
1
[
j
]
∂
F
(
x
→
0
[
j
]
)
∂
x
1
e
→
1
…
x
→
n
[
j
]
=
x
→
n
−
1
[
j
]
−
λ
n
[
j
]
∂
F
(
x
→
n
−
1
[
j
]
)
∂
x
n
e
→
n
{\displaystyle \left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]}-\lambda _{1}^{[j]}{\frac {\partial F({\vec {x}}_{0}^{[j]})}{\partial x_{1}}}{\vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1}^{[j]}-\lambda _{n}^{[j]}{\frac {\partial F({\vec {x}}_{n-1}^{[j]})}{\partial x_{n}}}{\vec {e}}_{n}\end{array}}\right.}
, где
λ
i
[
j
]
=
a
r
g
m
i
n
λ
F
(
x
→
i
−
1
[
j
]
−
λ
[
j
]
∂
F
(
x
→
i
−
1
[
j
]
)
∂
x
i
e
→
i
)
{\displaystyle \lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}_{i-1}^{[j]}-\lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e}}_{i}\right)}
Проверяют условие остановки:
если
|
x
→
n
[
j
]
−
x
→
0
[
j
]
|
>
ε
{\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon }
, то
x
→
0
[
j
+
1
]
=
x
→
n
[
j
]
,
j
=
j
+
1
{\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1}
и переход к шагу 2;
иначе
x
→
=
x
→
n
[
j
]
{\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}}
и останов.
Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений .
Применение метода к квадратичным функциям в
R
n
{\displaystyle \mathbb {R} ^{n}}
определяет минимум за
n
{\displaystyle n}
шагов.
Задаются начальным приближением и погрешностью:
x
→
0
,
ε
,
k
=
0
{\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0}
Рассчитывают начальное направление:
j
=
0
,
S
→
k
j
=
−
∇
f
(
x
→
k
)
,
x
→
k
j
=
x
→
k
{\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}}
x
→
k
j
+
1
=
x
→
k
j
+
λ
S
→
k
j
,
λ
=
arg
min
λ
f
(
x
→
k
j
+
λ
S
→
k
j
)
,
S
→
k
j
+
1
=
−
∇
f
(
x
→
k
j
+
1
)
+
ω
S
→
k
j
,
ω
=
|
|
∇
f
(
x
→
k
j
+
1
)
|
|
2
|
|
∇
f
(
x
→
k
j
)
|
|
2
{\displaystyle {\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j},\quad \lambda =\arg \min _{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j}),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega {\vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})||^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}}
Если
|
|
S
→
k
j
+
1
|
|
<
ε
{\displaystyle ||{\vec {S}}_{k}^{j+1}||<\varepsilon }
или
|
|
x
→
k
j
+
1
−
x
→
k
j
|
|
<
ε
{\displaystyle ||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon }
, то
x
→
=
x
→
k
j
+
1
{\displaystyle {\vec {x}}={\vec {x}}_{k}^{j+1}}
и останов.
Иначе
если
(
j
+
1
)
<
n
{\displaystyle (j+1)<n}
, то
j
=
j
+
1
{\displaystyle j=j+1}
и переход к 3;
иначе
x
→
k
+
1
=
x
→
k
j
+
1
,
k
=
k
+
1
{\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1}
и переход к 2.
Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М. : Высш. шк., 1986.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М. : Энергоатомиздат, 1972.
Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М. : МИФИ, 1980.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575-576.