漫步最优化四十四——基本拟牛顿法

你走进了我的视觉， $\textbf{你走进了我的视觉，}$

我开始发现， $\textbf{我开始发现，}$

心里有个角落， $\textbf{心里有个角落，}$

一直在等你出现。 $\textbf{一直在等你出现。}$

你的可爱让我沦陷， $\textbf{你的可爱让我沦陷，}$

你的魅力让我倾倒， $\textbf{你的魅力让我倾倒，}$

总是想着看你一遍， $\textbf{总是想着看你一遍，}$

不管天涯海角， $\textbf{不管天涯海角，}$

我要在你的身边。 $\textbf{我要在你的身边。}$

——畅宝宝的傻逼哥哥 $\textbf{——畅宝宝的傻逼哥哥}$

对于前面介绍的方法，第

k $k$ 次迭代生成的点由

x k + 1 = x k - α k S k g k (1)

$\begin{equation} \mathbf{x}_{k+1}=\mathbf{x}_k-\alpha_k\mathbf{S}_k\mathbf{g}_k\tag1 \end{equation}$

生成，其中

S k = {I n H - 1 k 对 于 最 速 下 降 法 对 于 牛 顿 法

$\mathbf{S}_k= \begin{cases} \mathbf{I}_n&\text{对于最速下降法}\\ \mathbf{H}_k^{-1}&\text{对于牛顿法} \end{cases}$

如果二次问题为

minimize f (x) = a + b T x + 1 2 x T H x

$\text{minimize}\ f(\mathbf{x})=a+\mathbf{b}^T\mathbf{x}+\frac{1}{2}\mathbf{x}^T\mathbf{Hx}$

我们现在用任意一个 $n\times n$ 的正定矩阵 $\mathbf{S}_k$ 来求上述问题的解，看看会得到什么。通过对 $f(\mathbf{x}_k-\alpha\mathbf{S}_k\mathbf{g}_k)$ 求导并令其等于零，最小化 $f(\mathbf{x}_k-\alpha\mathbf{S}_k\mathbf{g}_k)$ 的 $\alpha$ 可以化简为

α k = g T k S k g k g T k S k H S k g k (2)

$\begin{equation} \alpha_k=\frac{\mathbf{g}_k^T\mathbf{S}_k\mathbf{g}_k}{\mathbf{g}_k^T\mathbf{S}_k\mathbf{H}\mathbf{S}_k\mathbf{g}_k}\tag2 \end{equation}$

其中

g k = b + H x k

$\mathbf{g}_k=\mathbf{b}+\mathbf{Hx}_k$

是 $f(\mathbf{x})$ 在点 $\mathbf{x}=\mathbf{x}_k$ 处的梯度。

可以说明的是

f (x k + 1) - f (x *) \leq (1 - r 1 + r) 2 [f (x k) - f (x *)]

$f(\mathbf{x}_{k+1})-f(\mathbf{x}^*)\leq\left(\frac{1-r}{1+r}\right)^2[f(\mathbf{x}_k)-f(\mathbf{x}^*)]$

其中 $r$ 是 $\mathbf{S}_k\mathbf{H}$ 最小特征值与最大特征值之比。从效果上看基于等式1与2的算法将线性收敛，其收敛比率为

β = (1 - r 1 + r) 2

$\beta=\left(\frac{1-r}{1+r}\right)^2$

如果 $r=1$ 收敛最快，即 $\mathbf{S}_k\mathbf{H}$ 的特征值基本相等，这就意味着要想得到最好的结果，我们需要选择

S k H = I n

$\mathbf{S}_k\mathbf{H}=\mathbf{I}_n$

或者

S k = H - 1

$\mathbf{S}_k=\mathbf{H}^{-1}$

同样地，对于一般的最优化问题，我们选择的正定矩阵 $\mathbf{S}_k$ 应该等于或者至少近似等于 $\mathbf{H}_k^{-1}$ 。

拟牛顿法的搜索方向基于正定矩阵 $\mathbf{S}_k$ ，它由可得到的数据生成，并设法作为 $\mathbf{H}_k^{-1}$ 的近似。对于 $\mathbf{H}_k^{-1}$ 的近似法有许多，因此存在许多不同的拟牛顿法。