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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

\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^{[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.

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

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

Алгоритм[править | править исходный текст]

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

Метод покоординатного спуска (Гаусса—Зейделя)[править | править исходный текст]

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

Алгоритм[править | править исходный текст]

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

Метод сопряжённых градиентов[править | править исходный текст]

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

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

Алгоритм[править | править исходный текст]

  1. Задаются начальным приближением и погрешностью: \vec{x}_0,\quad \varepsilon, \quad k=0
  2. Рассчитывают начальное направление: j=0,\quad \vec{S}_k^j=-\nabla f(\vec{x}_k),\quad \vec{x}_k^j=\vec{x}_k
  3. \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, то \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.

Литература[править | править исходный текст]

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

Ссылки[править | править исходный текст]

См. также[править | править исходный текст]