线搜索理论满足以下模型，其中 ak$a_k$ 为步长，pk$p_k$ 为搜索方向：

为保证 pk$p_k$ 在目标函数 f$f$ 的下降方向，需要满足 pTk∇fk<0$p_k^T\mathrm{\nabla }{f}_k<0$，其一般模型为：

其中当 Bk$B_k$ 对称满秩且正定时，能够保证 pk$p_k$ 指向 f$f$ 下降方向

• steepest descent method: Bk=I$B_k=I$（单位矩阵）
• Newton’s method: Bk=∇2f(xk)$B_k={\mathrm{\nabla }}^{2}f(x_k)$（Hessian 矩阵）
• Quasi-Newton method： Bk→$B_k\to$ Hessian 估计矩阵（SR1 或 BFGS 方法等）

上述内容可以参考 我的上一篇笔记。

这篇笔记对 αk${\alpha }_k$ 的选择以及 收敛率（rate of convergence）做深入讨论。

---

1. 步长 Step Length

对于步长的选择，主要基于两个权衡：

• αk${\alpha }_k$ 能够实现 f$f$ 的大幅下降
• 不能花太多时间做决定

一般最为理想的方法是取下述 ϕ(.)$\varphi (.)$ 的最小值：

但通常此求解过程非常复杂，无法实现，故退而希望 αk${\alpha }_k$ 满足以下两个条件：

• 当前 αk${\alpha }_k$ 推进的部分在 f$f$ 的 pk$p_k$ 方向的下降区间内
• αk${\alpha }_k$ 较长，可以实现更有效率的下降

故引入以下几种条件。

1.2 Wolfe 条件 The Wolfe Conditions

Wolfe 条件其中包括两条条件：

• Armijo Condition：保证 αk${\alpha }_k$ 在 pk$p_k$ 方向上 f$f$ 的下降区间内
  
  ϕ(α)=f(xk+αpk)l(α)=f(xk)+c1α∇fTkpk,c1∈(0,1)ϕ(α)≤l(α)$$\begin{gathered} \varphi (\alpha )=f(x_k+\alpha p_k) \\ l(\alpha )=f(x_k)+c_1\alpha \mathrm{\nabla }{f}_k^T{p}_k,c_1\in (0,1) \\ \varphi (\alpha )\le l(\alpha ) \end{gathered}$$
  
  其中 c1$c_1$ 的典型值为 c1=10−4$c_1={10}^{-4}$
• 曲率条件：保证 αk${\alpha }_k$ 在上述条件的基础上足够大，使得算法有效率

其中 c2$c_2$ 的典型值如下：

• Newton / Quasi-Newton: c2=0.9$c_2=0.9$
• Nonlinear conjugate gradient method: c2=0.1$c_2=0.1$

综上所述，完整的 Wolfe Conditions 的叙述是：

严格 Wolfe Conditions 的叙述是：

其较于非严格 Wolfe Conditions 加上了 ϕ′(αk)${\varphi }^{\prime }({\alpha }_k)$ 必须为正的限定。

且需要注意的是，对于所有平滑且取值有界的目标函数 f$f$ 都能找到满足 （strong） Wolfe Conditions 的步长 αk${\alpha }_k$ （证明略）
故可以看出来 Wolfe Conditions 具有广义尺度不变性，即将 f$f$ 乘以一个常数或将 f$f$ 进行尺度变换不会改变 Wolfe Conditions 寻找的结果

1.2 Goldstein 条件 The Goldstein Conditions

其完整表达为：

前一个不等式控制步长长度使其不至于太短（以致效率过低），后一个不等值控制步长使其不至于超出 f$f$ 在 pk$p_k$ 方向上的下降区间

Goldstein 条件常用于 Newton type 算法，而不太使用于 Quasi-Newton type 算法

1.3 回溯算法 Backtracking

根据上述两个条件，可以看出仅限定 αk${\alpha }_k$ 在 f$f$ 的 pk$p_k$ 方向上的下降区间内是不足以促成一个成功的算法的，还需要对其收敛效率进行规定，故上述条件都有两个限定。
然而使用回溯算法便可以省略有关效率的那个限定条件，其算法流程如下：

Choose α¯¯¯>0,ρ∈(0,1),c∈(0,1)$\overline{\alpha }>0,\rho \in (0,1),c\in (0,1)$; Set α←α¯¯¯$\alpha \leftarrow \overline{\alpha }$
repeat until f(xk+αpk)≤f(xk)+cα∇fTkpk$f(x_k+\alpha p_k)\le f(x_k)+c\alpha \mathrm{\nabla }{f}_k^T{p}_k$
α←ρα$\alpha \leftarrow \rho \alpha$
end(repeat)
Terminate with αk=α${\alpha }_k=\alpha$

其中 α¯¯¯$\overline{\alpha }$ 的初值取法如下：

• Newton and Quasi-Newton: α¯¯¯=1$\overline{\alpha }=1$
• 其他算法的 α¯¯¯$\overline{\alpha }$ 的取值各不相同

其中的收缩系数 ρ$\rho$ 可在每步迭代后进行变动，只要满足 0<ρlo<ρhi<1$0<{\rho }_{lo}<{\rho }_{hi}<1$ 即可

这种算法很适合 Newton，但是不那么适用于 Quasi-Newton 与 Conjugate gradient 算法

2. 线搜索算法的收敛性

可证明，其他算法和 steepest descent algorithm 一样可以具有全局收敛性（虽然实现收敛的路径不同）

证明略

3. 收敛率 Rate of convergence

一个好的算法，需要满足下面两个条件：

• 严格的全局收敛保证
• 收敛速度快

但是这两个需要相互权衡，譬如: steepest descent method 具有极佳的全局收敛保证，但收敛速度慢；而纯 Newton method 收敛速度快，但有时可能达不到全局收敛。
故为了检验算法的全局收敛性，需要引入一个量“收敛率”。

在正式讨论各类算法的收敛率之前，首先引入另外两个小概念，方便后面叙述：
有两个迭代点 xk+1,xk$x_{k+1},x_k$，最优收敛点 x∗$x^{\ast }$，若存在实数 q>0$q>0$满足：

若：

• q∈(0,1)$q\in (0,1)$，线性收敛
• q=0$q=0$，超线性收敛

3.1 steepest descent 的收敛率

首先我们假设一个典型的二次目标函数：

其中 Q 对称正定，其最佳收敛点为 x∗$x^{\ast }$，即有 ∇f(x∗)=0$\mathrm{\nabla }f(x^{\ast })=0$
在此算法中 pk=−∇fk$p_k=-\mathrm{\nabla }{f}_k$，设步长为 αk${\alpha }_k$，则有：

使得上式等于 0，可以得到步长推断式：

这样就得到了迭代方程：

使用下式量化收敛率，即计算所得值和理想值之间的差距：

根据上面的讨论可以严格推导 steepest descent method 的收敛率推导式：

然而，这个推倒式太难计算了，所以给出了一些计算的替代方案：

• 当 f$f$ 为严格二次凸函数时：
  定义不等式：
  
  ||xk+1−x∗||2Q≤(λn−λ1λn+λ1)2||xk−x∗||2Q$$||x_{k+1}-x^{\ast }|{|}_Q^2\le (\frac{{\lambda }_n-{\lambda }_1}{{\lambda }_n+{\lambda }_1}{)}^2||x_k-x^{\ast }|{|}_Q^2$$
  
  其中 0<λ1≤λ2≤...≤λn$0<{\lambda }_1\le {\lambda }_2\le ...\le {\lambda }_n$ 是 Q$Q$ 的特征值
  可以看出，当所有特征值相等时（即 Q=I$Q=I$ 时），∇fk$\mathrm{\nabla }{f}_k$ 的形状是圆形，且 pk$p_k$ 直指全局收敛点；随着 κ(Q)=λnλ1$\kappa (Q)=\frac{{\lambda }_n}{{\lambda }_1}$ 的增大，其轮廓越来越椭圆，且路径越来越曲折。

• 当 f$f$ 仅仅是二次连续可微：
  
  r∈(λn−λ1λn+λ1,1)f(xk+1)−f(x∗)≤r2[f(xk)−f(x∗)]$$\begin{gathered} r\in (\frac{{\lambda }_n-{\lambda }_1}{{\lambda }_n+{\lambda }_1},1) \\ f(x_{k+1})-f(x^{\ast })\le r^2[f(x_k)-f(x^{\ast })] \end{gathered}$$

这显示出 steepest descent 算法在某些情况下（通常在 κ(Q)$\kappa (Q)$ 很大的情况下），可能会非常非常慢。

3.2 Newton’s method

其 pk$p_k$ 遵循下式：

但需要注意的是，在上式中有一个限定条件—— ∇2fk${\mathrm{\nabla }}^2{f}_k$ 必须是正定的，才能保证 pk$p_k$ 指向下降方向。

假定 f$f$ 二次可微，那么其 Hessian 矩阵 ∇2f(x)${\mathrm{\nabla }}^{2}f(x)$ Lipschitz 连续，x* 是最佳点（在 x* 附近开区间内 ∇2f${\mathrm{\nabla }}^{2}f$ 连续且 ∇f(x∗)=0$\mathrm{\nabla }f(x^{\ast })=0$ 且 ∇2f(x∗)${\mathrm{\nabla }}^{2}f(x^{\ast })$ 正定）。迭代式为 xk+1=xk+pk$x_{k+1}=x_k+p_k$，且 pk$p_k$ 的方法为 Newton 法，则：

• 如果初始点 x0$x_0$ 距离 x∗$x^{\ast }$ 足够近，那么序列在 x∗$x^{\ast }$ 处收敛
• 其 {xk$x_k$} 的收敛率是二次的
• 梯度序列 {||∇fk||$||\mathrm{\nabla }{f}_k||$} 二次收敛于 0

上述证明略。

但上面的定量非常棒棒，主要是能够递推出下列优厚性质：
当使用 Newton’s method 递推得到 pk$p_k$ 时：

• 对于所有 k，αk${\alpha }_k$ 都可通过 Wolfe/Goldstein conditions 的检验（即对于 Newton’s method 可以直接使用 αk${\alpha }_k$ 作为步长）
• 如果还满足 limk→∞||∇fk+∇2fkpk||||pk||=0$\underset{k\to \mathrm{\infty }}{lim}\frac{||\mathrm{\nabla }{f}_k+{\mathrm{\nabla }}^2{f}_k{p}_k||}{||p_k||}=0$，那么对于所有 k 来说，||x−x∗||2Q=0$||x-x^{\ast }|{|}_Q^2=0$
• 利用线搜索法时，αk=1${\alpha }_k=1$ 对于所有 k 局部二次收敛

3.3 Quasi-Newton method

其 pk$p_k$ 推导式为：

其中 Bk$B_k$ 的推导方法有 SR1，BFGS 等。其步长类似 Newton’s method， 先初定为 α=1$\alpha =1$，如果其满足 Wolfe conditions 那么就接受这个初定值。

假定 f:Rn→R$f:R^n\to R$ 中二次连续可微，迭代方式为 xk+1=xk+αkpk$x_{k+1}=x_k+{\alpha }_k{p}_k$，其中保证 pk$p_k$ 指向下降方向并且 αk${\alpha }_k$ 满足 Wolfe conditions(c1≤0.5$c_1\le 0.5$)。如果序列 xk$x_k$ 收敛于 x∗$x^{\ast }$，即 ∇f(x∗)=0$\mathrm{\nabla }f(x^{\ast })=0$ 且 ∇2f(x∗)${\mathrm{\nabla }}^{2}f(x^{\ast })$ 正定，这时如果寻找方向满足：

那么：

• 对于大于指定值 k0$k_0$ 的所有 k 来说，αk=1${\alpha }_k=1$ 全部可行
• 如果 αk=1${\alpha }_k=1$，那么对于所有 k>k0$k>k_0$，xk$x_k$ 超线性收敛于 x∗$x^{\ast }$

另外需要注意的是：

是 Quasi-Newton 超线性收敛的充要条件（当 Bk$B_k$ 不收敛于 ∇2f(x∗)${\mathrm{\nabla }}^{2}f(x^{\ast })$ 时也行，因为 Bk$B_k$ 会随 pk$p_k$ 的迭代越来越靠近 ∇2fk${\mathrm{\nabla }}^2{f}_k$）（证明略）