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

У этого термина существуют и другие значения, см. Метод Гаусса.

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

Содержание

1 Описание
2 Примечания
3 Литература
4 См. также

Описание

Пусть необходимо найти минимум действительнозначной функции , а — начальное приближение.

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

$\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.$ ,

где — ортонормированный базис в рассматриваемом пространстве.

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

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

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

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

Примечания

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

Литература

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

См. также

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

Krasorion.ru

Упаковочные материалы