Градиентные методы

Градие́нтные ме́тоды — численные методы итерационного приближения к экстремумам функции вдоль её градиента.

Постановка задачи решения системы уравнений в терминах методов оптимизации

Задача решения системы уравнений:

${\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)

с ${\displaystyle n}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ эквивалентна задаче минимизации функции

${\displaystyle F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}}$ (2)

или какой-либо другой возрастающей функции от абсолютных величин ${\displaystyle |f_{i}|}$ невязок (ошибок) ${\displaystyle f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})}$, ${\displaystyle i=1,2,\ldots ,n}$. Задача отыскания минимума (или максимума) функции ${\displaystyle n}$ переменных и сама по себе имеет большое практическое значение.

Для решения этой задачи итерационными методами начинают с произвольных значений ${\displaystyle x_{i}^{[0]}(i=1,2,...,n)}$ и строят последовательные приближения:

${\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}$

или покоординатно:

${\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)

которые сходятся к некоторому решению ${\displaystyle {\vec {x}}^{[k]}}$ при ${\displaystyle {j\to \infty }}$.

Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений

${\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}}$.

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра ${\displaystyle \lambda ^{[j]}}$, минимизирующим величину ${\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})}$ как функцию от ${\displaystyle \lambda ^{[j]}}$. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям ${\displaystyle \lambda ^{[j]}}$. Последний метод применим для отыскания max и min таблично заданной функции ${\displaystyle F(x_{1},x_{2},...,x_{n})}$.

Градиентные методы

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом: ${\displaystyle -\nabla F}$:

${\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}$,

где ${\displaystyle \lambda ^{[j]}}$ выбирается:

• постоянной, в этом случае метод может расходиться;
• дробным шагом, то есть длина шага в процессе спуска делится на некое число;
• наискорейшим спуском: ${\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda \nabla F({\vec {x}}^{[j]}))}$.

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

Основная статья: метод градиента

Выбирают ${\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}}$, где все производные вычисляются при ${\displaystyle x_{i}=x_{i}^{[j]}}$, и уменьшают длину шага ${\displaystyle \lambda ^{[j]}}$ по мере приближения к минимуму функции ${\displaystyle F}$.

Для аналитических функций ${\displaystyle F}$ и малых значений ${\displaystyle f_{i}}$ тейлоровское разложение ${\displaystyle F(\lambda ^{[j]})}$ позволяет выбрать оптимальную величину шага

${\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)

где все производные вычисляются при ${\displaystyle x_{i}=x_{i}^{[j]}}$. Параболическая интерполяция функции ${\displaystyle F(\lambda ^{[j]})}$ может оказаться более удобной.

Алгоритм

1. Задаются начальное приближение и точность расчёта ${\displaystyle {\vec {x}}^{0}\!,\,\epsilon }$
2. Рассчитывают ${\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)}$, где ${\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\right)}$
3. Проверяют условие останова:
   • если ${\displaystyle \left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon }$, то ${\displaystyle j=j+1}$ и переход к шагу 2;
   • иначе ${\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}}$ и останов.

Метод покоординатного спуска Гаусса — Зейделя

Запрос «Покоординатный спуск» перенаправляется сюда. На эту тему нужно создать отдельную статью.

Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений. Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые ${\displaystyle \lambda \quad n}$ раз за один шаг.

Алгоритм

1. Задаются начальное приближение и точность расчёта ${\displaystyle {\vec {x}}_{0}^{0},\quad \varepsilon }$
2. Рассчитывают ${\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.}$, где ${\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)}$
3. Проверяют условие остановки:
   • если ${\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon }$, то ${\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1}$ и переход к шагу 2;
   • иначе ${\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}}$ и останов.

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

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

Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.

Применение метода к квадратичным функциям в ${\displaystyle \mathbb {R} ^{n}}$ определяет минимум за ${\displaystyle n}$ шагов.

Алгоритм

1. Задаются начальным приближением и погрешностью: ${\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0}$
2. Рассчитывают начальное направление: ${\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}}$
3. ${\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}}}}$
   • Если ${\displaystyle ||{\vec {S}}_{k}^{j+1}||<\varepsilon }$ или ${\displaystyle ||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon }$, то ${\displaystyle {\vec {x}}={\vec {x}}_{k}^{j+1}}$ и останов.
   • Иначе
     • если ${\displaystyle (j+1)<n}$, то ${\displaystyle j=j+1}$ и переход к 3;
     • иначе ${\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1}$ и переход к 2.

См. также

• Интерполяционные формулы
• Математическое программирование
  • Метод градиента
  • Метод сопряжённых градиентов
  • Метод коллинеарных градиентов
  • Прямые методы
• Формула Тейлора
• Численные методы
  • Численное решение уравнений
  • Метод Нелдера — Мида

Литература

• Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
• Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.