优化算法（三）——非精确线搜索
如之前讨论过的，线搜索的方式要求计算出的需要保证是下降方向，也就是说它需要满足条件https://www.zhihu.com/equation?tex=f%27%28x_k%3Bd_k%29%3D%5Cnabla+f%5ET%28x_k%29d_k%3C0%5C%5C
然而，通常来讲，下降方向通常有如下的形式，
https://www.zhihu.com/equation?tex=d_k%3D-B_k%5E%7B-1%7D%5Cnabla+f%28x_k%29%5C%5C
其中，是一个对称且非奇异的矩阵。在最速下降中，的值是单位矩阵，在Newton法中，的值是Hessian矩阵 https://www.zhihu.com/equation?tex=%5Cnabla%5E2+f%28x_k%29 ，在quasi-Newton法中，的值是每一轮迭代通过low rank所近似出的Hessian矩阵。
因此这一方式所定义的下降方向需要满足条件
https://www.zhihu.com/equation?tex=-%5Cnabla+f%5ET%28x_k%29d_k%3D-%5Cnabla%5ET+f%28x_k%29B_k%5E%7B-1%7D%5Cnabla+f%28x_k%29%3C0%5C%5C
[*]这里考虑的是一般的函数，而当被特定限制为凸函数时，Newton法可以始终满足条件。（在讨论Newton法时会着重分析）
回溯直线搜索（Backtracking line search）
主要是一种非精确的直线搜索方式，只需要沿着射线 https://www.zhihu.com/equation?tex=%5C%7Bx%2B%5Crho%5CDelta+x%5Cvert%5Crho%3E0%5C%7D 来近似搜索，来确定步长和下降方向，需要保证函数 https://www.zhihu.com/equation?tex=f 始终满足要求的递减即可，因此主要的工作量在于考虑适当的步长 https://www.zhihu.com/equation?tex=%5Calpha_k 选取，以及下降方向的确定。
如果使用开始讨论的下降条件作为这一准则，它显然是不够充分的。
其中，会存在步长的选取，使得数值的下降不够明显。即使是凸函数，步长选择不合适，也可能不收敛。
例如，在求解优化问题 https://www.zhihu.com/equation?tex=%5Cmin_x+f%28x%29%3Dx%5E2 时，选取步长 https://www.zhihu.com/equation?tex=%5Calpha_k%3D%5Cfrac1%7Bk%28k%2B1%29%7D ，下降方向 https://www.zhihu.com/equation?tex=d_k%3D-1 ，可以得到每轮的迭代点是 https://www.zhihu.com/equation?tex=x_k%3D1%2B%5Cfrac%7B1%7Dk ，它满足条件 https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha_kd_k%29%3D1%2B%5Cfrac%7B1%7D%7Bk%2B1%7D%3Cf%28x_k%29%3D1%2B%5Cfrac%7B1%7Dk ，但是它最终只能收敛至 https://www.zhihu.com/equation?tex=1 ，并不能收敛到全局最优值 https://www.zhihu.com/equation?tex=0 。这说明这一条件不能使得下降方向满足其相应的收敛条件。
对于不同的步长，会有不同的收敛结果，因此需要选择合适的下降条件，使得满足条件。其中，如果是下降方向，则可以考虑如下的几个准则。
Armijo conditions
https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29%5Cleq+f%28x_k%29%2B%5Crho+g_k%5ETd_k%5Calpha%2C~~~~%5Crho%5Cin%280%2C1%29%5C%5C
如图所示，Armijo条件避免了当取的足够大时，使得下降不明显的问题。通常， https://www.zhihu.com/equation?tex=%5Crho 取的数值普遍比较小，大致在 https://www.zhihu.com/equation?tex=10%5E%7B-3%7D 数量级。
Armijo 条件，红色的部分表示这一条件避免的部分
可以看到，当取值较小的时候，依然有可能使得的下降不够明显。
Goldstein conditions
因此在Armijo条件的基础上，增加一个条件，使得消除掉当数值较小时带来的下降不明显的问题。
https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29%5Cleq+f%28x_k%29%2B%5Crho+%5Cnabla%5ETf%28x_k%29d_k%5Calpha%5C%5C+f%28x_k%2B%5Calpha+d_k%29%5Cgeq+f%28x_k%29%2B%281-%5Crho%29+%5Cnabla%5ETf%28x_k%29d_k%5Calpha%5C%5C
其中， https://www.zhihu.com/equation?tex=%5Crho%5Cin%280%2C%5Cfrac%7B1%7D2%29 。
Goldstein 条件，蓝色的部分表示这一条件在Armijo条件的基础上增加的避免部分
图中蓝色和黄色曲线中间部分，是在Goldstein条件的限制之下，可以选择的区间范围。这一条件通常在Newton-type的方法中使用，但是对始终保证Hessian矩阵正定的quasi-Newton法中，适用效果不好。（个人理解，如上图中左侧的蓝色部分，如果保证正定矩阵，与Armijo条件相比，去掉了很大一部分可行区间，包括下降程度很大的点。）
Wolfe conditions
另一种对于较小的的限制条件，是对于斜率增加限制，
https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29%5Cleq+f%28x_k%29%2B%5Crho+%5Cnabla%5ETf%28x_k%29d_k%5Calpha%5C%5C+%5Cnabla%5ET+f%28x_k%2B%5Calpha+d_k%29d_k%5Cgeq+%5Csigma+%5Cnabla%5ETf%28x_k%29d_k%5C%5C
其中 https://www.zhihu.com/equation?tex=0%3C%5Crho%3C%5Csigma%3C1 ，也即是说明 https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29 在点的斜率不能小于在 https://www.zhihu.com/equation?tex=%5Calpha%3D0 点斜率的 https://www.zhihu.com/equation?tex=%5Csigma 倍。这保证了此时选取的与原点相比，已经存在了一定的下降程度（由于 https://www.zhihu.com/equation?tex=%5Csigma%3C1 ）。
Wolfe 条件，和Goldstein条件类似，蓝色的部分是与Armijo条件相比，增加的避免部分
Strong wolfe使得更逼近精确线搜索条件。
https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29%5Cleq+f%28x_k%29%2B%5Crho+%5Cnabla%5ETf%28x_k%29d_k%5Calpha%5C%5C+%7C%5Cnabla%5ET+f%28x_k%2B%5Calpha+d_k%29d_k%7C%5Cleq+-%5Csigma+%5Cnabla%5ETf%28x_k%29d_k%5C%5C
强 Wolfe条件，对多余的部分增加了限制，使得更逼近最小值
但是在实际操作中，使得不是足够小的条件不是必须使用，由于目标是需要找到一个合适的，只需给定一个下界即可。
[*]它不是凸优化中的内容，不要求函数一定是凸函数
收敛性
Zoutendijk 条件：
假设是 https://www.zhihu.com/equation?tex=L-lipschitz 连续函数，且具有下界，则有
https://www.zhihu.com/equation?tex=%5Csum_%7Bk%3D0%7D%5E%5Cinfty%5Ccos%5E2%5Ctheta_k%5C%7C%5Cnabla+f%28x_k%29%5C%7C%5E2%3C%2B%5Cinfty%5C%5C ,
其中， https://www.zhihu.com/equation?tex=%5Ctheta_k 是负梯度 https://www.zhihu.com/equation?tex=-%5Cnabla+f%28x_k%29 和下降方向的夹角，也即
https://www.zhihu.com/equation?tex=%5Ccos%5Ctheta_k%3D%5Cfrac%7B-%5Cnabla%5ET+f%28x_k%29d_k%7D%7B%5C%7C%5Cnabla+f%28x_k%29%5C%7C%5C%7Cd_k%5C%7C%7D%5C%5C
待写
由于眼前需处理约束算法，因此其他的无约束算法先咕一波，之后每个算法都单独开一篇文章（Newton法、quasi-Newton法、conjugate gradient法，解稀疏矩阵方程的同伦算法、Bregman迭代法）。下一部分从projected gradient开始，然后依次primal-dual，interior point method， ADMM等处理约束问题的方法。
页:
[1]