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

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

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

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

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

$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}(x_{1},x_{2},\ldots ,x_{n})$ , $i=1,2,\ldots ,n$ . Задача отыскания минимума (или максимума) функции $n$ переменных и сама по себе имеет большое практическое значение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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]}$ . Параболическая интерполяция функции $F(\lambda ^{[j]})$ может оказаться более удобной.

Алгоритм

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

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

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

Алгоритм

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

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

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

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

Алгоритм

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

См. также

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Методы оптимизации
Одномерные	Метод золотого сечения Дихотомия Метод парабол Перебор по сетке Метод равномерного блочного поиска Метод Фибоначчи Троичный поиск Метод Пиявского Метод Стронгина
Нулевого порядка	Метод Гаусса Метод Нелдера — Мида Метод Хука — Дживса Метод Розенброка Метод Пауэлла
Первого порядка	Градиентный спуск Метод Зойтендейка Покоординатный спуск Метод сопряжённых градиентов Квазиньютоновские методы Алгоритм Левенберга — Марквардта
Второго порядка	Метод Ньютона Метод Ньютона — Рафсона Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS)
Стохастические	Метод Монте-Карло Имитация отжига Эволюционные алгоритмы Дифференциальная эволюция Муравьиный алгоритм Метод роя частиц Алгоритм пчелиной колонии Метод случайных блужданий
Методы линейного программирования	Симплекс-метод Алгоритм Гомори Метод эллипсоидов Метод потенциалов
Методы нелинейного программирования	Последовательное квадратичное программирование