优化算法（二）——最速下降法

Zephus · 发表于 2022-6-24 16:22

首先考虑使得目标函数值下降最快的方式，也即最速下降法（steepest descent）。
定义

由于函数  在点  处的变化率可以由其对应的方向导数表达，
$f'(x_k;d_k)=\lim_{\alpha\rightarrow0}\frac{f(x_k+\alpha d_k)-f(x_k)}{\alpha}=\nabla f^T(x_k)d_k\\$
因此，为了保证函数在  处下降最快，可以将问题转化为优化问题：
$\begin{gather} \min ~~\nabla^Tf(x_k)d_k\\ s.t.~~~~\|d_k\|\leq1\\ \end{gather} \\$
由Cauchy-Schwarz不等式，可以得到，
$|\nabla^T f(x_k)d_k|\leq\|\nabla f(x_k)\|\cdot\|d_k\|\leq\|\nabla f(x_k)\|\\$
然后去掉绝对值符号，可以得到
$\nabla^T f(x_k)d_k\geq-\|\nabla f(x_k)\|\\$
这就说明了最速的下降方向是负梯度方向，这一方向可以使得目标函数的变化率最大， $\arg\min_{\|d\|\leq1}f'(x_k;d_k)=-\frac{\nabla f(x_k)}{\|\nabla f(x_k)\|}\\$
以上的假设是基于Euclidean范数得到的，若采用其他范数，结果可能有部分差异。如使用对称正定矩阵  所度量的范数 $\|\cdot\|_A$ ，最速下降方向则变为
$\arg\min_{\|d\|\leq1}f'(x_k;d_k)=-\frac{A^{-1}\nabla f(x_k)}{\left(\nabla ^Tf(x_k)A^{-1}\nabla f(x_k)\right)^{\frac{1}2}}\\$
收敛性

接下来讨论最速下降法的收敛性。
如之前所说，考虑线性收敛速度 $O(1/k)$ ，目标是寻找一个收敛率 $\rho<1$ ，使得 $\|x_{k+1}-x^\star\|\leq\rho\|x_{k}-x^\star\|$ 成立。
先使用二次函数 $f(x)=\frac{1}2x^TAx+b^Tx$ 作为例子（  是一个正定矩阵），对于固定的step size，在迭代最终收敛时，满足
$x_{k+1}-x^\star=(I-\alpha A)(x_k-x^\star)\\$
因此，需要相应的选取合适的步长  ，从而保证 $\|x_{k+1}-x^\star\|$ 相较 $\|x_k-x^\star\|$ 一定是在收缩的。
首先计算出  的全部特征值，分三种情况进行讨论。

矩阵的全部特征值都非负，也即它的最小特征值 $1-\alpha\lambda_{max}\geq0$ 。因此有 $1/\lambda_{max}\geq\alpha$ ，进而得到 $\|I-\alpha A\|=1-\alpha\lambda_{min}\geq\frac{\lambda_{max}-\lambda_{min}}{\lambda_{max}}$ 。（矩阵的norm是它的最大特征值）
完全类似，矩阵的全部特征值都非正，也即它的最大特征值 $1-\alpha\lambda_{min}\leq0$ ，可得 $1/\lambda_{min}\leq\alpha$ 。同样地， $\|I-\alpha A\|=\alpha\lambda_{max}-1\geq\frac{\lambda_{max}-\lambda_{min}}{\lambda_{min}}$ 。
对于矩阵特征值有正有负的情况， $\|I-\alpha A\|=\max\{|1-\alpha\lambda_{max}|,|1-\alpha\lambda_{min}|\}$ ，为了使得它最小，令 $|1-\alpha\lambda_{max}|=|1-\alpha\lambda_{min}|$ ，可以解出，因此。

三种情况相比，显然最优选择为，进而可以计算得到 $\rho=\frac{\lambda_{max}-\lambda_{min}}{\lambda_{max}+\lambda_{min}}$ 。
因此
$\|x_{k+1}-x^\star\|=\rho^k\|x_0-x^\star\|\\$
由于 $0<\rho<1$ ，当 $k\rightarrow\infty$ 时，  将会收敛至 $x^\star$ 。因此要想确定一个不精确的bound，至多需要经过
$\frac{\log(\|x_0-x^\star\|/\epsilon)}{\log(1/\rho)}\\$
次迭代即可实现 $\epsilon$ 的误差。
缺陷
由于在每一步都要相应选取在 $d_k$ 方向上的极小点，因此 $f(x_k+\alpha d_k)$ 对step size  的导数应该也是 $0$ 。进而可以得到 $\nabla f(x_k+\alpha d_k)d_k=0$ ，由最速下降的定义，可以判定得到 $\nabla^T f(x_{k+1})\nabla f(x_k)=0$ 。
因此相邻两个搜索方向是正交的，路径是呈“之”字形不断下降，这会大幅影响收敛速度。
此外，当  的Hessian矩阵是奇异的或不存在时，若结果能收敛，它的收敛率也会大于线性收敛率。
和特征值之间的关系：

在二次函数中，目标函数的等值面可以被视为一个椭球面，由于收敛率为  ，最大最小特征值就对应了最长轴和最短轴的长度。当两特征值相差越大，椭球面越扁，这会使得搜索方向沿着扁平且较长的方向不断搜索，这时候它们会在两个相互正交的方向上交替迭代，如果没有一个能够恰好指向最小值的方向，迭代速度会比较缓慢。
从数值角度分析， $\lambda_{max}/\lambda_{min}$ 被称为条件数，当它越接近于 $1$ 时，越靠近 $0$ ，接近超线性的收敛速度。而反之，如果条件数越大，越靠近 $1$ ，收敛速度会越慢。
同样地，对于一般的凸函数  ，在近似收敛点的位置，目标函数也可以粗略地视为一个椭球面，只需要计算它的Hessian矩阵的最大最小特征值，可以以同样的方式理解。
对于非凸函数，需要找到它Hessian矩阵的上下界，也即一组参数 $(m,M)$ ，来替代最大最小特征值的的位置， $mI\preceq\nabla^2f(x)\preceq MI$ 。
所以说，尽管最速下降法每轮都可以取到最快的下降方向，但是从全局上讲，它不一定能够使得找到总体上更靠近最优值，会走一定的弯路，因此不是最快的收敛方法。
下一步会继续讨论Inexact的线搜索方式。

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