• n维牛顿法牛顿方法 迭代格式

  $$ \boldsymbol x^{(k+1)}=\boldsymbol x^{(k)}-\mathbf {F}(\boldsymbol{x}^{(k)})^{-1}\boldsymbol{g}^{(k)} $$

• 拟牛顿法：寻求海塞矩阵的近似

  1. 寻求$\boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1}$的近似

     $$ x^{(k+1)}=x^{(k)}-H_kg^{(k)} $$

  2. 寻求$\boldsymbol{F}(\boldsymbol{x}^{(k)})$的近似

     $$ x^{(k+1)}=x^{(k)}-(B_k)^{-1}g^{(k)}, $$

• 【割线方程】割线法使用差分格式近似梯度、海塞，本质是泰勒级数近似。

  注意这里是将当下的展开 到未来点上。

  $$ \begin{align}f^\prime (x)&\approx f(x^{(k+1)})+f^\prime (x_{k+1})(x-x^{(k+1)})\\f^{\prime\prime}(x^{(k)})& = \frac{f^{\prime}(x^{(k)})-f^{\prime}(x^{(k-1)})}{x^{(k)}-x^{(k-1)}} \\\end{align} $$

  多元函数寻求同样的泰勒展开，有：

  $$ \Delta g_k\approx \nabla^2f(x^{(k+1)})\cdot \Delta x\\\to H_{k+1} \Delta g_k\approx \Delta x\\\to or \ \Delta g_k\approx B_{k+1}\Delta x_k $$

  其中$\Delta g_k=\nabla f(x^{(k)})-\nabla f(x^{(k+1)}),\Delta x=x^{(k)}-x^{(k+1)}$.此线性方程组（割线方程,拟牛顿方程）有无穷解，寻求更多约束。

秩1校正拟牛顿法

已知海塞矩阵有性质

• 对称正定（极小化问题）

• 【更新过程变化尽量小：减小存储开销】$H_{k+1}=H_{k}+o(H_k)$. $o(H_k)$为一小扰动。

  取秩一校正$H_{k+1}$如下，实际是关于矩阵方程（拟牛顿方程）。

  $$

  \left\{ \begin{aligned} H_{k+1}\bm y_k&=x_k ,\bm u\in \mathbb F^{n\times 1},a\in \mathbb F\\ H_{k+1}&=H_k+a\bm u\bm u^T \end{aligned} \right.

  $$

  代入拟牛顿迭代格式方程，$a,u$待求解：

  $$ (H_k+a\bm u\bm u^T)\Delta \bm g_k=\Delta \bm x\\a\bm u(\bm u^T\Delta \bm g_k)=\Delta \bm x_k-H_k\Delta \bm g_k $$

  可以看出，$\bm u$与$\Delta \bm x_k-H_k\Delta \bm g_k$线性相关，那么可以写出$a(\bm u^T\Delta \bm g_k)=1，\bm u=\Delta \bm x_k-H_k\Delta \bm g_k$⇒$H_{k+1}=H_k+\frac{uu^T}{(u^T\Delta g_k)}$,也就是计算$H_{k+1}$只需要相对$H_k$更新迭代点$\Delta x,\Delta g$.算法一次迭代需要更新以下$2n$个量。

  $$ x^{(k+1)}=x^{(k)}-H_k\nabla f(x_k)\\ H_{k+1}=H_k+\frac{uu^T}{(u^T\Delta g_k)} $$

  拟牛顿法至少等于共轭梯度法（二次型问题有限步终止）。

增加了步长$\alpha_k$,有步长的算法比无步长搜索的算法更稳定（求解不同问题效果波动更小）.$H_0=I$

• 缺点

  1. 秩1公式分母接近零
  2. 秩1算法产生矩阵可能数值上非正定(奇异、病态)。

• 改进

  • 在秩1基础上，构造更精细的扰动模型：秩2模型，秩3模型

    $$ H_{k+1}=H_k+auu^T +bvv^T+\cdots $$

• 证明方法同上

                                                   $(H_k+auu^T+bvv^T)\\Delta g_k=\\Delta x$ 
  
                                          $au(u^T\\Delta g_k)+bv(v^T\\Delta g_k)=\\Delta x-H_k\\Delta g_k$
  

可见u与v的组合与$\Delta x-H_k\Delta g_k$线性相关令$a(u^T\Delta g_k)$与$a(v^T\Delta g_k)$都等于1，则$u=\Delta x$，$v=-H_k\Delta g_k$回代$H_{k+1}=H_k+auu^T +bvv^T+\cdots$可以得到

                                   $H_{k+1} =\\boldsymbol{H}_{k}+\\frac{\\Delta\\boldsymbol{x}^{(k)}\\Delta\\boldsymbol{x}^{(k)\\top}}{\\Delta\\boldsymbol{x}^{(k)\\top}\\Delta\\boldsymbol{g}^{(k)}}-\\frac{[\\boldsymbol{H}_{k}\\Delta\\boldsymbol{g}^{(k)}][\\boldsymbol{H}_{k}\\Delta\\boldsymbol{g}^{(k)}]^{\\top}}{\\Delta\\boldsymbol{g}^{(k)\\top}\\boldsymbol{H}_{k}\\Delta\\boldsymbol{g}^{(k)}}$

DFP算法 - 秩2校正算法

海塞矩阵取秩为2的扰动：

$$ \left\{\begin{aligned}&H_{k+1}\Delta g^{(k)}=\Delta x^{(k)}\\&H_{k+1}=H_k+auu^\mathrm{T}+bvv^\mathrm{T}\end{aligned}\right. $$

其中

$$ \left\{\begin{aligned}&\Delta\boldsymbol{x}^{(k)} =\alpha_{k}\boldsymbol{d}^{(k)} \\&\Delta\boldsymbol{g}^{(k)} =g^{(k+1)}-g^{(k)} \\ &\bm u=\Delta \bm x^{(k)}\\&\bm v=H_k \bm g^{(k)}\end{aligned}\right. $$