优化方法

机器学习

牛顿法

牛顿法主要使用分线性方程的泰勒展开，分为求根与求极值，相当于每一步中用线性来逼近原始函数

求根

求根：$f(x) = 0$，这里直接用一阶泰勒展开

$$f(x) = f(x_0) + f'(x_0)(x-x_0)$$
令其等于$0$得
$$x = x_0 - \frac{f(x_0)}{f'(x_0)}$$

求极值

求极值需要求$f'(x)=0$，这里牛顿法用的二阶泰勒展开

对$f(x)$在$x_0$处进行二阶泰勒展开

$$f(x) = f(x_0) + f'(x_0)(x-x_0) + \frac{1}{2}f''(x_0)(x-x_0)^2 + \omicron(x-x_0)$$
对其求导
$$f(x)' = f'(x_0) + f''(x_0)(x-x_0) = 0$$
得
$$x = x_0 - \frac{f'(x_0)}{f''(x_0)}$$
如果换成向量的形式，则需要Jacobian矩阵$\mathbf{J}_f$和Hessian矩阵$\mathbf{H}_f$，Hessian是由函数f的二阶偏导组成的矩阵（方阵）。这里要求$f:x\in\mathbb{R}^n\mapsto \mathbb{R}^1$，既要求输入是$n$维的向量输出是一个数，这时Jacobian矩阵成了一个$n$维向量，Hessian矩阵为一个$n\times n$的方阵
$$\mathbf{H}_f = \begin{bmatrix} \frac{\partial f}{\partial x_1\partial x_1} & \frac{\partial f}{\partial x_1\partial x_2} & \cdots & \frac{\partial f}{\partial x_1\partial x_n} \\ \frac{\partial f}{\partial x_2\partial x_1} & \frac{\partial f}{\partial x_2\partial x_2} & \cdots & \frac{\partial f}{\partial x_2\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial x_n\partial x_1} & \frac{\partial f}{\partial x_n\partial x_2} & \cdots & \frac{\partial f}{\partial x_n\partial x_n} \end{bmatrix}$$
则上面的迭代公式变为

$$x = x_0 - \mathbf{H}_f^{-1}\mathbf{J}_f$$