主要内容是最优化中的牛顿法和拟牛顿法，还包括最简单的最速下降法，都是用于求解无约束最优化问题的梯度类最经典算法。

对于无约束最优化问题 \[ \min_{x \in R^n} f(x) \] 通用的算法流程如下：

  1. 初始化，选取起点 \(x^0\)，记 \(k=0\)
  2. 在当前位置 \(x^k\)，获取搜索方向 \(d^k\)，通常是基于当前位置的一阶导和二阶导信息
  3. 在给定方向上进行一维搜索，\(a^k = \text{argmin}_{a \ge 0} f(x + a d^k)\)，获取步长因子 \(a^k\)
  4. 更新 \(x^{k+1} = x^k + a^k d^k\)，\(k=k+1\)，回到第二步

关于一维搜索的细节，这里不做讨论，这篇笔记只关注搜索方向的确定。

最速下降法

每一次的搜索相当于对 \(f\) 进行了一阶的泰勒展开。 \[ \begin{aligned} f(x) &= f(x^k) + \nabla f(x^k)^T (x-x^k) + O(|x-x^k|^2) \\ \end{aligned} \] 这里记 \(g^k\) 为梯度方向，在下文中用于简写。 \[ g^k = \nabla f(x^k) \] 取搜索方向为负梯度方向，此时可以保证函数值下降 \[ d^k = - \nabla f(x^k) \]

牛顿法

每一次的搜索相当于对 \(f\) 进行了二阶的泰勒展开。 \[ \begin{aligned} f(x) &= f(x^k) + \nabla f(x^k)^T (x-x^k) + \frac12 (x-x^k)^T \nabla^2 f(x^k)(x-x_k)+ O(|x-x^k|^3) \\ \end{aligned} \] 这里的二阶导是hesse矩阵 \[ G_k = \nabla^2 f(x^k) \] 针对二次函数取极小点 \(x^*\)，当前点向极小点的位移方向取为搜索方向 \[ d^k = x^* - x^k= - {G_k}^{-1}\nabla f(x^k) \]

牛顿法存在的最大问题是：我们希望需要计算的hesse矩阵是对称正定的，但是实际问题中hesse矩阵可能不定，此时二次近似没有极小值点；甚至可能矩阵不可逆，计算无法继续。

  • 经典的牛顿法不会进行一维搜索，总是取步长为 1；
  • 阻尼牛顿法：在经典的牛顿法基础上，使用一维搜索确定步长。

拟牛顿法

为了克服牛顿法的困难，更好的做法是采用一族对称正定矩阵 \(H_k\) 作为 \(\nabla^2 f(x^k)\) 的近似逆，使得计算可以继续。

牛顿方向 \(d^k\) 满足 \[ G_k (-d^k) = g^k \] 引入如下记号 \[ \begin{aligned} s^k &= x^{k+1}-x^k\\ y^k &= \nabla f(x^{k+1}) - \nabla f(x^k) \end{aligned} \] 近似有下式成立 \[ y^k = G_{k+1} s^k \] 我们希望构造 \(H_{k+1} \approx G_{k+1}^{-1}\) ，满足下式（称为正割条件，拟牛顿条件） \[ H_{k+1} y^k = s^k \] 这里的构造并不唯一，对应是不同的拟牛顿法。

拟牛顿法的一般流程为：

  1. 初始化，选取起点 \(x^0\)，令 \(H_0=I\)，记 \(k=0\)
  2. 在当前位置 \(x^k\)，计算 \(H_k\)，获取搜索方向 \(d^k= - H_k \nabla f(x^k)\)
  3. 在给定方向上进行一维搜索，\(a^k = \text{argmin}_{a \ge 0} f(x + a d^k)\)，获取步长因子 \(a^k\)
  4. 更新 \(x^{k+1} = x^k + a^k d^k\)，\(k=k+1\)，回到第二步

hesse矩阵的对称正定近似逆 \(\{H_k\}\) 的构造是依次进行的，基于上一步添加一个低秩矩阵而来 \[ \begin{aligned} H_{k+1} &= H_k + E_k\\ H_0 &= I \end{aligned} \]

对称秩一校正（SR1）

近似逆采用如下形式计算 \[ H_{k+1} = H_k + a u u^T \] 利用拟牛顿条件可得 \[ H_{k+1} = H_k + \frac{(s^k-H_k y^k)(s^k-H_k y^k)^T}{(s^k-H_k y^k)^T y^k} \] 对称秩一校正可以保证对称性，但不能保证正定，不能完全满足需求。

对称秩二校正（SR2）

近似逆采用如下形式计算 \[ H_{k+1} = H_k + a u u^T + b vv^T \] 拟牛顿条件 \[ H_{k+1}y^k = H_k y^k + (au^Ty^k)u + (bv^T y^k)v = s^k \] 对称秩二校正自由度过多，拟牛顿条件和对称正定性质不足以保证唯一解

一种取法是 \[ \begin{aligned} u &= s^k\\ a u^T y^k &= 1\\ v &= -H_k y^k\\ b v^T y^k &= -1 \end{aligned} \] 得到 DFP 校正公式 \[ H_{k+1}^{DFP}=H_k + \frac{s^k (s^k)^T}{(s^k)^T y^k} - \frac{H_k y^k (y^k)^{T}H_k}{(y^k)^T H_k y^k} \]

另一种取法是 BFGS 校正公式（相当于对 \(G_k\) 直接进行DFP对称秩二校正，然后取逆） \[ H_{k+1}^{BFGS}=H_k + \left(1+\frac{(y^k)^T H_k y^k}{(s^k)^T y^k}\right)\frac{s^k (s^k)^T}{(s^k)^T y^k} - \frac{H_k y^k (s^k)^{T} + s^k (y^k)^T H_k}{(s^k)^T y^k} \]