Алгоритм Trust-Region
Материал из MachineLearning.
| (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> может | + | Алгоритм 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 ( | + | <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> |
==Пример== | ==Пример== | ||
==Рекомендации программисту== | ==Рекомендации программисту== | ||
Текущая версия
Содержание |
Введение
Рассмотрим здачу минимизации
Метод решения задачи
Алгоритм Trust-Region основан на построение модельной функции , которая приближает исходную в некоторой окрестности текущей точки
. При этом функция
может плохо приближать f в других точках, поэтому мы ограничиваен минимизацию этой некоторой окрестностью точки
. Другими словами, решается здача:
, где
лежит внутри доверельной окрестности
Обычно, доверительная окрестность - шар радиуса . В качесте модели функции
обычно берется квадратичная:
- разложение функции f по формуле Тейлора до второго слааемого.
Итак, на каждом шаге решается подзадача:
s.t.
Первая проблема, которая возникает, это определение радиуса доверительного интервала. Мы выбираем этот радиус, исходя из модели функции и функции f на предыдущий итерациях. Определим соотношение
