Метод Гаусса (оптимизация)

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

Метод Гаусса[1] — прямой метод решения задач многомерной оптимизации.

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

Пусть необходимо найти минимум действительнозначной функции f(\vec{x})\to\min_{\vec{x}\in\mathbb{R}^n}, а \vec{x}_0\! — начальное приближение.

Суть метода заключается в том, чтобы на каждой итерации по очереди минимизировать функцию вдоль каждой из координат, то есть:

\vec{x}^{k+1}_0=\vec{x}_k\!
\left\{\begin{array}{rl}
\vec{x}^{k+1}_1=\vec{x}^{k+1}_0+\lambda_1 \vec{e}_1, & \lambda_1=\arg \min_{\lambda} f(\vec{x}^{k+1}_0+\lambda_1 \vec{e}_1)\\
\ldots & \\
\vec{x}^{k+1}_n=\vec{x}^{k+1}_{n-1}+\lambda_n \vec{e}_n, & \lambda_n=\arg \min_{\lambda} f(\vec{x}^{k+1}_{n-1}+\lambda_n \vec{e}_n)
\end{array}\right.,

где \vec{e}_1,\ldots,\vec{e}_n\!ортонормированный базис в рассматриваемом пространстве.

Таким образом метод как бы «поднимется» по координатам, используя на шагах одной итерации для вычисления следующей координаты точки приближения все предыдущие значения координат, вычисленные на той же итерации, в этом и состоит схожесть с одноимённым методом решения СЛАУ.

При завершении итерации, точка, полученная на последнем шаге этой итерации, берётся в качестве следующего приближения:

\vec{x}_{k+1}=\vec{x}^{k+1}_n.

Процедура продолжается до тех пор, пока не будет достигнута заданная точность \varepsilon\!, то есть пока:

||\vec{x}_{k+1}-\vec{x}_k||>\varepsilon\!.

Улучшением данного метода является метод покоординатного спуска (метод Гаусса-Зейделя).

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

  1. Гаусс, Карл Фридрих (17771855) — немецкий математик, физик и астроном

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

  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  • Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

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