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

Zephus

如之前讨论过的，线搜索的方式要求计算出的  需要保证是下降方向，也就是说它需要满足条件

然而，通常来讲，下降方向通常有如下的形式，

其中，  是一个对称且非奇异的矩阵。在最速下降中，  的值是单位矩阵，在Newton法中，  的值是Hessian矩阵 ，在quasi-Newton法中，  的值是每一轮迭代通过low rank所近似出的Hessian矩阵。
因此这一方式所定义的下降方向需要满足条件

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

回溯直线搜索（Backtracking line search）

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


如图所示，Armijo条件避免了当  取的足够大时，使得  下降不明显的问题。通常， 取的数值普遍比较小，大致在 数量级。



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

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

因此在Armijo条件的基础上，增加一个条件，使得消除掉当  数值较小时带来的下降不明显的问题。

其中， 。



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


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

另一种对于较小的  的限制条件，是对于斜率增加限制，

其中 ，也即是说明 在  点的斜率不能小于在 点斜率的 倍。这保证了此时选取的  与原点相比，已经存在了一定的下降程度（由于 ）。



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

Strong wolfe使得更逼近精确线搜索条件。




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

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

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

收敛性
Zoutendijk 条件：
假设  是 连续函数，且具有下界，则有
,
其中， 是负梯度 和下降方向  的夹角，也即


待写

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