Алгоритм Trust-Region

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

Перейти к: навигация, поиск

Содержание

Введение

Рассмотрим здачу минимизации
\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)}

Пример

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

Заключение

Литература

Смотри также

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