Алгоритм Trust-Region

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

Версия 20:30, 18 ноября 2008 (править) М.А.Задонский (Обсуждение | вклад) ← К предыдущему изменению		Текущая версия (15:09, 14 декабря 2008) (править) (отменить) М.А.Задонский (Обсуждение | вклад)
(9 промежуточных версий не показаны.)
Строка 1:		Строка 1:
-	== Постановка задачи ==	+	==Введение==
-	=== Безусловная оптимизация ===	+	Рассмотрим здачу минимизации<br>
-	Среди задач на поиск безусловного минимума особое место занимают задачи минимизации функции вида:<br>к	+	<tex>\min_x f(x)</tex> <tex>x \in R^n</tex><br>
-	<tex>F(x) = \frac{1}{2}\sum_i{r_i^m(x)^2}</tex><br>	+	==Метод решения задачи==
-	где <tex>r_i(x)</tex> - гладкая нелинейная функция из <tex>R^n</tex> в <tex>R</tex>. Будем считать, что m ≥ n.<br>	+	Алгоритм Trust-Region основан на построение модельной функции <tex>m_k</tex>, которая приближает исходную в некоторой окрестности текущей точки <tex>x_k</tex>. При этом функция <tex>m_k</tex> может плохо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки <tex>x_k</tex>. Другими словами, решается здача:<br>
-	Если обозначить <tex>r_i(x) = (r_1(x),\dots,r_m(x))^T</tex><br>	+	<tex>\min_p m_k(x_k + p)</tex>, где <tex>x_k + p</tex> лежит внутри доверельной окрестности <br>
-	то <tex>F(x) = \frac{1}{2}||r(x)||_2^2</tex><br>	+	Обычно, доверительная окрестность - шар радиуса <tex>||p||_2 < \Delta</tex>. В качесте модели функции <tex>m_k</tex> обычно берется квадратичная: <br>
-	Обозначим якобиан функции r: <tex>J(x) = \frac{\delta r_j}{\delta x_i}</tex><br>	+	<tex>m_k (p) = f_k + p^T\nabla f_k + \frac12p^TH_kp</tex><br>
-	Тогда производные функции f(x) можно вычислить с помощью формул:<br>	+	- разложение функции f по формуле Тейлора до второго слааемого.<br>
-	<tex>\nabla f(x) = \sum_{j = 1}^m{r_j(x)\nabla r_j(x) = J(x)^Tr(x)}</tex><br>	+	Итак, на каждом шаге решается подзадача:<br>
-	<tex>\nabla^2 f(x) = \sum_{j = 1}^m{\nabla r_j(x)\nabla r_j(x) + \sum_{j = 1}^m{\nabla^2 r_j(x)r_j(x)= J(x)^TJ(x) + \sum_{j = 1}^m{\nabla^2 r_j(x)r_j(x)}</tex><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>\rho_k = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}</tex><br>
-	== Метод решения задачи ==	+	==Пример==
-	== Рекомендации программисту ==	+	==Рекомендации программисту==
-	== Выводы ==	+	==Заключение==
-	== Литература ==	+	==Литература==
-	Philip E. Gill Practical Otpimization 1981.<br>	+	== Смотри также ==
		+	* [[Практикум ММП ВМК, 4й курс, осень 2008]]
		+	{{stub}}
		+
		+	[[Категория:Учебные задачи]]

---

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

Содержание 1 Введение 2 Метод решения задачи 3 Пример 4 Рекомендации программисту 5 Заключение 6 Литература 7 Смотри также

Введение

Рассмотрим здачу минимизации

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

Алгоритм Trust-Region основан на построение модельной функции , которая приближает исходную в некоторой окрестности текущей точки . При этом функция может плохо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки . Другими словами, решается здача:
, где лежит внутри доверельной окрестности
Обычно, доверительная окрестность - шар радиуса . В качесте модели функции обычно берется квадратичная:

- разложение функции f по формуле Тейлора до второго слааемого.
Итак, на каждом шаге решается подзадача:
s.t.
Первая проблема, которая возникает, это определение радиуса доверительного интервала. Мы выбираем этот радиус, исходя из модели функции и функции f на предыдущий итерациях. Определим соотношение

Пример

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

Заключение

Литература

Смотри также

• Практикум ММП ВМК, 4й курс, осень 2008