优化算法（三）——非精确线搜索

Zephus · 发表于 2022-7-19 16:16

如之前讨论过的，线搜索的方式要求计算出的需要保证是下降方向，也就是说它需要满足条件
$f'(x_k;d_k)=\nabla f^T(x_k)d_k<0\\$
然而，通常来讲，下降方向通常有如下的形式，
$d_k=-B_k^{-1}\nabla f(x_k)\\$
其中，是一个对称且非奇异的矩阵。在最速下降中，的值是单位矩阵，在Newton法中，的值是Hessian矩阵 $\nabla^2 f(x_k)$ ，在quasi-Newton法中，的值是每一轮迭代通过low rank所近似出的Hessian矩阵。
因此这一方式所定义的下降方向需要满足条件
$-\nabla f^T(x_k)d_k=-\nabla^T f(x_k)B_k^{-1}\nabla f(x_k)<0\\$

这里考虑的是一般的函数，而当被特定限制为凸函数时，Newton法可以始终满足条件。（在讨论Newton法时会着重分析）

回溯直线搜索（Backtracking line search）

主要是一种非精确的直线搜索方式，只需要沿着射线 $\{x+\rho\Delta x\vert\rho>0\}$ 来近似搜索，来确定步长和下降方向，需要保证函数 $f$ 始终满足要求的递减即可，因此主要的工作量在于考虑适当的步长 $\alpha_k$ 选取，以及下降方向  的确定。
如果使用开始讨论的下降条件  作为这一准则，它显然是不够充分的。
其中，会存在步长的选取，使得数值的下降不够明显。即使是凸函数，步长选择不合适，也可能不收敛。
例如，在求解优化问题 $\min_x f(x)=x^2$ 时，选取步长 $\alpha_k=\frac1{k(k+1)}$ ，下降方向 $d_k=-1$ ，可以得到每轮的迭代点是 $x_k=1+\frac{1}k$ ，它满足条件 $f(x_k+\alpha_kd_k)=1+\frac{1}{k+1}<f(x_k)=1+\frac{1}k$ ，但是它最终只能收敛至 $1$ ，并不能收敛到全局最优值 $0$ 。这说明  这一条件不能使得下降方向满足其相应的收敛条件。
对于不同的步长，会有不同的收敛结果，因此需要选择合适的下降条件，使得满足条件。其中，如果  是下降方向，则可以考虑如下的几个准则。
Armijo conditions

$f(x_k+\alpha d_k)\leq f(x_k)+\rho g_k^Td_k\alpha,~~~~\rho\in(0,1)\\$
如图所示，Armijo条件避免了当  取的足够大时，使得  下降不明显的问题。通常， $\rho$ 取的数值普遍比较小，大致在 $10^{-3}$ 数量级。

Armijo 条件，红色的部分表示这一条件避免的部分

可以看到，当  取值较小的时候，依然有可能使得  的下降不够明显。
Goldstein conditions

因此在Armijo条件的基础上，增加一个条件，使得消除掉当  数值较小时带来的下降不明显的问题。
$f(x_k+\alpha d_k)\leq f(x_k)+\rho \nabla^Tf(x_k)d_k\alpha\\ f(x_k+\alpha d_k)\geq f(x_k)+(1-\rho) \nabla^Tf(x_k)d_k\alpha\\$
其中， $\rho\in(0,\frac{1}2)$ 。

Goldstein 条件，蓝色的部分表示这一条件在Armijo条件的基础上增加的避免部分

图中蓝色和黄色曲线中间部分，是在Goldstein条件的限制之下，可以选择的区间范围。这一条件通常在Newton-type的方法中使用，但是对始终保证Hessian矩阵正定的quasi-Newton法中，适用效果不好。（个人理解，如上图中左侧的蓝色部分，如果保证正定矩阵，与Armijo条件相比，去掉了很大一部分可行区间，包括下降程度很大的点。）
Wolfe conditions

另一种对于较小的  的限制条件，是对于斜率增加限制，
$f(x_k+\alpha d_k)\leq f(x_k)+\rho \nabla^Tf(x_k)d_k\alpha\\ \nabla^T f(x_k+\alpha d_k)d_k\geq \sigma \nabla^Tf(x_k)d_k\\$
其中 $0<\rho<\sigma<1$ ，也即是说明 $f(x_k+\alpha d_k)$ 在  点的斜率不能小于在 $\alpha=0$ 点斜率的 $\sigma$ 倍。这保证了此时选取的  与原点相比，已经存在了一定的下降程度（由于 $\sigma<1$ ）。

Wolfe 条件，和Goldstein条件类似，蓝色的部分是与Armijo条件相比，增加的避免部分

Strong wolfe使得更逼近精确线搜索条件。
$f(x_k+\alpha d_k)\leq f(x_k)+\rho \nabla^Tf(x_k)d_k\alpha\\ |\nabla^T f(x_k+\alpha d_k)d_k|\leq -\sigma \nabla^Tf(x_k)d_k\\$

强 Wolfe条件，对多余的部分增加了限制，使得更逼近最小值

但是在实际操作中，使得  不是足够小的条件不是必须使用，由于目标是需要找到一个合适的  ，只需给定一个下界即可。

它不是凸优化中的内容，不要求函数一定是凸函数

收敛性
Zoutendijk 条件：
假设是 $L-lipschitz$ 连续函数，且具有下界，则有
$\sum_{k=0}^\infty\cos^2\theta_k\|\nabla f(x_k)\|^2<+\infty\\$ ,
其中， $\theta_k$ 是负梯度 $-\nabla f(x_k)$ 和下降方向的夹角，也即
$\cos\theta_k=\frac{-\nabla^T f(x_k)d_k}{\|\nabla f(x_k)\|\|d_k\|}\\$

待写

由于眼前需处理约束算法，因此其他的无约束算法先咕一波，之后每个算法都单独开一篇文章（Newton法、quasi-Newton法、conjugate gradient法，解稀疏矩阵方程的同伦算法、Bregman迭代法）。下一部分从projected gradient开始，然后依次primal-dual，interior point method， ADMM等处理约束问题的方法。

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

优化算法（三）——非精确线搜索

本帖子中包含更多资源