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