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

rustum · 发表于 2022-5-10 13:26

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

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

$\lim_{k\rightarrow \infty}x_k=x^*$

或者说

$\lim_{k\rightarrow \infty}f(x_k)=f(x^*)$

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

$\lim_{k\rightarrow \infty}\|\nabla f(x_k)\|=\|\nabla f(x^*)\|=0 \qquad (1)$

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

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

$\lim_{k\rightarrow \infty} \cos^2\theta_k\|\nabla f_k\|^2=0 \qquad (2)$

其中 $\cos\theta_k=\frac{-\nabla f_k^T p_k}{\|\nabla f_k\| \|p_k\|}$ ，为  与  的夹角余弦。
Lipschitz连续

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

$\|f(x)-f(\hat{x})\|\leq L\|x-\hat{x}\|, \qquad\forall x,\hat{x}$

其实变换成这种形式， $\frac{\|f(x)-f(\hat{x})\|}{\|x-\hat{x}\|}\leq L$ ，就是说  的梯度不能有无穷大的地方，总之是有个上界的。

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

$\|\nabla f(x)- \nabla f(\hat{x})\|\leq L\|x-\hat{x}\|\qquad (3)$
前提条件

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

在开区间  上，记 $x_{k+1}=x_k+\alpha_k p_k$ ，我们有以下几点要求，

满足Lipschitz连续，即公式 $(3)$
是下降方向，即 $\nabla f_k^Tp_k<0\qquad(4)$
$\alpha_k$ 满足wolfe条件，即:
$f_{k+1}<f_k+c_1\alpha_k\nabla f_k^Tp_k\qquad (5)$

$\nabla f_{k+1}^Tp_k\geq c_2\nabla f_k^T p_k \qquad(6)$

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

首先根据公式 $(6)$ 有：

$(\nabla f_{k+1}-\nabla f_k)^Tp_k\geq(c_2-1)(\nabla f_k^T p_k) \qquad (7)$

又根据公式(3)，有：

$\|\nabla f_{k+1}-\nabla f_k\|\leq \alpha_k L \|p_k\|$

两边同时乘上 $\|p_k\|$ ：

$\|\nabla f_{k+1}-\nabla f_k\|\|p_k\|\leq \alpha_k L \|p_k\|^2$

根据向量内积知 $(\nabla f_{k+1}-\nabla f_k)^Tp_k\leq\|\nabla f_{k+1}-\nabla f_k\|\|p_k\|$ ，则有：

$(\nabla f_{k+1}-\nabla f_k)^Tp_k\leq \alpha_k L \|p_k\|^2 \qquad (8)$

联立公式 $(7,8)$ 可知：

$\alpha_k \geq \frac{c_2-1}{L}\frac{\nabla f_k^T p_k}{\|p_k\|^2} \qquad (9)$

又因为公式  中 $c_1 \nabla f_k^Tp_k<0$ ，所以将公式 $(9)$ 代入  ，有：

$f_{k+1}\leq f_k+c_1\frac{c_2-1}{L}\frac{(\nabla f_k^Tp_k)^2}{\|p_k\|^2} \qquad (10)$

再将 $\cos \theta_k$ 带入：

$f_{k+1}\leq f_k+c_1\frac{c_2-1}{L} \cos^2\theta_k\|\nabla f_k\|^2$

其中，记 $c=c_1\frac{1-c_2}{L}>0$ ，带入：

$f_k -f_{k+1}\geq c\cos^2\theta_k\|\nabla f_k\|^2 \qquad (11)$

将公式 $(11)$ 左右两边累加则有：

$f_0-f_{k+1}\geq c\Sigma_{j=0}^{k}\cos^2\theta_j\|\nabla f_j\|^2$

  是有下界的，  趋近无穷大时， $f_0-f_{k}<\infty$ ，所以

$\Sigma_{k=0}^{\infty}\cos^2\theta_k\|\nabla f_k\|^2<\infty$

所以证得Zoutendijk条件：


收敛性证明

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



更进一步，如果能够证明

$\cos\theta_k \geq \delta >0, \forall k \qquad(12)$

那么显然要想仍然满足Zoutendijk条件，则只能要求 $\lim_{k\rightarrow \infty}\|\nabla f_k\|=0$ ，从而证明了收敛性。

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

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

分别来看一下，对于最速下降方向， $p_k = -\nabla f_k$ ，天然的 $\cos\theta_k=1$ ，则自然满足收敛性。

对于牛顿方向和拟牛顿方向，我们统一记 $p_k = -B_k^{-1}\nabla f_k$ ，其中  是牛顿方向中的黑塞矩阵，拟牛顿方向中构建的近似黑塞矩阵，我们要求  是正定的，并且有特征值 $0<\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n$ ，则有：

$\cos\theta_k = \frac{-\nabla f_k^T p_k}{\|\nabla f_k\| \|p_k\|} =\frac{\nabla f_k^T B_k^{-1} \nabla f_k}{\|\nabla f_k\| \|B_k^{-1}\nabla f_k\|}$

$\geq \frac{\frac{1}{\lambda_n}\|\nabla f_k\|^2}{\|\nabla f_k\| \|B_k^{-1}\nabla f_k\|} \geq \frac{\frac{1}{\lambda_n}\|\nabla f_k\|^2}{\|B_k^{-1}\|\|\nabla f_k\|^2} =\frac{\frac{1}{\lambda_n}\|\nabla f_k\|^2}{\frac{1}{\lambda_1}\|\nabla f_k\|^2} =\frac{\lambda_1}{\lambda_n} =\frac{1}{\kappa(B_k)} \qquad (13)$

所以，只要  的条件数满足 $\frac{1}{\kappa(B_k)}\geq \delta, \forall k$ ，也就是:
$\kappa(B_k)=\|B_k\|\|B_k^{-1}\|\leq M, \forall k$
那就满足了收敛性，其中 $M$ 为某一常数。

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

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

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

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

矩阵二范数的定义为：

$\|B\|=\max_x\frac{\|Ax\|}{\|x\|} \qquad(14)$
其中 $x$ 是一个向量，也就是一个向量经过矩阵变换后的拉伸。

因此从公式 $(14)$ 中可知 $\|B\|\geq\frac{\|Ax\|}{\|x\|},\forall x$ 。令 $B=B_{k}^{-1},x=\nabla f_k$ ，带入公式  中的分母，我们有：
$\|B_k^{-1}\nabla f_k\|\leq\|B_k^{-1}\|\|\nabla f_k\|$
由此可知不等式可以放缩。
另外：

$\|B^{-1}\|=\frac{1}{\min_x\frac{\|Ax\|}{\|x\|}}$

可以类似压缩。

条件数定义为：

$\kappa(B)=\|B\|\|B^{-1}\|$

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

$\|B\|=\sigma_{\max}$

$\|B^{-1}\|=\frac{1}{\sigma_{\min}}$

其中 $\sigma_{\max},\sigma_{\min}$ 分别为最大最小奇异值。特别的，正定矩阵的奇异值与特征值相等。因此公式  中 $\|B_k^{-1}\|=\frac{1}{\lambda_1}$

JamesB · 发表于 2022-5-10 13:26

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源