前言

最近在学习深蓝学院的汪博讲的《机器人学中的数值优化》，本文用来记录与总结。在课程第一章汪博对凸函数 的性质花了很长时间介绍，本文略过。 水平有限，如有错误之处，敬请指正！

第一章无约束优化问题

无约束优化问题的定义为：

$\min_{x \in \mathbb{R}^n} f(x)$

其中，x 属于 n 维实数空间的变量。关于无约束的优化问题，课程中主要介绍了几种常见数值优化方法。本文对一些求导概念性属于进行介绍。

名称	符号	维度	X 维度	Y 维度
导数	f’(x)	1	1	1
梯度	▽f(x)	n × 1	n	1
海森	Hessian	n × n	n	1
雅可比	Jacobian	m × n	n	m

其中，梯度和海森分别是多输入单输出函数的一阶和二阶导数。

梯度下降法

梯度下降法顾名思义，利用的是梯度信息。具体的迭代表达式为：

$x_{k+1} = x_k - \alpha \nabla f(x_k)$

其中，α 为步长。

为什么需要步长这一概念？-▽f(x)是搜索的方向，如果走多了，会出现“曲折、振荡”的现象。线搜索 专门用于计算步长 α ，避免手动设定固定步长导致的收敛失败。

常见的确定步长方法有：

α = c ，为常数，这就特备容易引发上面说的振荡。
α = c / k ，步长随着迭代次数增加逐渐降低
精确线搜索
非精确线搜索

下面对几个线搜索相关的方法具体介绍。

【补充】线搜索

精确线搜索

假设第 k 步的最优步长为 $ α_k $，那么则构建出子优化问题：

$\alpha_k^* = \arg\min_{\alpha_k} f \left( \boldsymbol{x}_k + \alpha_k \, \boldsymbol{d}_k \right) \\ d_k = -\nabla f(x_k)$

但是此方法复杂度太高。

Armijo准则

$f(x_k) - f(x_k + \alpha d_k) \geq -c \cdot \alpha \nabla f(x_k)^T d_k$

一般 c 取(0,1)。公式咋得来的？请看：

$f(x_k + \alpha d_k) \approx f(x_k) + \alpha \nabla f(x_k)^T d_k + o(\alpha^2)\\ f(x_k) - f(x_k + \alpha d_k) \approx -\alpha \nabla f(x_k)^T d_k - o(\alpha^2)$

总的来说就是 实际下降量 ≥ 预期下降的缩小值。保证每次迭代的函数值下降是充分的，而非随意或微小的。所以，满足Armijo准则的条件又叫做充分下降条件。

弱Wolfe准则

弱Wolfe准则满足2个条件，分别为上述的Armijo条件和曲率条件。曲率条件表达式为：

$\nabla f (x_k + \alpha d_k)^\top d_k ≥ c_2 \nabla f(x_k)^\top d_k$

如下图，公式的左半边是Φ(α)函数的导数，物理意义是说，曲率条件的物理意义是Φ(α)函数在α的斜率大于等于c2倍的Φ(0)的斜率。只限制方向导数的下界，允许步长较大。

强Wolfe准则

强Wolfe准则和弱Wolfe准则的区别在于前者曲率条件多了个绝对值，也就是

$\|\nabla f(x + \alpha d)^T d_k\| \leq c_3 \|\nabla f(x)^T d_k\|$

为什么弱Wolfe准则 和 强Wolfe准则 的曲率条件一个是≥ 而一个是 ≤ ？

弱Wolfe 允许斜率过正，而强Wolfe准则避免斜率过度正或过度负，从而防止步长过大（如跳过极小点）或过小（收敛缓慢）。

牛顿法

梯度下降法是使用一阶梯度信息进行更新的，牛顿法则用到了二阶的Hessian矩阵。怎么得来的呢？首先，将f(x)进泰勒展开到二次项。

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

求极值，即求f’(x) = 0 （因为默认是光滑凸函数），对上面公式求导得到

$\nabla f(x_k) + \nabla^2 f(x_k) (x - x_k) = 0 \\ \mathbf x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$

这就得到了递推公式！，一般称x_k后面的为牛顿步。牛顿法相对于梯度下降法有更快的收敛速度，但是稳定性较差。因为需要求解Hessian的逆，所以呀需要 Hessian 非奇异且正定（非奇异—->求逆，正定—->牛顿步为下降方向），而且这一步很耗时。所以出现了一些解决方案：

使用修正矩阵M 去近似 Hessian
$M = \nabla^2 f(x) + \lambda I, \quad \epsilon = \min\left(1, \|\nabla f(x)\|, \ldots\right) / 10$
引入线性方程组，求解d代替求逆

$\nabla^2 f(x_k) d = -\nabla f(x_k)$

1）若 Hessian 矩阵半正定 ，使用Cholesky 分解

$\nabla^2 f(x_k) = LL^T$

其中 L 是下三角矩阵。

2）若Hessian 矩阵不定，使用Bunch-Kaufman 分解

$\nabla^2 f(x_k) = LDL^T$

其中 D 是 块对角矩阵 （稀疏矩阵）。可以很容易地去修改这些小块矩阵的特征值，把他们改成正数。

拟牛顿法

BFGS

总的来说，牛顿法还是存在不小的问题的，其一，不保证一定是下降方向；其二，二阶Hessian求解还是比较难的，所以出现了拟牛顿法，核心思想是使用一阶梯度信息去近似二阶信息。同样是求解B矩阵近似Hessian 。

对梯度▽f(x) 泰勒展开得到

$\nabla f(x_k + p) = \nabla f(x_k) + \nabla^2 f(x_k) p + \mathcal{O}(\|p\|^2)$

然后，由于x_k + p =x_k+1，带入得到

$\nabla f(x_{k+1}) - \nabla f(x_k) = \nabla^2 f(x_k) (x_{k+1} - x_{k+1})$

整理得到约束条件，一般叫做 牛顿条件：

$\Delta g^{k} = M^{k+1} \Delta x^{k} （梯度变化）\\ \Delta x^{k} = B^{k+1} \Delta g^{k} （变量变化）\\$

M和B互为逆矩阵，一般用第二个B 矩阵的公式。公式里变量具体含义为：

$\begin{aligned} B^{k+1} = \left[ \nabla^{2} f(x^{k}) \right]^{-1}, \Delta x^{k} = x^{k+1} - x^{k}, \Delta g^{k} = \nabla f(x^{k+1}) - \nabla f(x^{k}) \end{aligned}$

那么接下来去求B。核心思想是：尽量保留已有信息，同时满足牛顿条件。

$\min_{B} \| H^{1/2}(B - B^k)H^{1/2} \|^2 \\ \text{s.t.} \quad B = B^T, \quad \Delta x = B \Delta g$

通过一系列复杂的计算（没看懂），最终得到BFGS算法的迭代公式，3 2 1 上公式！

这是一个迭代更新的过程，每一轮迭代优化步都需要对B矩阵进行更新，从而用历史的一阶梯度信息，对二阶信息进行迭代估计。

但这个方法的缺点越比较明显：

存储和计算开销较大，去近似的Hessian矩阵，需要n × n 的空间，当变量维数很大，内存和计算代价高
无法保证B^k+1 正定，不能保证目标函数下降，所以一般与线搜索连用

L-BFGS

核心思路：使用有限个的历史梯度变化，近似Hessian ，直接上伪代码！

共轭梯度法

共轭梯度法是专门用来求解线性方程的。共轭梯度法在每步迭代中选择一组与A共轭的方向。主啵累了，放公式：

参考

1 2	https://zhuanlan.zhihu.com/p/670856639 https://www.shenlanxueyuan.com/course/745

A Blog

Optimization in Robot (1)

前言

第一章无约束优化问题

梯度下降法