Метод покоординатного спуска

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 26: Строка 26:
# <tex>||f(x^{[k+1]})-f(x^{[k]})||\leq\eps</tex>
# <tex>||f(x^{[k+1]})-f(x^{[k]})||\leq\eps</tex>
-
Здечь <tex>x^{[k]} \in \mathbb{R}^n</tex> --- значение, полученное после <tex>k</tex>-го шага оптимизации.
+
Здесь <tex>x^{[k]} \in \mathbb{R}^n</tex> - значение, полученное после <tex>k</tex>-го шага оптимизации.
 +
<tex>\eps</tex> - наперед заданное положительное число.
===Сходимость метода===
===Сходимость метода===

Версия 22:08, 18 ноября 2008

Содержание

Постановка задачи

Рассмотрим задачу поиска минимума функции f(x): \mathbb{R}^n \to \mathbb{R} , записываемую в виде:

(1)
f(x) \to \min_{x \in \mathbb{R}^n}

Метод покоординатного спуска (Метод Гаусса-Зейделя)

Алгоритм

Рис.1 Иллюстрация метода
Рис.1 Иллюстрация метода

Вход: функция f: \mathbb{R}^n \to \mathbb{R}

Выход: найденная точка оптимума x

  1. Инициализация некоторым значением x_0 \in \mathbb{R}^n
  2. повторять:
    • для i=1\dots n
      1. фиксируем значения всех переменных кроме x_i, получая одномерную функцию f(x_i)
      2. проводим одномерную оптимизацию по переменной x_i, любым методом одномерной оптимизации
      3. если выполен критерий останова, то возвращаем текущее значение x=(x_1,\dots,x_n)

Критерий останова

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

  1. ||x^{[k+1]}-x^{[k]}||\leq\eps
  2. ||f(x^{[k+1]})-f(x^{[k]})||\leq\eps

Здесь x^{[k]} \in \mathbb{R}^n - значение, полученное после k-го шага оптимизации. \eps - наперед заданное положительное число.

Сходимость метода

Рис.2
Рис.2

Легко убедится, что существуют функции, когда метод координатного спуска не приводит даже в локальный оптимум.

Пусть линии уровня образуют истинный овраг (рис.2), когда спуск по любой координате приводит на <<дно>> оврага, а любое движение по следующей координате (пунктирная линия) ведет на подъем. Никакой дальнейший спуск по координатам в данном случае невозможен, хотя минимум еще не достигнут.

Теорема о сходимости метода покоординатного спуска.

Для простоты рассмотрим функцию двух переменных f(x,y). Выберем некоторое началное приближение (x_0,y_0) и проведем линию уровня через эту точку. Пусть в области G, ограниченной этой линией уровня, выполняются неравенства, означающий положительную определенность квадратичной формы:

f_{xx}''\geq a>0,\; f_{yy}''\geq b>0,\; |f_{xy}''|\leq c,\; ab>c^2.

Тогда спуск по координатам сходится к минимуму из данного начального приближения, причем линейно.

Числовые примеры

Рекомендации программисту

Заключение

Ссылки

Список литературы

  • А.А.Самарский, А.В.Гулин.  Численные методы. Москва «Наука», 1989.
  • Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.  Численные методы. Лаборатория Базовых Знаний, 2003.
  • Н.Н.Калиткин.  Численные методы. Москва «Наука», 1978.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D0%BA%D0%BE%D0%BE%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0»
Личные инструменты