Русская Википедия:Градиентные методы
Градие́нтные ме́тоды — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции.
Постановка задачи решения системы уравнений в терминах методов оптимизации
Задача решения системы уравнений:
<math>\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. </math>(1)
с <math>n</math> <math>x_1, x_2, \ldots, x_n</math> эквивалентна задаче минимизации функции
<math>F(x_1, x_2, \ldots, x_n)\equiv\sum_{i=1}^n|f_i(x_1, x_2, ..., x_n)|^2</math> (2)
или какой-либо другой возрастающей функции от абсолютных величин <math>|f_i|</math> невязок (ошибок) <math>f_i = f_i(x_1, x_2, \ldots, x_n)</math>, <math>i=1, 2, \ldots,n</math>. Задача отыскания минимума (или максимума) функции <math>n</math> переменных и сама по себе имеет большое практическое значение.
Для решения этой задачи итерационными методами начинают с произвольных значений <math>x_i^{[0]} (i = 1, 2, ..., n)</math> и строят последовательные приближения:
<math>\vec{x}^{[j+1]}=\vec{x}^{[j]}+\lambda^{[j]} \vec{v}^{[j]}</math>
или покоординатно:
<math>x^{[j+1]}_i = x^{[j]}_i + \lambda^{[j]}v^{[j]}_i ,\quad i=1, 2, \ldots,n,\quad j = 0, 1, 2, \ldots</math> (3)
которые сходятся к некоторому решению <math>\vec{x}^{[k]}</math> при <math>{j\to\infty}</math>.
Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений
<math>v^{[j]}_1: v^{[j]}_2: \ldots :v^{[j]}_n </math>.
Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра <math>\lambda^{[j]}</math>, минимизирующим величину <math>F(x^{[j+1]}_1, x^{[j+1]}_2, \ldots, x^{[j+1]}_n )</math> как функцию от <math>\lambda^{[j]}</math>. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям <math>\lambda^{[j]}</math>. Последний метод применим для отыскания max и min таблично заданной функции <math>F(x_1, x_2, ..., x_n)</math>.
Градиентные методы
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом: <math>-\nabla F</math>:
<math>\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]}) </math>,
где <math>\lambda^{[j]}</math> выбирается:
- постоянной, в этом случае метод может расходиться;
- дробным шагом, то есть длина шага в процессе спуска делится на некое число;
- наискорейшим спуском: <math>\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]})) </math>.
Метод наискорейшего спуска (метод градиента)
Выбирают <math>v^{[j]}_i = -\frac{\partial F}{\partial x_i}</math>, где все производные вычисляются при <math>x_i = x^{[j]}_i</math>, и уменьшают длину шага <math>\lambda^{[j]}</math> по мере приближения к минимуму функции <math>F</math>.
Для аналитических функций <math>F</math> и малых значений <math>f_i</math> тейлоровское разложение <math>F(\lambda^{[j]})</math> позволяет выбрать оптимальную величину шага
<math>\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_kdx_h}\frac{\partial F}{\partial x_k}\frac{\partial F}{\partial x_h}}</math>, (5)
где все производные вычисляются при <math>x_i = x^{[j]}_i</math>. Параболическая интерполяция функции <math>F(\lambda^{[j]})</math> может оказаться более удобной.
Алгоритм
- Задаются начальное приближение и точность расчёта <math>\vec{x}^0\!,\, \epsilon</math>
- Рассчитывают <math>\vec{x}^{[j+1]}=\vec{x}^{[j]}-\lambda^{[j]}\nabla F\left(\vec{x}^{[j]}\right) </math>, где <math>\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F\left(\vec{x}^{[j]}-\lambda^{[j]}\nabla F\left(\vec{x}^{[j]}\right)\right) </math>
- Проверяют условие останова:
- если <math>\left|\vec{x}^{[j+1]}-\vec{x}^{[j]}\right|>\epsilon</math>, то <math>j=j+1</math> и переход к шагу 2;
- иначе <math>\vec{x}=\vec{x}^{[j+1]}</math> и останов.
Метод покоординатного спуска Гаусса — Зейделя
Шаблон:Falseredirect Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений. Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые <math>\lambda \quad n</math> раз за один шаг.
Алгоритм
- Задаются начальное приближение и точность расчёта <math>\vec{x}^0_0, \quad \varepsilon</math>
- Рассчитывают <math>\left\{\begin{array}{lcr}
\vec{x}^{[j]}_1 & = & \vec{x}^{[j]}_0-\lambda^{[j]}_1\frac{\partial F(\vec{x}^{[j]}_0)}{\partial x_1}\vec{e}_1 \\ \ldots & & \\ \vec{x}^{[j]}_n & = & \vec{x}^{[j]}_{n-1}-\lambda^{[j]}_n\frac{\partial F(\vec{x}^{[j]}_{n-1})}{\partial x_n}\vec{e}_n \end{array} \right. </math>, где <math>\lambda^{[j]}_i=\mathrm{argmin}_{\lambda} \,F\left( \vec{x}^{[j]}_{i-1}-\lambda^{[j]}\frac{\partial F(\vec{x}^{[j]}_{i-1})}{\partial x_{i}} \vec{e}_i \right) </math>
- Проверяют условие остановки:
- если <math>|\vec{x}^{[j]}_n-\vec{x}^{[j]}_0|>\varepsilon</math>, то <math>\vec{x}^{[j+1]}_0=\vec{x}^{[j]}_n,\quad j=j+1</math> и переход к шагу 2;
- иначе <math>\vec{x}=\vec{x}^{[j]}_n</math> и останов.
Метод сопряжённых градиентов
Шаблон:Main Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.
Применение метода к квадратичным функциям в <math>\mathbb{R}^n</math> определяет минимум за <math>n</math> шагов.
Алгоритм
- Задаются начальным приближением и погрешностью: <math>\vec{x}_0,\quad \varepsilon, \quad k=0</math>
- Рассчитывают начальное направление: <math>j=0,\quad \vec{S}_k^j=-\nabla f(\vec{x}_k),\quad \vec{x}_k^j=\vec{x}_k</math>
- <math>\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}</math>
- Если <math>||\vec{S}_k^{j+1}||<\varepsilon</math> или <math>||\vec{x}_k^{j+1}-\vec{x}_k^j||<\varepsilon</math>, то <math>\vec{x}=\vec{x}_k^{j+1}</math> и останов.
- Иначе
- если <math>(j+1)<n</math>, то <math>j=j+1</math> и переход к 3;
- иначе <math>\vec{x}_{k+1}=\vec{x}_k^{j+1},\quad k=k+1</math> и переход к 2.
См. также
Литература
Шаблон:Rq Шаблон:Методы оптимизации
