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

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

Описание

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

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

${\overrightarrow{x}}_0^{k+1}={\overrightarrow{x}}_k$

$\{\begin{array}{cc}{\overrightarrow{x}}_1^{k+1}={\overrightarrow{x}}_0^{k+1}+{\lambda }_1{\overrightarrow{e}}_1,& {\lambda }_1=\arg \underset{\lambda }{\min }f({\overrightarrow{x}}_0^{k+1}+{\lambda }_1{\overrightarrow{e}}_1)\\ \dots & \\ {\overrightarrow{x}}_n^{k+1}={\overrightarrow{x}}_{n-1}^{k+1}+{\lambda }_n{\overrightarrow{e}}_n,& {\lambda }_n=\arg \underset{\lambda }{\min }f({\overrightarrow{x}}_{n-1}^{k+1}+{\lambda }_n{\overrightarrow{e}}_n)\end{array}$,

где ${\overrightarrow{e}}_1,\dots ,{\overrightarrow{e}}_n$ — ортонормированный базис в рассматриваемом пространстве.

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

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

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

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

$||{\overrightarrow{x}}_{k+1}-{\overrightarrow{x}}_k||<\epsilon$.

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

Литература

• Шаблон:Книга
• Шаблон:Книга

См. также

• Методы оптимизации
  • Метод покоординатного спуска Гаусса — Зейделя
  • Алгоритм Гаусса — Ньютона
• Линейная алгебра
  • Метод Гаусса
  • Метод Гаусса — Зейделя решения системы линейных уравнений