前言

在无约束优化中，我们依赖实变量来最小化目标函数。数学表达式为：
$\underset{x}{\text{min}}f(x)$

其中 $X \in R$ 是拥有 $n \geqslant 1$ 个元素的实数向量， $f:\mathbb{R}^n \rightarrow \mathbb{R}$ 是光滑函数。
通常，我们对函数 $f$ 缺乏全局的视角。我们所知道 $f$ 的值或许只是一些它在点集 $x_0,x_1,x_2,…$ 的导数。

例子 `最小二乘拟合`

最优解的定义

全局极小值的定义为：

$\text{点} x^° \text{是全局极小值,仅当} f(x^°) \leqslant f(x) , x \in \mathbb{R}$

由于我们关于 $f$ 的知识通常只是局部的，因此全局极小值很难去求解。
我们无法确定 $f$ 是否在算法无法采样的区域是否有急剧下降。大多数算法只能找到局部极小值。关于局部极小值的定义如下：
$\text{点} x^° \text{是局部极小值,仅当存在}x^°\text{的邻域} \mathbb{N}使得f(x^°)\leqslant f(x) , x \in \mathbb{N}$
上述定义有时成为弱极小值，在上述情况下，加强约束条件，就变成严格极小值。
$f(x^°) < f(x) , x \in \mathbb{N} with x \neq x^ °$

识别局部最小值

判断点 $x^°$ 紧邻的点是不是有更小的值。当 $f$ 是光滑函数时，很容易找到局部极小值。特别地，若 $f$ 连续二阶可导，可以通过判断梯度 $\nabla f(X^°)$ 和Hessian矩阵 $\nabla ^2f(X^°)$ 。
研究光滑函数的数学工具是泰勒定理。这个定理是本书的核心。

定理2.1 泰勒定理

假设 $f:\mathbb{R}^n \rightarrow \mathbb{R}$ 是连续可导的， $p \in \mathbb{R}$ ，那么存在 $t \in (0,1)$ 使
$f(x+p)=f(x)+ \nabla f(x+tp)^Tp$
如果 $f$ 是二阶连续可导，有
$\nabla f(x+p)=\nabla f(x)+ \int_0^1{\nabla ^2 f(x+tp)pdt}$
所以可得
$f(x+p)=f(x)+ \nabla f(x)^Tp + \frac{1}{2}p^T\nabla ^2 f(x+tp)p$

定理2.2 一阶必要条件

如果 $x^°$ 是极小值，在 $x^°$ 的开邻域 $f$ 连续光滑，那么 $\nabla f(x^°)=0$ 。

定理2.3 二阶必要条件

如果 $x^°$ 是极小值， $\nabla ^2 f$ 存在并且在 $x^°$ 的开邻域连续光滑，那么 $\nabla f(x^°)=0$ 、 $\nabla ^2 f(x^°)$ 是半正定矩阵。

定理2.4 二阶充分条件

如果 $\nabla f$ 是在 $x^°$ 的开邻域是连续的，且 $\nabla f(x^°)=0$ ，且 $\nabla ^2 f(x^°)$ 是正定矩阵，那么 $x^°$ 是严格极小值。

算法概述

所有的无约束算法都需要使用者提供一个起点 $x_0$ ，拥有数据集的使用者能够提供一个合理的估计初值。否则就需要算法通过系统性方法或任意的方式来选择起点。从 $x_0$ 开始，优化算法产生一系列迭代 $\{ x_k \}_{k=0}^\infty$ ，直到不能有任何改进或者以足够的精度逼近结果。
在决定迭代 $x_k$ 的下一次移动时，算法会参考 $f$ 在 $x_k$ 的信息，可能还会用到更早的迭代 $x_0,x_1,…,x_{k-1}$ 。算法使用这些信息能够找到比在 $x_k$ 的函数值新的迭代值 $x_{k+1}$ 。有两种基本的策略来从当前 $x_k$ 计算到 $x_{k+1}$ 的移动。

两种策略：线搜索和信任域

在线搜索方法中，算法在 $x_k$ 迭代时，会选择一个方向 $p_k$ ，使得新的迭代有更小的函数值。沿着 $p_k$ 移动的距离近似为下面的寻找步长 $\alpha$ 的一维最小化问题：
$\underset{\alpha >0}{\text{min}}f(x_k+\alpha p_k)$

第二种是信任域方法。通过构造模型函数 $m_k$ 来收集 $f$ 的信息， $m_k$ 在 $x_k$ 附近的特性应和目标函数相似。因为模型 $m_k$ 在离 $x_k$ 较远的 $x$ 处可能不是 $f$ 好的近似。所以我们强制在 $x_k$ 的某个区域来寻找 $m_k$ 的极小值。换句话说，我们通过近似求解下列子问题来寻找候选步 $p$ ：
$\underset{p}{\text{min}} m_k(x_k+p) , x_k+p\text{在信任域内}$

如果候选解不能产生 $f$ 上的充分下降，可以得知信任域太大，需要缩小并重新求解。通常，信任域是定义为 $\lVert \textrm{p} \rVert _2\le \Delta$ 的球，这里标量 $\Delta$ 成为信任域半径。椭圆、盒子形的信任域也有使用。
模型 $m_k$ 通常定义为二次方程：
$m_k(x_k+p)=f_k+p^T \nabla f_k +\frac{1}{2}p^TB_kp$
其中 $f_k$ ， $\nabla f_k$ ， $B_k$ 分别是标量、向量、矩阵。 $m_k$ 和 $f$ 在 $x_k$ 处一阶是相同的。 $B_k$ 是Hessian矩阵或者它的近似。

线搜索方法和信任域方法的区别就在计算方向和步长的次序上。
线搜索方法选择固定的方向 $p_k$ ，然后确定一个合适的步长；而信任域方法首先选择最大的信任域半径，然后寻找满足距离约束的最大改进可能的方向和步子，如果步子被证明是不满意的，我们减小信任域半径，重新计算。

线搜索方法中的搜索方向

在线搜索方法中，最速下降方向 $\nabla f_k$ 是明显的选择。它是在从 $x_k$ 出发的所有下降很快的方向之一。证明如下：对于任意搜索方向 $p$ 和步长因子 $\alpha$ ，我们有
$f(x_k+\alpha p)=f(x_k)+\alpha p^T \nabla f_k,\text{subject to } \lVert \textrm{p} \rVert =1$

$f$ 在 $x_k$ 处沿着方向 $p$ 的变化率简化成 $\alpha$ 的系数，即 $p^T \nabla f_k$ 。因此，单位方向 $p$ 的最快下降方向是下列问题的解。
$\underset{p}{\text{min}} p^T \nabla f_k ,\text{sunject to }\lVert p \rVert=1$

所以有
$p^T\nabla f_k=\lVert p \rVert \lVert \nabla f_k \rVert cos \theta=\lVert \nabla f_k \rVert cos \theta$
这里 $\theta$ 是 $p$ 和 $\nabla f_k$ 的角度。显然， $cos \theta =-1$ 上式到达最小，
$p=-\frac{ \nabla f_k}{ \lVert \nabla f_k \rVert}$

得证。
最速下降法是 $p_k=- \nabla f_k$ 的线搜索方法，它选择步长 $\alpha _k$ 有多种方式，优点之一就是只用到了梯度，没有用到二阶导数。但是，这个算法在一些比较难的问题上极其地慢。
线搜索搜索方法可能使用区别于最速下降法的搜索方向。通常，在步长充分小时，与 $- \nabla f_k$ 的角度小于 $\frac {\pi}{2}$ 的方向都能保证 $f$ 下降。

另外一个最重要的搜索方是牛顿方向。这个方向采用二阶泰勒展开式来逼近 $f(x_k+p)$
$f(x_k+p) \approx f_k +p^T \nabla f_k+ \frac{1}{2}p^T \nabla ^2 f_k \overset{\textrm{def}}{=} m_k(p)$
假设 $\nabla ^2 f_k$ 是正定的(二阶充分条件)，我们可以找到 $p$ 使 $m_k(p)$ 最小。令 $\nabla m_k(p)=0$ ，可得牛顿方向：
$p^N_k=- \frac{\nabla f_k }{\nabla ^2 f_k }$

当 $f(x_k+p)$ 和它的二次近似 $m_k(p)$ 差别不大时，牛顿方向还是很可靠的。

拟牛顿方向可以替代牛顿方向，因为他不用不同计算Hessian矩阵，而且仍然拥有超线性下降速度。它使用近似矩阵 $B_k$ 来替换Hessian矩阵， $B_k$ 会在每一次迭代中运用获得的知识来更新。

我们在 $x_{k+1}$ 处采用二次函数 $m_{k+1}$ 来近似目标函数 $f$
$m_{k+1}(p)=f_{k+1}+p^T \nabla f_{k+1} +\frac{1}{2}p^TB_{k+1}p$
如果我们有 $\nabla m_{k+1}$ 和 $\nabla f_{k+1}$ 在 $x_k$ 和 $x_{k+1}$ 处的值相同，那么可以认为是一个很好的近似。
当 $p=0$ 时，两者相等；
当 $p=-\alpha p_k$ 时，有
$\nabla m_{k+1}(-\alpha p_k)= \nabla f_{k+1} - \alpha B_{k+1}p_k=\nabla f_k$
进行移项，令 $s_k=x_{k+1}-x_k$ , $y_k=\nabla f_{k+1}-\nabla f_k$ ，我们可以得到割线方程
$B_{k+1}s_k=y_k$
因为 $B_{k+1}$ 是正定的，所以我们可以得到曲率条件：
$s_k^TB_{k+1}s_k=s_k^T y_k>0$
两个比较常用的更新 $B_{k+1}$ 的方式是SR1和BFGS。

SR1公式定义如下：
$B_{k+1}=B_k+\frac{(y_k - B_k s_k)(y_k - B_k s_k)^T}{(y_k - B_k s_k)^Ts_k}$

BFGS公式定义如下：
$B_{k+1}=B_k-\frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^Ts_k}$

$B_k$ 和 $B_{k+1}$ 在SR1中是秩为1的矩阵，在BFGS中是秩为2的矩阵。相同点都满足割线方程，都是对称矩阵。
拟牛顿搜索方向可以在牛顿方向上替换Hessian矩阵为 $B_k$ 得到：
$p_k=-B_k^{-1} \nabla f_k$
一些拟牛顿的实现方法通过更新 $B_k^{-1}$ 而不是 $B_k$ 来避免分解计算。
如果有 $H_k \overset{\textrm{def}}{=} B_k^{-1}$ ，那么在SR1和BFGS方程可以转化成：
$H_{k+1}=(I- \rho _k s_k y_k^T)H_k(I-\rho _k y_k s_k^T)+\rho s_k s_k^T,\rho _k=\frac{1}{y_k^Ts_k}$

$p_k$ 可以通过 $p_k=-H_k \nabla f$ 计算。

最后一种搜索方向是非线性共轭梯度法，公式如下：
$p_k=-\nabla f(x_k)+\beta _k p_{k-1}$
这里 $\beta _k$ 保证 $p_k$ 和 $p_{k+1}$ 是共轭的,共轭是在二次函数最小化中非常重要的概念。
共轭梯度法最初是用来求解 $Ax=b$ 的线性方程组的，这里 $A$ 是对称正定矩阵。求解线性系统等价于最小化如下的凸二次函数：
$\phi (x)=\frac{1}{2}x^T A x-b^Tx$
非线性共轭梯度法比最速下降法更有效且计算简单。它没有牛顿方法和拟牛顿方法的拟合速度快，但是不需要保存矩阵。

信任域方法中的模型

$m_k(x_k+p)=f_k+p^T \nabla f_k +\frac{1}{2}p^TB_kp$
如果令上式中的 $B_k=0$ ，且定义信任域使用欧几里得范数，那么信任域子问题变成
$\underset{p}{\text{min}} f_k +p^T \nabla f_k \quad \text{subject to } \lVert p \rVert \leqslant \varDelta _k$
那么解就是
$p_k=-\frac{\varDelta _k \nabla f_k}{\lVert \nabla f_k \rVert}$
这就是最速下降法上把步长设为信任域半径。
更有趣的信任域算法是将 $B_k$ 设为Hessian矩阵 $\nabla ^2 f_k$ ，那么就是信任域牛顿方法。如果 $B_k$ 通过拟牛顿方法来近似，那么就是信任域拟牛顿方法

尺度问题

考虑
$f(x)=10^9 x_1^2 +x_2^2$
对于 $x_1$ 对于小的变化非常敏感，而 $x_2$ 则不是。解决方法是令 $z=10^9 x_1$ 。一些算法例如最速下降法对于缩放是敏感的，而另一些，例如牛顿方法则不受影响。

总结

本章介绍了两种选择步长和搜索方向的策略，即线搜索和信任域，两者主要区别是计算步长和搜索方向的步骤相反。对于搜索方向的选择，我们又有最速下降、牛顿、拟牛顿、非线性共轭梯度等方法。主要基础理论就是泰勒定理和矩阵相关知识。

原创文章，转载请注明出处。
刘文武 2016年9月7日于电子科大航空航空学院

前言

例子 最小二乘拟合