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

Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции.

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

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

$\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$$n$  $x_1,x_2,\dots <!--\; \dots \; -->,x_n$$x_{1},x_{2},\ldots ,x_{n}$  эквивалентна задаче минимизации функции

$F(x_1,x_2,\dots <!--\; \dots \; -->,x_n)\equiv <!--\; \equiv \; -->\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}|f_i(x_1,x_2,...,x_n){|}^2$$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|$$|f_{i}|$  невязок (ошибок) $f_i=f_i(x_1,x_2,\dots <!--\; \dots \; -->,x_n)$$f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})$ , $i=1,2,\dots <!--\; \dots \; -->,n$$i=1,2,\ldots ,n$ . Задача отыскания минимума (или максимума) функции $n$$n$  переменных и сама по себе имеет большое практическое значение.

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

${\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}={\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}+{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}{\stackrel{\to <!--\; \to \; -->}{v}}^{[j]}$${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}$ 

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

$x_i^{[j+1]}=x_i^{[j]}+{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}{v}_i^{[j]},i=1,2,\dots <!--\; \dots \; -->,n,j=0,1,2,\dots <!--\; \dots \; -->$$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)

которые сходятся к некоторому решению ${\stackrel{\to <!--\; \to \; -->}{x}}^{[k]}$${\vec {x}}^{[k]}$  при $j\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$${j\to \infty }$ .

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

$v_1^{[j]}:v_2^{[j]}:\dots <!--\; \dots \; -->:v_n^{[j]}$$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

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

Градиентные методыПравить

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

${\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}={\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}\mathrm{\nabla <!--\; \nabla \; -->}F({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]})$${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})$ ,

где ${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}$$\lambda ^{[j]}$  выбирается:

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

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

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

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

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

${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}=\frac{\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}(\frac{\mathrm{\partial <!--\; \partial \; -->}F}{\mathrm{\partial <!--\; \partial \; -->}{x}_k}{)}^2}{\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\underset{h=1}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{{\mathrm{\partial <!--\; \partial \; -->}}^{2}F}{\mathrm{\partial <!--\; \partial \; -->}{x}_{k}d{x}_h}\frac{\mathrm{\partial <!--\; \partial \; -->}F}{\mathrm{\partial <!--\; \partial \; -->}{x}_k}\frac{\mathrm{\partial <!--\; \partial \; -->}F}{\mathrm{\partial <!--\; \partial \; -->}{x}_h}}$$\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]}$$x_{i}=x_{i}^{[j]}$ . Параболическая интерполяция функции $F({\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]})$$F(\lambda ^{[j]})$  может оказаться более удобной.

АлгоритмПравить

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

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

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

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

АлгоритмПравить

1. Задаются начальное приближение и точность расчёта ${\stackrel{\to <!--\; \to \; -->}{x}}_0^0,\mathrm{\epsilon <!--\; \epsilon \; -->}$${\vec {x}}_{0}^{0},\quad \varepsilon$ 
2. Рассчитывают $\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.$ , где ${\mathrm{\lambda <!--\; \lambda \; -->}}_i^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}_{i-<!--\; -\; -->1}^{[j]}-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}\frac{\mathrm{\partial <!--\; \partial \; -->}F({\stackrel{\to <!--\; \to \; -->}{x}}_{i-<!--\; -\; -->1}^{[j]})}{\mathrm{\partial <!--\; \partial \; -->}{x}_i}{\stackrel{\to <!--\; \to \; -->}{e}}_i\right)$$\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. Проверяют условие остановки:
   • если $|{\stackrel{\to <!--\; \to \; -->}{x}}_n^{[j]}-<!--\; -\; -->{\stackrel{\to <!--\; \to \; -->}{x}}_0^{[j]}|>\mathrm{\epsilon <!--\; \epsilon \; -->}$$|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ , то ${\stackrel{\to <!--\; \to \; -->}{x}}_0^{[j+1]}={\stackrel{\to <!--\; \to \; -->}{x}}_n^{[j]},j=j+1$${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$  и переход к шагу 2;
   • иначе $\stackrel{\to <!--\; \to \; -->}{x}={\stackrel{\to <!--\; \to \; -->}{x}}_n^{[j]}$${\vec {x}}={\vec {x}}_{n}^{[j]}$  и останов.

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

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

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

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

АлгоритмПравить

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

См. такжеПравить

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

ЛитератураПравить

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