1 Newton 法

考虑无约束优化问题 $$\underset{x\in {\mathbb{R}}^n}{min}f(x),$$ 设 ${\displaystyle x^{\ast }}$ 是 ${\displaystyle f}$ 的极小值点. 设 ${\displaystyle f}$ 有二阶连续偏导数, 进行 Taylor 展开: $$\begin{array}{}\text{(1.1)}& f(x)=f(x^{(k)})+g_k^{\mathrm{T}}(x-x^{(k)})+\frac{1}{2}(x-x^{(k)}{)}^{\mathrm{T}}H(x^{(k)})(x-x^{(k)}),\end{array}$$ 这里 ${\displaystyle g_k=g(x^{(k)})=\mathrm{\nabla }f(x^{(k)})}$, ${\displaystyle H(x)={\left[\frac{{\partial }^{2}f}{\partial x_i\partial x_j}\right]}_{n\times n}}$ 为 Hessian 矩阵, ${\displaystyle H_k=H(x^{(k)})}$. ${\displaystyle f(x)}$ 有极值的必要条件是 ${\displaystyle \mathrm{\nabla }f(x^{\ast })=0}$, 且 ${\displaystyle H(x^{\ast })}$ 正定.

接下来需要推导迭代方式, 假设从 ${\displaystyle x^{(k)}}$ 出发得到了 ${\displaystyle x^{(k+1)}}$ 就是极小值点, 也即 ${\displaystyle g_{k+1}=0}$. 而由 (1.1) 左右同时取梯度: $$\begin{array}{}\text{(1.2)}& \mathrm{\nabla }f(x)=g_k+H_k(x-x^{(k)}).\end{array}$$^[1] 从而再带入 ${\displaystyle x^{(k+1)}}$: $$g_k+H_k(x^{(k+1)}-x^{(k)})=0\Rightarrow x^{(k+1)}=x^{(k)}-H_k^{-1}{g}_k,$$ 然后记 ${\displaystyle p_k=H_k^{-1}{g}_k}$.

2 拟 Newton 法

上述 Newton 法最后需要计算 ${\displaystyle H^{-1}}$, 计算量较大, 希望通过一个 ${\displaystyle G_k=G(x^{(k)})}$ 来近似代替 ${\displaystyle H_k^{-1}}$.
首先考查一下 ${\displaystyle H_k}$ 满足的条件. 对 (1.2), 取 ${\displaystyle x=x^{(k+1)}}$: $$g_{k+1}-g_k=H_k(x^{(k+1)}-x^{(k)}).$$ 记 ${\displaystyle y_k=g_{k+1}-g_k,{\delta }_k=x^{(k+1)}-x^{(k)}}$, 则 $$\begin{array}{}\text{(2.1)}& y_k=H_k{\delta }_k\Rightarrow H_k^{-1}{y}_k={\delta }_k.\end{array}$$ (这称为拟 Newton 条件).

当 ${\displaystyle H_k}$ 正定, ${\displaystyle H_k^{-1}}$ 也是正定的. 由于 Newton 法中搜索方向是 ${\displaystyle p_k=-H_k^{-1}{g}_k}$, 因此该方向上的点 ${\displaystyle x}$ 满足 $$x=x^{(k)}+\lambda p_k=x^{(k)}-\lambda H_k^{-1}{g}_k,$$ 因此 ${\displaystyle f(x)}$ 的 Taylor 展开近似为 $$f(x)=f(x^{(k)})-\lambda g_k^{\mathrm{T}}{H}_k^{-1}{g}_k.$$ 而 ${\displaystyle H_k^{-1}}$ 正定, 总有 ${\displaystyle g_k^{\mathrm{T}}{H}_k^{-1}{g}_k>0}$, 当 ${\displaystyle \lambda >0}$ 充分小, 总有 ${\displaystyle f(x)<f(x^{(k)})}$. 在拟 Newton 法中, ${\displaystyle G_k}$ 同样需要满足正定和拟Newton条件: $$G_{k+1}{y}_k={\delta }_k.$$

2.1 DFP 算法

^[2]

现在假设 ${\displaystyle G_{k+1}}$ 的更新公式为 $$G_{k+1}=G_k+P_k+Q_k$$ (${\displaystyle P_k,Q_k}$ 为两个附加项), 同右乘 ${\displaystyle y_k}$ 后考虑到拟 Newton条件, 可以让 ${\displaystyle P_k{y}_k={\delta }_k,Q_k{y}_k=-G_k{y}_k}$. 例如, 取 $$P_k=\frac{{\delta }_k{\delta }_k^{\mathrm{T}}}{{\delta }_k^{\mathrm{T}}{y}_k},Q_k=-\frac{G_k{y}_k{y}_k^{\mathrm{T}}{G}_k}{y_k^{\mathrm{T}}{G}_k{y}_k}.$$ 下面梳理这个算法

2.2 BFGS 算法

^[3]

这是当下最常用的拟 Newton 算法. 在上述 DFP 算法中, 我们用 ${\displaystyle G_k}$ 逼近 ${\displaystyle H^{-1}}$; 我们现在考虑用 ${\displaystyle B_k}$ 逼近 ${\displaystyle H}$. 此时拟 Newton 条件变为 ${\displaystyle B_{k+1}{\delta }_k=y_k}$. 同样令 $$B_{k+1}=B_k+P_k+Q_k,$$ 同时右乘 ${\displaystyle {\delta }_k}$, 然后考虑 $$P_k{\delta }_k=y_k,Q_k{\delta }_k=-B_k{\delta }_k$$ 然后给出

2.3 Broyden 类算法

根据 (4.1), 带入 ${\displaystyle G_k=B_k^{-1},G_{k+1}=B_{k+1}^{-1}}$, 然后应用 Sherman-Morrison公式得到 $$G_{k+1}=(I-\frac{{\delta }_k{y}_k^{\mathrm{T}}}{{\delta }_k^{\mathrm{T}}{y}_k})G_k{(I-\frac{{\delta }_k{y}_k^{\mathrm{T}}}{{\delta }_k^{\mathrm{T}}{y}_k})}^{\mathrm{T}}+\frac{{\delta }_k{\delta }_k^{\mathrm{T}}}{{\delta }_k^{\mathrm{T}}{y}_k},$$ 将这样的 ${\displaystyle G_k}$ 记作 ${\displaystyle G^{\mathrm{BFGS}}}$, 与 ${\displaystyle G^{\mathrm{DFP}}}$ 结合: $$G_{k+1}=\alpha G^{\mathrm{DFP}}+(1-\alpha )G^{\mathrm{BFGS}},0\le \alpha \le 1.$$