无约束优化算法

第六章 无约束优化算法

本章考虑如下无约束优化问题
$$\underset{x\in R^n}{\min }f(x)\text{\hspace{1em}(6.0.1)}$$
其中$f(x)$是$R^n\to R$的函数，无约束优化问题是众多优化问题中最基本的问题，它对自变量$x$的取值范围不加限制，所以无需考虑$x$的可行性。对于光滑函数，我们可以较容易的利用梯度和海瑟矩阵的信息来设计算法；对于非光滑函数，我们可以利用次梯度来构造迭代格式。很多无约束优化问题的算法思想可以推广到其他优化问题上。

无约束优化问题的优化算法主要分为两大类：线搜索类型的优化算法和信赖域类型的优化算法，它们都是对函数$f(x)$在局部进行近似，但处理近似问题的方式不同。
线搜索类算法根据搜索方向的不同可以分为梯度类算法、次梯度算法、牛顿算法、拟牛顿算法等。一旦确定了搜索的方向，下一步即沿着该方向寻找下一个迭代点。
而信赖域算法主要针对$f(x)$二阶可微的情形，它是在一个给定的区域内使用二阶模型近似原问题，通过不断直接求解该二阶模型从而找到最优值点。

6.1 线搜索方法

对于优化问题6.0.1，我们将求解$f(x)$的最小值点的过程比喻成下山的过程，假设一个人处于某点$x$处，$f(x)$表示此处的高度，为了寻找最低点，在点$x$处需要确定如下两件事情，第一，下一步该向哪一方向行走；第二，沿着该方向行走多远后停下以便选取下一个下山方向，以上这两个因素确定后，便可以一直重复，直至到达$f(x)$的最小值点

线搜索类算法的数学表述为：给定当前迭代点$x^k$，首先通过某种算法选取向量$d^k$，之后确定正数${\alpha }_k$，则下一步的迭代点可写作
$$x^{k+1}=x^k+{\alpha }_k{d}^k$$
我们称$d^k$为迭代点$x^k$处的搜索方向，${\alpha }_k$为相应的步长。这里要求$d^k$是一个下降方向，即$(d^k{)}^T\nabla f(x^k)<0$。这个下降性质保证了沿着此方向搜索函数$f$的值会减少。线搜索类算法的关键是如何选取一个好的方向以及合适的步长。
在本节中，我们回答如何选取${\alpha }_k$这一问题，这是因为选取$d^k$的方法千差万别，但选取${\alpha }_k$的方法在不同算法中非常相似，首先构造辅助函数
$$\varphi (\alpha )=f(x^k+\alpha d^k)$$
其中$d^k$是给定的下降方向，$\alpha >0$是该辅助函数的自变量，函数$\varphi (\alpha )$的几何含义非常直观，它是一个目标函数$f(x)$在射线 { x k + α d k : α > 0 } \{x^k+\alpha{d^k}:\alpha>0\} {xk+αdk:α>0}上的限制。注意到$\varphi (\alpha )$是一个一元函数，而我们研究一元函数相对比较方便。
线搜索的目标是选取合适的${\alpha }_k$使得$\varphi ({\alpha }_k)$尽可能的小，但这项工作并不容易，${\alpha }_k$应该使得$f$充分下降，同时不应该在寻找${\alpha }_k$上花费过多的计算量，我们需要权衡这两个方面。
首先一个最直接的想法是寻找${\alpha }_k$使得
$${\alpha }_k=argma{x}_{\alpha >0}\varphi (\alpha )$$
即${\alpha }_k$为最佳步长。这种线搜索算法被称为精确线搜索算法。需要指出的是，使用精确线搜索算法时我们可以在多数情况下得到优化问题的解，但选取${\alpha }_k$通常需要很大计算量，在实际应用中较少使用。
另一个想法不要求${\alpha }_k$是$\varphi (\alpha )$的最小值点，而仅仅要求$\varphi ({\alpha }_k)$满足某些不等式性质。这种线搜索算法被称为非精确线搜索算法

PS：说实话，因为我最近深度学习做的多，好像跟这一块有点区别

6.1.1 线搜索准则

我们选取${\alpha }_k$需要满足一定的要求，这些要求被称为线搜索准则。这里指出，线搜索准则的合适与否直接决定了算法的收敛性，若选取不合适的线搜索准则将会导致算法无法收敛
例6.4 考虑一维无约束优化问题
$$\underset{x}{\min }f(x)=x^2$$
迭代初始点$x^0=1$，由于问题是一维的，下降方向只有{-1,1}两种，我们选取$d^k=-sign(x^k)$，且只要求选取的步长满足迭代点处函数值单调下降，考虑选取如下两种步长
$${\alpha }_{k,1}=\frac{1}{3^{k+1}},{\alpha }_{k,2}=1+\frac{2}{3^{k+1}}$$
通过简单计算可以得到（一步步递推把，等比公式，从k=0开始推，然后最后变一下把k+1变成k）
$$x_1^k=\frac{1}{2}(1+\frac{1}{3^k}),x_2^k=\frac{(-1{)}^k}{2}(1+\frac{1}{3^k})$$
可以看到序列 { f ( x 1 k ) } \{f(x_1^k)\} {f(x1k​)}和序列 { f ( x 2 k ) } \{f(x_2^k)\} {f(x2k​)}均单调下降，但序列1收敛的点不是极小值点，序列2则在原点左右振荡。
出现上述情况的原因是在迭代过程中下降量不够充分或过于多了。以至于算法无法收敛到极小值点，为了避免这种情况发生，必须引入一些更合理的线搜索准则来确保迭代的收敛性。

1. Armijo准则

我们首先引入Armijo准则，它是一个常用的线搜索准则，引入Armijo准则的目的是保证每一步迭代充分下降
定义6.1（Armijo准则）设$d^k$是点$x^k$处的下降方向，若
$$f(x^k,\alpha d^k)\le f(x^k)+c_1\alpha \nabla f(x^k{)}^T{d}^k\text{\hspace{1em}(6.1.2)}$$
则称步长$\alpha$满足$Armijo$准则，其中$c_1\in (0,1)$是一个常数
$Armoji$的几何含义我没有弄明白，就是你的$\alpha$要在一个直线下方$\nabla f(x^k{)}^T{d}^k$是$\varphi (0{)}^{\prime }$

$f(x^k+\alpha d^k)$可以充分下降，但是你又不能跨太大，所以后面那一项又带有步长和斜率，如果够斜的话，你的步子就应该小一点。
在实际应用中，参数$c_{!}$通常选一个很小的正数，例如$c_1=10^{-3}$，这使得$Armijo$准则非常容易满足，但是仅仅使用$Armijo$准则无法保证迭代的收敛性，因为$\alpha =0$也满足条件，因此，$Armijo$准则需要配合其他准则共同使用。
在优化算法的时间中，寻找一个满足$Armijo$准则的步长是比较容易的，一个常用的算法是回退法。给定初值$\hat{\alpha }$，回退法通过不断以指数方式缩小试探步长，找到第一个满足$Armijo$准则的点，具体来说，回退法选取
$${\alpha }_k={\gamma }^{j_0}\hat{\alpha }$$
其中
j 0 = min ⁡ { j = 0 , 1 , ⋯ ∣ f ( x k + γ j α ^ d k ) ≤ f ( x k ) + c 1 γ j α ^ ∇ f ( x k ) T d k } j_0=\min\{j=0,1,\cdots|f(x^k+\gamma^j\hat{\alpha}d^k){\le}f(x^k)+c_1\gamma^j\hat{\alpha}\nabla{f(x^k)^T}d^k\} j0​=min{j=0,1,⋯∣f(xk+γjα^dk)≤f(xk)+c1​γjα^∇f(xk)Tdk}
其中参数$\gamma \in (0,1)$为一个给定的实数，看伪代码会比较简单

可以确保输出的${\alpha }_k$尽量的大，此外算法6.1不会无限进行下去，因为$d^k$是一个下降方向，当$\alpha$充分小时，会满足的，实际上我们通常会给$\alpha$设置一个下届，防止步长过小。

2.Goldstein准则

为了克服$Armijo$准则的缺陷，我们需要引入其他准则来保证每一步的${\alpha }^k$不会太小，既然$Armijo$准则要求点$(\alpha ,\varphi (\alpha ))$必须处在某直线下方，我们也可以使用 相同的形式使得点必须在另一条直线上方，这就是$Armijo-Goldstein$准则，简称$Goldstein$准则
定义6.2($GoldStein$准则)设$d^k$是点$x^k$处的下降方向，若
$$f(x^k+\alpha d^k)\le f(x^k)+c\alpha \nabla f(x^k{)}^T{d}^k\text{\hspace{1em}(6.1.3a)}$$
$$f(x^k+\alpha d^k)\ge f(x^k)+(1-c)\alpha \nabla f(x^k{)}^T{d}^k\text{\hspace{1em}(6.1.3b)}$$
则称步长$\alpha$满足$Goldstein$准则，其中$c\in (0,\frac{1}{2})$

总之就是这样确实会防止$\alpha$过小，这个从式子上都能看出来。

3.Wolfe准则

$Goldstein$准则能够使得函数值充分下降，但是它可能避开了最优的函数值，如上图所示，为此我们引入$Armijo-Wolfe$准则，简称$Wolfe$准则
定义6.3（$Wolfe$准则），设$d^k$是点$x^k$处的下降方向，若
$$f(x^k+\alpha d^k)\le f(x^k)+c_1\alpha \nabla {f(x^k)}^T{d}^k\text{\hspace{1em}(6.1.4a)}$$
$$\nabla f(x^k+\alpha d^k)\ge c_2\nabla f(x^k{)}^T{d}^k\text{\hspace{1em}(6.1.4b)}$$
则称步长$\alpha$满足$Wolfe$准则，其中$c_1,c_2\in (0,1)$为给定的常数且$c_1<c_2$
第一个不等式就是$Armijo$准则，则第二个不等式则是$Wolfe$准则的本质要求，注意到$\nabla f(x^k+\alpha d^k)d^k$就是$\varphi (\alpha )$的导数，$Wolfe$准则实际要求$\varphi (\alpha )$在点$\alpha$的切线的斜率不能小于${\varphi }^{\prime }(0)$的$c_2$倍，注意到在极小点处有${\varphi }^{\prime }({\alpha }^{\ast })=\nabla {f(x^k+{\alpha }^{\ast }{d}^k)}^T{d}^k=0$所以${\alpha }^{\ast }$永远满足条件6.1.4b，而选择较小的$c_1$可使得${\alpha }^k$同时满足6.1.4a，实际应用中，$c_2$通常取0.9

4.非单调线搜索准则

以上介绍的三种准则都有一个共同点：使用这些准则产生的迭代点列都是单调的，在实际应用中，非单调算法有时会有更好的效果，这就需要我们应用非单调的搜索准则，这里介绍其中两种
定义6.4（$Grippo$）设$d^k$是点$x^k$处的下降方向，$M>0$为给定的正整数，以下不等式可作为一种线搜索准则
f ( x k + α d k ) ≤ max ⁡ 0 ≤ j ≤ m i n { k , M } f ( x k − 1 + c 1 α ∇ f ( x k ) T d k ) (6.1.5) f(x^k+\alpha{d^k}){\le}\max_{0{\le}j\le{min\{k,M\}}}f(x^{k-1}+c_1\alpha{\nabla{f(x^k)^Td^k}})\tag{6.1.5} f(xk+αdk)≤0≤j≤min{k,M}max​f(xk−1+c1​α∇f(xk)Tdk)(6.1.5)
其中$c_1\in (0,1)$为给定的常数
准则6.1.5和$Armijo$准则非常相似，区别在于$Armijo$准则要求下一次迭代的函数值相对于本次迭代的函数值有充分下降，而准则6.1.5只需要下一步的函数值相比前面至多M步以内迭代的函数值有下降就可以了，显然比$Armijo$更宽，也不要求$f(x^k)$的单调性

另一种非单调线搜索准则的定义更加宽泛
定义6.5设$d^k$是点$x^k$处的下降方向，以下不等式可作为一种线搜索准则
$$f(x^k+\alpha d^k)\le C^k+c_1\alpha \nabla f(x^k{)}^T{d}^k\text{\hspace{1em}(6.1.6)}$$
其中$C^k$满足递推式$C^0=f(x^0),C^{k+1}=\frac{1}{Q^{k+1}}(\eta Q^k{C}^k+f(x^{k+1}))$，$Q^0=1,Q^{k+1}=\eta Q^k+1$

我们可以用以下方式理解这个准则，变量$C^k$实际上是本次搜索准则的参照函数值，即充分下降性质的起始标准，而下一步的标准$C^{k+1}$是函数值$f(x^{k+1})和$$C^k$是凸组合，并非仅仅依赖于$f(x^{k+1})$

6.1.2 线搜索算法

本小节介绍在实际中使用的线搜索算法，之前的讨论已经初步介绍了回退法，并指出该算法可以用于寻找$Armijo$准则的步长，实际上只要修改一下算法的终止条件，回退法就可以被用在其他线搜索准则，例如之前我们提到的两种非单调线搜索准则6.15和6.16。回退法实现简单，原理直观，所以它是最常用的线搜索算法之一。
然而，回退法的缺点也很明显：第一，它无法保证找到$Wolfe$准则的步长，即条件6.1.4b不一定成立，但对一些优化算法而言，找到满足$Wolfe$准则的步长是十分必要的，第二，回退法以指数的方式缩小步长，因此对初值和参数$\gamma$的选取比较敏感， 下面简单介绍一下其他类型的线搜索算法。
为了提到回退法的效率，我们有基于多项式插值的线搜索算法，假设初始步长$\widehat{{\alpha }_0}$已给定，如果经过验证，$\widehat{{\alpha }_0}$不满足$Armijo$准则，下一步就需要减少试探步长，和回退法不同，我们不直接将$\widehat{{\alpha }_0}$缩小常数倍，而是基于$\varphi (0),{\varphi }^{\prime }(0),\varphi ({\hat{\alpha }}_0)$这三个信息构造一个二次插值函数$p_2(\alpha )$，即寻找二次函数$p_2(\alpha )$满足
$$p_2(0)=\varphi (0),p_2^{\prime }(0)={\varphi }^{\prime }(0),p_2(\widehat{{\alpha }_0})=\varphi (\widehat{{\alpha }_0})$$
三个条件可以确定一个唯一的$p_2(\alpha )$。而且不难验证其最小值点恰到位于$(0,\widehat{{\alpha }_0})$内，此时取$p_2(\alpha )$的最小值点作为下一个试探点，不断递归下去
基于插值的线搜索算法可以有效减少试探次数，但仍然不能保证找到的步长满足$Wolfe$准则，为此$Fletcher$提出了一个用于寻找满足$Wolfe$准则的算法，这个算法比较复杂，就不展开叙述。

6.1.3 收敛性分析

这一小节给出使用不同线搜索准则导出的算法的收敛性，此收敛性建立在一般的线搜索类算法的框架上，因此得到的结论也比较弱，不过它可以帮助我们理解线搜索算法收敛的本质要求。
定理6.1（Zoutendijk）考虑一般的迭代格式6.1.1，其中$d^k$是搜索方向，${\alpha }_k$是步长，且在迭代过程中$Wolfe$准则6.1.4满足，假设目标函数$f$下有界，连续可微且梯度L-利普希茨连续，即
$$||\nabla f(x)-\nabla f(y)||\le L||x-y||,\forall x,y\in R^n$$
那么
$$\sum _{k=0}^{\infty }co{s}^2{\theta }_k||\nabla f(x^k)|{|}^2<+\infty \text{\hspace{1em}(6.1.7)}$$
其中$cos{\theta }_k$为负梯度$-\nabla f(x^k)$和下降方向$d^k$夹角的余弦
不等式6.1.7也被称为$Zoutendijk$条件
证明先略
推论6.1（线搜索算法的收敛性）对于迭代法6.1.1，设${\theta }_k$为每一步负梯度$-\nabla f(x^k)$与下降方向$d^k$的夹角，并假设对任意的$k$，存在常数$\gamma >0$，使得
$${\theta }_k<\frac{\pi }{2}-\gamma \text{\hspace{1em}(6.1.8)}$$
则在定理6.1成立的条件下，有
$$\underset{k\to \infty }{\lim }\nabla f(x^k)=0$$
推论6.1建立在$Zoutendijk$条件之上，他的本质要求是关系6.1.8，即每一步的下降方向$d^k$和负梯度方向不能趋于正交，这个条件的几何直观明显，当下降方向$d^k$和梯度正交时，目标函数值几乎不会发生改变。因此我们要求$d^k$与梯度正交方向夹角有一致的下界，后面会介绍多种$d^k$的选取方法。
总的来说，推论6.1仅仅给出了最基本的收敛性，而没有更进一步回答算法的收敛速度，这是由于算法收敛速度极大地取决于$d^k$的选取，接下来我们将着重介绍如何选取下降方向$d^k$。

6.2 梯度类算法

本节介绍梯度类算法，其本质是仅仅使用函数的一阶导数信息选取下降方向$d^k$，这其中最基本的算法是梯度下降法，即直接选择负梯度作为下降方向$d^k$，梯度下降法的方向选取非常直观，实际应用范围非常广，因此它在优化算法中的地位可相当于高斯消元法在线性方程组算法中的地位。
此外我们也会介绍BB算法，该方法作为一种梯度法的变形，虽然理论性质目前仍不完整，但由于它有优秀的数值表现，也是在实际应用中使用较多的一种算法。

6.2.1 梯度下降法

对于光滑函数$f(x)$，在迭代点$x^k$处，我们需要选择一个较为合理的$d^k$作为下降方向，注意到$\varphi (\alpha )=f(x^k+\alpha d^k)$有泰勒展开
$$\varphi (\alpha )=f(x^k)+\alpha \nabla f(x^k{)}^T{d}^k+O({\alpha }^2||d^k|{|}^2)$$
根据柯西不等式，当$\alpha$足够小时，取$d^k=-\nabla f(x^k)$的算法，它的迭代格式为
$$x^{k+1}=x^k-{\alpha }_k\nabla f(x^k)\text{\hspace{1em}(6.2.1)}$$
步长的选取可依赖于上一节的线搜索算法，也可以直接选取固定的${\alpha }_k$
定理6.2 考虑正定二次函数
$$f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x$$
其最优值点为$x^{\ast }$，若使用梯度法6.2.1并选取${\alpha }_k$为精确线搜索步长，即
$${\alpha }_k=\frac{||\nabla f(x^k)|{|}^2}{\nabla f(x^k{)}^{T}A\nabla f(x^k)}\text{\hspace{1em}(6.2.2)}$$
则梯度法关于迭代点列 { x k } \{x^k\} {xk}是Q-线性收敛的，即
$$||x^{k+1}-x^{\ast }|{|}_A^2\le (\frac{{\lambda }_1-{\lambda }_n}{{\lambda }_1+{\lambda }_n}{)}^2||x^k-x^{\ast }|{|}_A^2$$
其中${\lambda }_1,{\lambda }_n$分别为$A$的最大、最小特征值
$||x|{|}_A=\sqrt{x^{T}Ax}$
定理6.2指出使用精确线搜索的梯度法在正定二次问题上有Q-线性收敛速度，线性收敛速度的常数和矩阵$A$最大特征值与最小特征值之比有关，这个比例越大，梯度迭代收敛也就越慢，这个结果其实说明了梯度法一个很重大的缺陷，当目标函数的海瑟矩阵条件数较大时，它的收敛速度会非常缓慢。
接下里我们介绍当$f(x)$为梯度利普希茨连续的凸函数时，梯度法的收敛性质
定理6.3（梯度法在凸函数上的收敛性）设函数$f(x)$为凸的梯度L-利普希茨连续函数，$f^{\ast }=f(x^{\ast })={\inf }_{x}f(x)$存在且可达，如果步长${\alpha }_k$取常数$\alpha$且满足$0<\alpha <\frac{1}{L}$，那么由迭代6.2.1得到的点列 { x k } \{x^k\} {xk}的函数值收敛到最优值，且在函数值意义下收敛速度为$\mathcal{O}(\frac{1}{k})$
证明略，如果函数$f$还是$m-强凸函数$，则梯度法的收敛速度会进一步提升为Q-线性收敛。
要证收敛性证明前需要知道以下引理（但我们就不证了）
引理6.1 设函数$f(x)$是$R^n$上的凸可微函数，则以下结论等价：
（1）$f$的梯度为L-利普希茨连续的
（2）函数$g(x)=\frac{L}{2}{x}^{T}x-f(x)$是凸函数
（3）$\nabla f(x)$有余强制性，即对任意的$x,y\in R^n$，有
$$(\nabla f(x)-\nabla f(y){)}^T(x-y)\ge \frac{1}{L}||\nabla f(x)-\nabla f(y)|{|}^2\text{\hspace{1em}(6.2.4)}$$
证明略

定理6.4（梯度法在强凸函数上的收敛性）设函数$f(x)$为m-强凸的梯度L-利普希茨连续函数，$f^{\ast }=f(x^{\ast })={\inf }_{x}f(x)$存在且可达，如果步长$\alpha$满足$0<\alpha <\frac{2}{m+L}$，那么由梯度下降法6.2.1迭代得到的点列 { x k } \{x^k\} {xk}收敛到$x^{\ast }$，且为Q-线性收敛

6.2.2 Barzilar-Borwein 方法

当问题的条件数很大，即问题比较病态时，梯度下降法的收敛性质会受到很大影响，BB方法是一种特殊的梯度法，经常比一般的梯度法有着更好的效果，从形式上来看，BB方法的下降方向仍是点$x^k$处的负梯度方向$-\nabla f(x^k)$，但步长${\alpha }_k$并不是直接由线搜索算法给出的，考虑梯度下降的格式：
$$x^{k+1}=x^k-{\alpha }_k\nabla f(x^k)$$
这种格式也可以写成
$$x^{k+1}=x^k-D^k\nabla f(x^k)$$
其中$D^k={\alpha }_{k}I$,BB方法选取的${\alpha }_k$是如下两个最优问题之一的解：
$$\underset{\alpha }{\min }||\alpha y^{k-1}-s^{k-1}|{|}^2,\text{\hspace{1em}(6.2.7)}$$
$$\underset{\alpha }{\min }||y^{k-1}-{\alpha }^{-1}{s}^{k-1}|{|}^2,\text{\hspace{1em}(6.2.8)}$$
其中引入记号$s^{k-1}=x^k-x^{k-1}$以及$y^{k-1}=\nabla f(x^k)-\nabla f(x^{k-1})$。这里先直接写出6.2.7和6.2.8，它们的实际含义将在6.5小节中给出合理解释
容易验证问题6.2.7和6.2.8的解分别为
$${\alpha }_{BB1}^k=\frac{(s^{k-1}{)}^T{y}^{k-1}}{(y^{k-1}{)}^T{y}^{k-1}},{\alpha }_{BB2}^k=\frac{(s^{k-1}{)}^T{s}^{k-1}}{(s^{k-1}{)}^T{y}^{k-1}}\text{\hspace{1em}(6.2.9)}$$
因此可以得到BB方法的两种迭代格式
$$x^{k+1}=x^k-{\alpha }_{BB1}^k\nabla f(x^k)\text{\hspace{1em}(6.2.10a)}$$
$$x^{k+1}=x^k-{\alpha }_{BB2}^k\nabla f(x^k)\text{\hspace{1em}(6.2.10b)}$$
我们从6.29注意到，计算两种BB步长的任意一种仅仅需要函数相邻两步的梯度信息和迭代点信息，不需要任何线搜索算法即可选取算法步长。因为这个特点，BB方法的使用范围特别广泛，对于一般的问题，通过6.2.9式计算出的步长可以过大或过小，我们还需要将步长做截断
$${\alpha }_m\le {\alpha }_k\le {\alpha }_M$$
需要注意的是，BB算法本身是非单调方法，有时配合非单调收敛准则使用可以获得更好的实际效果

例如二次函数的BB算法

可以看到BB算法的收敛速度较快，实际上，对于正定二次函数，BB方法有Q-超线性收敛速度，对于一般问题，BB算法的收敛性还需要进一步研究，但即使如此，使用BB算法的步长通常会减少算法迭代次数，因此在编写算法时，选取BB方法的步长是常用加速策略之一。