---

[toc]

最速下降法

最速下降法即下降方向是梯度的负方向，步长由精确线搜索得到

一般步骤如下：

1. 给出$x_0,k:=0$
2. 若终止条件满足，迭代停止
3. 计算$d_k=-g_k$
4. 精确线搜索得到$\alpha_k$
5. $x_{k+1}:=x_k-\alpha_kg_k,k:=k+1$,转步2

---

对目的函数$min_x\ f(x)=\frac{1}{2}x^TAx+b^Tx+c$

一阶导数$g_k= \nabla{f(x_k)} =Ax+b$

又更新公式为$x_{k+1}=x_k-\alpha_kg_k$

求$\alpha$，由$g_{k+1}^Tg_k=0$,带入

$$\begin{aligned} g_{k+1}&=Ax_{k+1}+b\\ &=A(x_k-\alpha_kg_k)+b\\ &=Ax_k+b-A\alpha_k\nabla{f(x_k)}\\ &=g_k-A\alpha_kg_k \end{aligned}$$

所以

$$\begin{aligned} g_{k+1}^Tg_k&=(g_k-A\alpha_kg_k)^Tg_k\\ &=(g_k^T-\alpha_kg_k^TA^T)g_k\\ &=0 \end{aligned}$$

所以$\alpha_k=\Large\frac{g_k^Tg_k}{g_k^TAg_k}$

所以$x_{k+1}=x_k-\Large{\frac{g_k^Tg_k}{g_k^TAg_k}}\normalsize g_k$

Newton 方法

对于要优化的目标函数$f(x)$，当前迭代点为$x_k$，则$f(x)$在$x_k$处的Taylor展开式为

$$f(x_k+d)\approx f(x_k)+\nabla{f(x)}^Td+\frac{1}{2}d^T\nabla^2f(x)d$$

当$x_k$固定时，$d$取多少使得$f(x_k+d)$最小？当$f(x_k+d)$最小，则$f(x_k+d)$对$d$的偏导为0

$$\begin{aligned} &\frac{\partial}{\partial{d}}f(x_k+d) = \nabla{f(x)} + \nabla^2f(x)d = 0\\ &\therefore d = -\nabla^2f(x_k)^{-1}\nabla{f(x_k)} \\ &\therefore x_{k+1} = x_k + d = x_k - \nabla^2f(x_k)^{-1}\nabla{f(x_k)}\\ &\therefore x_{k+1} = x_k - G_k^{-1}g_k \end{aligned}$$

拟Newton方法

Newton方法的缺点：每步迭代都需要计算Hesse矩阵，为此需要计算二阶偏导；若该方法产生的迭代点不能充分接近极小点，$G_k$的正定性不能保证

Newton方法的优点：具有二阶收敛速度

所以我们构造一种不需要计算二阶偏导，又具有较快的收敛速度，我们采用了拟Newton方法

对目标函数$f(x)$在$x_{k+1}$处进行Taylor展开，得到

$$\begin{aligned} f(x)&\approx f(x_{k+1}) + \nabla{f(x_{k+1})}(x-x_{k+1}) + \nabla^2f(x_{k+1})(x-x_{k+1}) \\ &= f(x_{k+1}) + \nabla^2f(x_{k+1})(x-x_{k+1})\\ \end{aligned}$$

令$x=x_k$，有$f(x_k)=f(x_{k+1})+G_{k+1}(x_k-x_{k+1})$

令$f(x_{k+1})-f(x_k)=y_k,x_{k+1}-x_k=s_k$，则有

$$G_{k+1}s_k=y_k$$

因为$B_{k+1}$是$G_{k+1}$的近似矩阵，所以同样的也有:

$$B_{k+1}s_k=y_k$$

若记$H_{k+1}=B_{k+1}^{-1}$,则

$$H_{k+1}y_k=s_k$$

拟牛顿方法是确定迭代方向d的最优化方法

每次迭代中，我们还要修正$H_{k+1}$，即是$H_{k+1}=H_k+\Delta{H_k}$中确定$\Delta H_k$

拟Newton法修正公式

对称秩1公式（Symmetric Rank 1，SR1）

令$B_{k+1}=arg\ min_{B^T=B}||B-B_k||$

考虑更新$B_{k+1}=B_k + \frac{1}{a}vv^T$，代入$B_{k+1}s_k=y_k$，得到

$$\begin{aligned} (B_k+\frac{1}{a}vv^T)s_k&=y_k\\ \frac{v^Ts_k}{a}v&=y_k-B_ks_k \end{aligned}$$

所以$v$与$y_k-B_ks_k$同向，令$v=\tilde{a}(y_k-B_ks_k)$，则

$$B_{k+1}=B_k+\frac{\tilde a^2}{a}(y_k-B_ks_k)(y_k-B_ks_k)^T$$

设$b=\Large\frac{\tilde a^2}{a}$，两边同乘于$s_k$，得

$$\begin{aligned} B_{k+1}s_k&=B_ks_k+b(y_k-B_ks_k)(y_k-B_ks_k)^Ts_k \\ y_k&=B_ks_k+b(y_k-B_ks_k)(y_k-B_ks_k)^Ts_k\\ y_k-B_ks_k&=b(y_k-B_ks_k)(y_k-B_ks_k)^Ts_k\\ 1&=b(y_k-B_ks_k)^Ts_k\\ \therefore b&=\frac{1}{(y_k-B_ks_k)^Ts_k} \end{aligned}$$

由$b=\Large\frac{\tilde a^2}{a}$，令$\tilde a=1$，得到$a=(y_k-B_ks_k)^Ts_k$

将$\tilde a=1$代入$v=\tilde{a}(y_k-B_ks_k)$,得到$v=y_k-B_ks_k$

将$v=y_k-B_ks_k,a=(y_k-B_ks_k)^Ts_k$代入$B_{k+1}=B_k+\Large\frac{1}{a}\normalsize vv^T$，得到

$$\begin{aligned} B_{k+1}&=B_k+\frac{1}{(y-B_ks_k)^Ts_k}(y_k-B_ks_k)(y_k-B_ks_k)^T\\ B_{k+1}&=B_k+\frac{(y_k-B_ks_k)(y_k-B_ks_k)^T}{(y-B_ks_k)^Ts_k} \end{aligned}$$

DFP公式

对秩2公式$H_{k+1}=H_k + \alpha u_ku_k^T+ \beta v_kv_k^T$

令$E_k = \alpha u_ku_k^T+ \beta v_kv_k^T$则$H_{k+1}=H_k+E_k$,代入拟牛顿方程$H_{k+1}y_k=s_k$,得到

$$(H_k+E_k)y_k=s_k$$

其中$v_k^Ty_k=\begin{bmatrix}v_1\...\\v_n\end{bmatrix}^T\begin{bmatrix}y_1\...\\y_n\end{bmatrix}=v_1y_1+…+v_ny_n$是一个常数,$u_k^Ty_k$同理

即是

$$\begin{aligned} (H_k+\alpha u_ku_k^T+ \beta v_kv_k^T)y_k&=s_k\\ H_ky_k+\alpha{u_ku_k^Ty_k}+\beta{v_kv_k^Ty_k}&=s_k\\ \alpha(u_k^Ty_k)u_k+\beta(v_k^Ty_k)v_k&=s_k-H_ky_k\\ \end{aligned}$$

假设$u_k=rH_ky_k,v_k=\theta s_k$,则

$$\begin{aligned} E_k&=\alpha{rH_ky_k}(rH_ky_k)^T+\beta{\theta{s_k}(\theta{s_k})^T}\\ &=\alpha r^2H_ky_ky_k^TH_k+\beta \theta^2s_ks_k^T \end{aligned}$$

代入$\alpha(u_k^Ty_k)u_k+\beta(v_k^Ty_k)v_k=s_k-H_ky_k$,得

$$\begin{aligned} &\alpha[(rH_ky_k)^Ty_k](rH_ky_k)+\beta[(\theta{s_k})^Ty_k](\theta{s_k})=s_k-H_ky_k\\ &[\alpha r^2(y_k^TH_ky_k)+1](H_ky_k)+[\beta\theta^2(s_k^Ty_k)-1](s_k)=0\\ \end{aligned}$$

令$[\alpha r^2(y_k^TH_ky_k)+1]=0,[\beta\theta^2(s_k^Ty_k)-1]=0$.得到

$$\alpha r^2(y_k^TH_ky_k)+1=0,\beta\theta^2(s_k^Ty_k)-1=0\\ \therefore \alpha r^2=-\frac{1}{y_k^TH_ky_k},\beta\theta^2=\frac{1}{s_k^Ty_k}$$

所以

$$\begin{aligned} H_{k+1}&=H_k + E_k\\ &=H_k+\alpha r^2H_ky_ky_k^TH_k+\beta \theta^2s_ks_k^T\\ &=H_k-\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}+\frac{s_ks_k^T}{s_k^Ty_k} \end{aligned}$$

为什么$H_k^T=H_k$?

因为Hesse矩阵是对称矩阵，而$H_k=B_k^{-1}\approx G_k^{-1}$

BFGS公式

考虑$B_{k+1}=B_k+\alpha{vv^T}+\beta{uu^T}$

代入拟牛顿方程$B_{k+1}s_k=y_k$，得

$$\begin{aligned} (B_k+\alpha{vv^T}+\beta{uu^T})s_k&=y_k\\ \alpha(v^Ts_k)v+\beta(u^Ts_k)u&=y_k-B_ks_k \end{aligned}$$

观察式子，可令$v=ry_k,u=\theta B_ks_k$，代入上式得

$$\begin{aligned} \alpha((ry_k)^Ts_k)(ry_k)+\beta((\theta B_ks_k)^Ts_k)(\theta B_ks_k)&=y_k-B_ks_k\\ (\alpha r^2(y_k^Ts_k)-1)(y_k)+(\beta\theta^2(s_k^TB_ks_k)+1)(B_ks_k))&=0 \end{aligned}$$

则,可令

$$\alpha r^2(y_k^Ts_k)-1 = 0，\beta\theta^2(s_k^TB_ks_k)+1=0\\ \therefore \alpha r^2=\frac{1}{y_k^Ts_k},\beta\theta^2=-\frac{1}{s_k^TB_ks_k}$$

又

$$\begin{aligned} &\alpha vv^T+\beta uu^T\\ =&\alpha (ry_k)(ry_k)^T+\beta(\theta B_ks_k)(\theta B_ks_k)^T\\ =&\alpha r^2y_ky_k^T+\beta\theta^2B_ks_ks_k^TB_k \end{aligned}$$

将$\alpha r^2$和$\beta\theta^2$代入，得

$$\begin{aligned} B_{k+1}&=B_k + \alpha vv^T+\beta uu^T\\ &= B_k + \alpha r^2y_ky_k^T+\beta\theta^2B_ks_ks_k^TB_k\\ &= B_k + \frac{y_ky_k^T}{y_k^Ts_k}-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} \end{aligned}$$