Народное машинное обучение — метод оптимизации — метод Ньютона

@[toc]

Введение

Метод Ньютона, английское название BFGS, является одним из наиболее эффективных методов решения задач нелинейной оптимизации.

Функции

Быстрая сходимость;

Способ

Метод Ньютона представляет собой итерационный алгоритм, на каждом шаге которого необходимо решить целевую функциюМатрица ГессеОбратная матрица , вычисление более сложное (метод квазиньютона будет объяснен позже, а метод квазиньютона упрощает этот процесс, аппроксимируя обратную матрицу или матрицу Гессе матрицы Гессе положительно определенной матрицей.

анализировать

Рассмотрение задач неограниченной оптимизации

$\min_{x \in R} f(x)$

в $x^*$ точка минимума целевой функции. Предполагая, что f(x) имеет непрерывную частную производную второго порядка, если значение k-й итерации равно $x^{(k)}$ , то f(x) может быть $x^{(k)}$ Рядом выполняется разложение Тейлора второго порядка:

$f(x) = f(x^{k}) + g_{k}^{T}(x - x^{k}) + 1/2(x-x^{k})^TH(x^{k})(x - x^{k})$

$g_k = g(x^{k})= \nabla(f(x^{k}))$ - вектор градиента f (x) в $x^{(k)}$ значение .
$H(x^{k})$ - матрица Гессе функции f (x) $[\frac {\partial f^2} {\partial x_i \partial y_j}]_{nxn}$ существует $x^{(k)}$ значение .

Вот подробное объяснение матрицы Гессе в расширении Тейлора и временное объяснение расширения Тейлора бинарной функции. enter image description here

Затем продолжаем, необходимым условием для того, чтобы функция f(x) имела экстремальное значение, является то, что первая производная в точке экстремального значения равна 0, то есть вектор градиента равен 0. особенно когда $H(x^{k})$ Когда это положительно определенная матрица, экстремальное значение функции f (x) является минимальным значением, поэтому:

$\nabla(f(x)) = 0$

Производная по f(x), тогда

$\nabla(f(x) = f(x^{k}) + g_{k}^{T}(x - x^{k}) + 1/2(x-x^{k})^TH(x^{k}(x - x^{k})))$ $= g_k + H(x^{k})(x - x^{k})$ но $g_k + H(x^{k})(x^{k+1} - x^{k}) = 0$ $x^{k+1} - x^{k}= -H(x^k)^{-1}g_k$ или $x^{k+1} = x^{k} + p_k$ в $H(x^k)p_k = -g_k$ Вывод этой формулы завершен

алгоритм

Вход: целевая функция f(x), градиент $g(x) = \nabla f(x)$ , матрица Гессе H(x), требование точности ε; Выход: точка минимума x^* функции f(x);

взять начальное значение точки $x^{(0)}$ , к=0;
рассчитать $g_k = g(x^{(k)})$
как $||g_k|| < ε$ , затем останавливаем расчет и получаем решение $x^* = x^{(k)}$
рассчитать $H_k = H(x^{(k)})$ , и решить для $p_k$

$H(x^k)p_k = -g_k$ 5. Итерация, $x^{k+1} = x^{k} + p_k$ , запросить k++, перейти к шагу 2;