Градиентные методы | это... Что такое Градиентные методы? (original) (raw)

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

Содержание

1 Постановка задачи решения системы уравнений в терминах методов оптимизации
2 Градиентные методы
3 Литература
4 Ссылки
5 См. также

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

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

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

с $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$ . Задача отыскания минимума (или максимума) функции переменных и сама по себе имеет большое практическое значение.

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

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

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

$x^{[j+1]}_i = x^{[j]}_i + \lambda^{[j]}v^{[j]}_i ,\quad i=1, 2, \ldots,n,\quad j = 0, 1, 2, \ldots$ (3)

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

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

$v^{[j]}_1: v^{[j]}_2: \ldots :v^{[j]}_n$ .

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра $\lambda^{[j]}$ , минимизирующим величину $F(x^{[j+1]}_1, x^{[j+1]}_2, \ldots, x^{[j+1]}_n )$ как функцию от $\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^{[j]}_i = -\frac{\partial F}{\partial x_i}$ , где все производные вычисляются при $x_i = x^{[j]}_i$ , и уменьшают длину шага $\lambda^{[j]}$ по мере приближения к минимуму функции .

Для аналитических функций и малых значений тейлоровское разложение $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_kdx_h}\frac{\partial F}{\partial x_k}\frac{\partial F}{\partial x_h}}$ (5)

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

Алгоритм

Задаются начальное приближение и точность расчёта $\vec{x}^0, \quad \epsilon$
Рассчитывают $\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]})$ , где $\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]}))$
Проверяют условие останова:

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

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

Алгоритм

Задаются начальное приближение и точность расчёта $\vec{x}^0_0, \quad \epsilon$
Рассчитывают $\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.$ , где $\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-1}} \vec{e}_i \right)$
Проверяют условие остановки:

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

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

Применение метода к квадратичным функциям в $\mathbb{R}^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}$

Литература

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

Ссылки

См. также

Численные методы
- Численное решение уравнений
- Метод Гаусса-Зейделя решения СЛАУ

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