前言
在无约束优化中，我们依赖实变量来最小化目标函数。数学表达式为：
$$\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日 于 电子科大航空航空学院
