Участник:Anton/Песочница

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
== Введение ==
+
== Постановка задачи ==
-
== Изложение метода ==
+
Рассмотрим задачу поиска минимума функции <tex>f(x): \mathbb{R}^n \to \mathbb{R} </tex>, записываемую в виде:
 +
{{eqno|1}}
 +
::<tex>f(x) \to \min_{x \in \mathbb{R}^n}</tex>
 +
 
 +
== Метод покоординатного спуска (Метод Гаусса-Зейделя) ==
 +
 
 +
===Алгоритм===
 +
 
 +
'''Вход:''' функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex>
 +
 
 +
'''Выход:''' найденная точка оптимума <tex>x</tex>
 +
 
 +
# Инициализация некоторым значением <tex>x_0 \in \mathbb{R}^n</tex>
 +
# повторять:
 +
#* для <tex>i=1\dots n</tex>
 +
#*# фиксируем значения всех переменных кроме <tex>x_i</tex>, получая одномерную функцию <tex>f(x_i)</tex>
 +
#*# проводим одномерную оптимизацию по переменной <tex>x_i</tex>, любым методом одномерной оптимизации
 +
#*# если выполен критерий останова, то возвращаем текущее значение <tex>x=(x_1,\dots,x_n)</tex>
 +
 +
===Критерий останова===
 +
Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях.
 +
Некоторые из них:
 +
# <tex>||x_{k+1}-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>-го шага оптимизации.
 +
 
 +
===Сходимость метода===
 +
[[Изображение:Coord1.PNG|thumb|122px|Рис.1]]
 +
 
 +
Легко убедится, что существуют функции, когда метод координатного спуска не приводит даже в локальный оптимум.
 +
 
 +
Пусть линии уровня образуют истинный овраг (рис.1), когда спуск по любой координате приводит на <<дно>> оврага, а любое движение по следующей координате (пунктирная линия) ведет на подъем. Никакой дальнейший спуск по координатам в данном случае невозможен, хотя минимум еще не достигнут.
 +
 
 +
'''Теорема о сходимости метода покоординатного спуска.'''
 +
 
 +
Для простоты рассмотрим функцию двух переменных <tex>f(x,y)</tex>. Выберем некоторое началное приближение <tex>(x_0,y_0)</tex> и проведем линию уровня через эту точку. Пусть в области <tex>G</tex>, ограниченной этой линией уровня, выполняются неравенства, означающий положительную определенность квадратичной формы:
 +
::<tex>f_{xx}''\geq a>0,\; f_{yy}''\geq b>0,\; |f_{xy}''|\leq c,\; ab>c^2.</tex>
 +
Тогда спуск по координатам сходится к минимуму из данного начального приближения, причем линейно.
 +
 
== Числовые примеры ==
== Числовые примеры ==
== Рекомендации программисту ==
== Рекомендации программисту ==

Версия 21:12, 18 ноября 2008

Содержание

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

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

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

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

Алгоритм

Вход: функция 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-го шага оптимизации.

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

Рис.1
Рис.1

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

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

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

Для простоты рассмотрим функцию двух переменных 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://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Anton/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты