数值优化（四）——线搜索算法的收敛性

rustum

所谓算法的收敛性，就是通过迭代，算法一定能逼近最优解。我们前面讨论了线搜索算法的方向和步长，总结起来便是说每一次迭代都要能保证目标函数  充分下降，既然每次都是下降的，而  一定有下界，直觉上来说那么肯定是收敛的，但其实这样说并不严谨。举个例子，假设目标函数是 的抛物线函数，显然最优解 ，假设我们从初始值 出发，不排除算法会一步步这样迭代： ，每一次迭代 都更加靠近  ，目标函数值也都会下降，但显然只能收敛到 ，所以算法是不是真的能够到达最优解，还需要严格的证明。
收敛性的数学形式

我们说收敛的最优解，很简单的直接要求：



或者说



这样就说明算法能够到达最优解了，但有个问题是我们并不知道  或者 是多少(否则也不用求了)，这个条件并不好利用，但有一点我们是知道的，那就是 ，我们更常用这一点，如果算法满足：



我们就说算法是收敛的。
Zoutendijk条件

我们将收敛性证明分为两步，首先证明在一定条件下可以满足Zoutendijk条件，它的形式如下：



其中 ，为  与  的夹角余弦。
Lipschitz连续

Lipschitz连续是比连续性要求更强一点的连续，对于  来说，不光要求其连续，而且要求存在 满足：



其实变换成这种形式， ，就是说  的梯度不能有无穷大的地方，总之是有个上界的。

同样的，这是对一阶来说的，还可以要求  满足Lipschitz连续：


前提条件

对于一个优化问题和算法来说，不是在任何情况下都满足Zoutendijk条件的，我们想要证明Zoutendijk条件，首先需要整理清楚前提条件。第一点是我们考虑的定义域，前面学习过，迭代过程中要求每一步都是下降的，所以我们只需要考虑满足 的区域， 是我们的初始点，以后每次迭代都不会超过初始点，记作水平集 ，但  并不一定是连续的一块，我们将包含  的连续开区间记为  ，这就是我们考虑的范围。

在开区间  上，记 ，我们有以下几点要求，

• 满足Lipschitz连续，即公式
  
• 是下降方向，即
  
• 满足wolfe条件，即:
    
  
    
  

这几点要求对大多数优化问题来说都是比较容易满足的。
Zoutendijk条件证明

首先根据公式 有：



又根据公式(3)，有：



两边同时乘上 ：



根据向量内积知 ，则有：



联立公式 可知：



又因为公式  中 ，所以将公式 代入  ，有：



再将 带入：



其中，记 ，带入：



将公式 左右两边累加则有：



  是有下界的，  趋近无穷大时， ，所以



所以证得Zoutendijk条件：

  
收敛性证明

上面我们已经证明了在一定条件下，可以推导出Zoutendijk条件：

  

更进一步，如果能够证明



那么显然要想仍然满足Zoutendijk条件，则只能要求 ，从而证明了收敛性。

观察公式 ，也就是要求 与 有一定距离，也就是下降方向  与最速下降方向  不会趋近于正交。其实直观上来讲这一点还是很好理解的，既然  是下降方向，那么它自然应该比较贴近最速下降方向，如果她与最速下降方向接近正交，那么沿着  目标函数是趋近保持不变的，这显然不是算法构造  的初衷。所以只要算法构造的  能够保证与正交有一定距离，那么算法就是收敛的。



红色为最速下降方向，绿色为梯度方向，黄色为正交方向



分别来看一下，对于最速下降方向， ，天然的 ，则自然满足收敛性。

对于牛顿方向和拟牛顿方向，我们统一记 ，其中  是牛顿方向中的黑塞矩阵，拟牛顿方向中构建的近似黑塞矩阵，我们要求  是正定的，并且有特征值 ，则有：





所以，只要  的条件数满足 ，也就是:

那就满足了收敛性，其中 为某一常数。

上述不等式的放缩需要一点矩阵条件数的知识，放到了末尾补充。
总结

总结一下，算法的收敛性要求当  趋近于无穷大时，梯度  趋近于 ，也就是最优解。为了证明收敛性，我们首先证明在一定条件下满足Zoutendijk条件，进一步证明了如果能够保证下降方向远离与(负)梯度方向正交，便满足收敛性。而且分别分析了最速下降方向和(拟)牛顿方向的收敛性要求，其中最速下降方向自然满足，(拟)牛顿方向要求(近似)黑塞矩阵条件数小于某一常数。
矩阵条件数

向量范数是对向量长度一种衡量，也叫向量的模，常用的是二范数，也就是欧氏空间中的距离。我们这里也都是讨论的二范数，也有像是F范数，定义为矩阵所有元素平方和再开方(很类似向量)，这里不多讨论。

矩阵的范数类似向量，可以理解为是对矩阵的坐标变换能力的衡量。

矩阵二范数的定义为：


其中 是一个向量，也就是一个向量经过矩阵变换后的拉伸。

因此从公式 中可知 。令 ，带入公式  中的分母，我们有：

由此可知不等式可以放缩。
另外：



可以类似压缩。

条件数定义为：



实际上，我们可以通过矩阵的奇异值来衡量放缩能力，上面可以直接得到：





其中 分别为最大最小奇异值。特别的，正定矩阵的奇异值与特征值相等。因此公式  中

JamesB

看完很有感触，谢谢博主[爱]