Алгоритм Trust-Region

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (15:09, 14 декабря 2008) (править) (отменить)
 
(1 промежуточная версия не показана)
Строка 3: Строка 3:
<tex>\min_x f(x)</tex> <tex>x \in R^n</tex><br>
<tex>\min_x f(x)</tex> <tex>x \in R^n</tex><br>
==Метод решения задачи==
==Метод решения задачи==
-
Алгоритм Trust-Region основан на построение модельной функции <tex>m_k</tex>, которая приближает исходную в некоторой окрестности текущей точки <tex>x_k</tex>. При этом функция <tex>m_k</tex> может полхо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки <tex>x_k</tex>. Другими словами, решается здача:<br>
+
Алгоритм Trust-Region основан на построение модельной функции <tex>m_k</tex>, которая приближает исходную в некоторой окрестности текущей точки <tex>x_k</tex>. При этом функция <tex>m_k</tex> может плохо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки <tex>x_k</tex>. Другими словами, решается здача:<br>
<tex>\min_p m_k(x_k + p)</tex>, где <tex>x_k + p</tex> лежит внутри доверельной окрестности <br>
<tex>\min_p m_k(x_k + p)</tex>, где <tex>x_k + p</tex> лежит внутри доверельной окрестности <br>
Обычно, доверительная окрестность - шар радиуса <tex>||p||_2 < \Delta</tex>. В качесте модели функции <tex>m_k</tex> обычно берется квадратичная: <br>
Обычно, доверительная окрестность - шар радиуса <tex>||p||_2 < \Delta</tex>. В качесте модели функции <tex>m_k</tex> обычно берется квадратичная: <br>
-
<tex>m_k (x + p) = f_k + p^T\nabla f_k + \frac12p^TH_kp</tex><br>
+
<tex>m_k (p) = f_k + p^T\nabla f_k + \frac12p^TH_kp</tex><br>
 +
- разложение функции f по формуле Тейлора до второго слааемого.<br>
 +
Итак, на каждом шаге решается подзадача:<br>
 +
<tex>m_k (p) = f_k + p^T\nabla f_k + \frac12p^TH_kp</tex> s.t.<tex>||p||_2 < \Delta_k</tex><br>
Первая проблема, которая возникает, это определение радиуса доверительного интервала. Мы выбираем этот радиус, исходя из модели функции <tex>m_k</tex> и функции f на предыдущий итерациях. Определим соотношение<br>
Первая проблема, которая возникает, это определение радиуса доверительного интервала. Мы выбираем этот радиус, исходя из модели функции <tex>m_k</tex> и функции f на предыдущий итерациях. Определим соотношение<br>
-
<tex>\rho_k = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}</tex>
+
<tex>\rho_k = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}</tex><br>
==Пример==
==Пример==
==Рекомендации программисту==
==Рекомендации программисту==

Текущая версия

Содержание

Введение

Рассмотрим здачу минимизации
\min_x  f(x) x \in R^n

Метод решения задачи

Алгоритм Trust-Region основан на построение модельной функции m_k, которая приближает исходную в некоторой окрестности текущей точки x_k. При этом функция m_k может плохо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки x_k. Другими словами, решается здача:
\min_p  m_k(x_k + p), где x_k + p лежит внутри доверельной окрестности
Обычно, доверительная окрестность - шар радиуса ||p||_2 < \Delta. В качесте модели функции m_k обычно берется квадратичная:
m_k (p) = f_k + p^T\nabla f_k + \frac12p^TH_kp
- разложение функции f по формуле Тейлора до второго слааемого.
Итак, на каждом шаге решается подзадача:
m_k (p) = f_k + p^T\nabla f_k + \frac12p^TH_kp s.t.||p||_2 < \Delta_k
Первая проблема, которая возникает, это определение радиуса доверительного интервала. Мы выбираем этот радиус, исходя из модели функции m_k и функции f на предыдущий итерациях. Определим соотношение
\rho_k = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}

Пример

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

Заключение

Литература

Смотри также

Личные инструменты