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

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

Описание

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

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

${\vec {x}}_{0}^{k+1}={\vec {x}}_{k}\!$

$\left\{{\begin{array}{rl}{\vec {x}}_{1}^{k+1}={\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1},&\lambda _{1}=\arg \min _{\lambda }f({\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1})\\\ldots &\\{\vec {x}}_{n}^{k+1}={\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n},&\lambda _{n}=\arg \min _{\lambda }f({\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n})\end{array}}\right.$,

где ${\vec {e}}_{1},\ldots ,{\vec {e}}_{n}\!$ — ортонормированный базис в рассматриваемом пространстве.

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

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

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

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

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

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

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.

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

См. также

• Методы оптимизации
  • Метод Гаусса—Зейделя
• Линейная алгебра
  • Метод Гаусса
  • Метод Гаусса—Зейделя