经典牛顿法

经典牛顿法 #

考虑优化方向: $x_{k + 1} = x_k + \alpha_k p_k$ , 取步长 $\alpha_k = 1$ , 那么有 $x_{k + 1} = x_k + p_k$ , 需要求解 $$ p_k = \argmin_{p}f(x_{k + 1}) = \argmin_{p} f(x_k + p)\ = \argmin_{p} f(x_k) + \nabla f(x_k)^Tp + \frac{1}{2}p^T \nabla^2 f(x_k) p + o(||p||^2)\ \approx \argmin_{p} f(x_k) + \nabla f(x_k)^Tp + \frac{1}{2}p^T \nabla^2 f(x_k) p \ = \argmin_{p} g(p) $$ 这是关于 $p$ 的, 开口向上的二次函数, 能够找到 $p^*$ 让我们的 $g(p)$ 接近最小. 计算 $g(p)$ 的梯度: $$ \nabla_p g(p) =\nabla_x f(x_k) + \nabla_x^2 f(x_k)p = 0 $$ 变形后的式子也被称作牛顿方程: $$ \nabla^2 f(x_k)p = -\nabla f(x_k) $$ 如果 $f(x)$ 在 $x_k$ 处的 Hessian Matrix $\nabla^2 f(x_k)$ 是正定的, 我们有 $$ p = (\nabla^2 f(x_k))^{-1}\cdot \nabla f(x_k) $$ 计算内积查看 $p$ 与梯度之间的方向: $$ <\nabla f(x_k), p> = -\nabla f(x_k)^T\cdot (\nabla^2 f(x_k))^{-1} \cdot \nabla f(x_k) < 0 $$ 所以 $p$ 此时是下降方向. 对于 Hessian Matrix 非正定的情况, 无法确定 $p$ 的方向.