# 优化算法的分类

• 零阶优化：只使用函数 $f(x)$ 本身
  • 遗传算法
  • 贝叶斯优化
• 一阶优化：使用函数 $f(x)$ 和其梯度 $\nabla f(x)$
  • 梯度下降算法
  • 随机梯度下降算法
• 二阶优化：使用函数 $f(x)$、其梯度 $\nabla f(x)$ 和其 Hessian 矩阵 $\nabla^2 f(x)$
  • 牛顿法
  • 拟牛顿法

# 牛顿法

二阶泰勒展开如下：

$$f(\textbf{x}^k + \textbf{d}^k) = f(\textbf{x}^k) + \nabla f(\textbf{x}^k)^T \textbf{d}^k + \frac{1}{2} \textbf{d}^T \nabla^2 f(\textbf{x}^k) \textbf{d}^k$$

# 修正牛顿法

$$\bm{x}^{k+1} = \bm{x}^{k} - \alpha_k S^k \nabla f(\bm{x}^{k}), \quad \bm{S}^k \in \mathbb{R}^{n \times n}.$$

其中当 $S^k = \textbf{I}_n$ 时，为梯度下降算法，当 $\bm{S}^k = [\nabla^2 f(\bm{x}^k)]^{-1}$ 时，为拟牛顿法。

# 收敛性分析

$$\epsilon(\bm{x}^{k+1}) \leq \left(\frac{\Lambda^k - \lambda^k}{\Lambda^k + \lambda^k}\right)^2 \epsilon(\bm{x}^{k}), \quad \lambda^k = \min_{i} \lambda_i^k, \Lambda^k = \max_{i} \lambda_i^k.$$

$\Lambda - \lambda$ 称为条件数 (conditioning number), 条件数越小，算法收敛越快。

怎么保证 $\nabla^2 f(\bm{x})$ 正定？

# 近似牛顿法

每次计算 Hession 矩阵都是一个立方复杂度。因此产生了近似牛顿法。

最简单的方式是不更新 Hessian 矩阵，但是会造成误差。

另外，注意到牛顿法的复杂度在于计算 Hessian 的逆矩阵

$$\bm{d}^k = -[\nabla^2 f(\bm{x}^k)]^{-1} \nabla f(\bm{x}^k),$$

该计算的时间复杂度为 $\mathcal{O}(n^3)$, 空间复杂度为 $\mathcal{O}(n^2)$. 这实际上是求线性方程组：

$$\nabla^2f(\bm{x}^k) \bm{d}^k = \nabla f(\bm{x}^k).$$

线性方程组可以使用优化算法来进行近似的快速计算。嗯，其实就是用梯度下降。

# PCG

此外，还可以用改进条件数的方法进行优化。对线性方程组 \bm{Ax} = \bm

# 拟牛顿法

牛顿法存在两个问题

1. Hessian 矩阵不一定正定
2. 需要计算 Hessian 的逆，复杂度过高

拟牛顿法的策略为：

1. 构造一个 Hessian 矩阵（只需要满足 Hessian 阵的部分性质），保持其正定性
2. 通过迭代方式更新 Hessian 矩阵，降低复杂度