Градие́нтные ме́тоды — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции.
Задача решения системы уравнений :
{ 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 ] − λ [ j ] ∇ F ( x → [ j ] ) ) {\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\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 ] − λ [ j ] ∇ F ( x → [ j ] ) ) {\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]}\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.