Алгоритм Trust-Region

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

Содержание

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

Введение

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