线搜索基本概述

在每一次线搜索过程中需要计算一个搜索方向 $p_{k}$ 和在方向上前进的步长 $\alpha_{k}$ .

$x_{k+1}=x_{k}+\alpha_{k} p_{k}$

大多数线搜索需要 $p_{k}$ 作为下降方向： $p^{T} \nabla f_{k} < 0$ 来让目标函数 $f$ 沿着方向下降，在前面一章讨论过，通常搜索方向的通式为：

$p_{k}=-B_{k}^{-1} \nabla f_{k}$

$B_{k}$ 为对称且非奇异矩阵，在最速下降法中， $B_{k}$ 为单位矩阵 $I$ (identity matrix), 在牛顿法中， $B_{k}$ 为Hessian matrix $\nabla^{2} f\left(x_k\right)$ . 在拟牛顿法中， $B_{k}$ 为Hessian matrix的近似，并且在每一次迭代中用mean of low-rank formula更新。当 $p_{k}$ 如上定义后且 $B_{k}$ 是正定的，

$p_{k}^{T} \nabla f_{k}=-\nabla f_{k}^{T} B_{k}^{-1} \nabla f_{k}<0$

在本章中，我们主要讨论如何选择 $\alpha_{k}$ 和 $p_{k}$ 来提高算法的收敛性。我们同样会讨论以上各种方法的收敛率(rate of convergence)。

Step length 步长

通常在选择步长 $\alpha_{k}$ 的过程中我们都面临权衡情况(tradeoff), 我们希望 $\alpha_{k}$ 能够使目标函数 $f$ 大量下降的同时又不浪费过多时间。一个理想的情况是作为一个单变量函数的全局最优，如

$\phi(\alpha)=f\left(x_{k}+\alpha p_{k}\right), \quad \alpha>0$

但是通常这个过程的时间成本过高，在确定最终的全局优化过程中总需要对目标函数 $f$ 和梯度 $\nabla f$ 的大量评估。一个较为实用的方法就是使用非精确搜索(Inexact line search)。

线搜索在达到以下两点时可以结束：1. 包围阶段可以找到包含所需步长的间隔； 2.对分(bisection)或插值(interpolation)阶段会在此间隔内计算出良好的步长。一个成熟的线搜索算法通常非常复杂。

Termination conditions/Sufficient decrease conditon 终止条件和充分下降条件

Armijo condition/ Sufficient decrease condition

$f\left(x_{k}+\alpha p_{k}\right) \leq f\left(x_{k}\right)+c_{1} \alpha \nabla f_{k}^{T} p_{k}, \space c_{1} \in(0,1)$

the reduction in $f$ should be proportional to both the step length $\alpha_{k}$ and the directional derivative $\nabla f_{k}^{T} p_{k}$ .

Usually,

$\phi(\alpha)=f\left(x_{k}+\alpha p_{k}\right)$

Curvature condition

$\nabla f\left(x_{k}+\alpha_{k} p_{k}\right)^{T} p_{k} \geq c_{2} \nabla f_{k}^{T} p_{k} \space ,\quad c_{2} \in\left(c_{1}, 1\right)$

其中， $c_{1}$ 来自上个公式，本公式左边即是 $\phi^{\prime}\left(\alpha_{k}\right)$ 并且公式右边就是系数 $c_{2}$ 乘以 $\phi^{\prime}\left(0\right)$ 。公式右边为负数，所以通过改变斜率来使得公式左边接近0或者大于0。同时，如果 $\phi^{\prime}\left(\alpha_{k}\right)$ 仅仅略小于0甚至是正数，那就标志着对于函数 $f$ 而言在此方向不能有更多的下降，此时线搜索终结。

当搜索方向选择为牛顿或者拟牛顿方向的时候， $c_{2}$ 通常赋值0.9；当选择为非线性共轭梯度方法时， $c_{2}$ 通常赋值0.1

Wolfe Conditions

Armijo condition + Curvature condition

$\begin{aligned}f\left(x_{k}+\alpha_{k} p_{k}\right) & \leq f\left(x_{k}\right)+c_{1} \alpha_{k} \nabla f_{k}^{T} p_{k} \space \space \space \space Armijo\\\nabla f\left(x_{k}+\alpha_{k} p_{k}\right)^{T} p_{k} & \geq c_{2} \nabla f_{k}^{T} p_{k}, \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space Curvature\\ 0<c_{1}<c_{2}<1\end{aligned}$

在一般Wolfe 条件下，可能出现满足以上两式但并不非常靠近函数最小值的情况。于是强Wolfe (Strong Wolfe Conditions )条件为

$\begin{aligned}f\left(x_{k}+\alpha_{k} p_{k}\right) & \leq f\left(x_{k}\right)+c_{1} \alpha_{k} \nabla f_{k}^{T} p_{k} \space \space \space \space Armijo\\\left|\nabla f\left(x_{k}+\alpha_{k} p_{k}\right)^{T} p_{k}\right| & \leq c_{2}\left|\nabla f_{k}^{T} p_{k}\right|, \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space Curvature\\ 0<c_{1}<c_{2}<1\end{aligned}$

此时我们限制 $\phi^{\prime}\left(\alpha_{k}\right)$ not to be too positive，通过此方法将那些远离 $\phi$ 驻点(Stationary point)的值剔除。

Wolfe condition proof

定理:假设目标函数f是一个连续可导(Continuously differentiable)的，并且在 $x_{k}$ 处的搜索方向（下降方向）为 $p_{k}$ 在射线 $\left\{x_{k}+\alpha p_{k} \mid \alpha>0\right\}$ 的情况里 $f$ 是有边界的，则如果存在 $0<c_{1}<c_{2}<1$ ，那么也存在步长 $\alpha$ 满足 Wolfe conditions 和 Strong Wolfe Conditions.

Proof：对于所有步长 $\alpha$ >0 而言， $\phi(\alpha)=f\left(x_{k}+\alpha p_{k}\right)$ 是有下界的(Bounded below)，并且在 $0< c_{1}< 1$ 情况下，线 $l(\alpha)=f\left(x_{k}\right)+\alpha c_{1} \nabla f_{k}^{T} p_{k}$ 是无下界的 (Unbounded below), 所以一定会和 $\phi$ 产生相交。

1.令最小的交点 $\alpha$ '>0 则有

$f\left(x_{k}+\alpha^{\prime} p_{k}\right)=f\left(x_{k}\right)+\alpha^{\prime} c_{1} \nabla f_{k}^{T} p_{k}$

2. 根据中值定理(Mean value theorem), 存在 $\alpha^{\prime \prime} \in\left(0, \alpha^{\prime}\right)$ ，

$f\left(x_{k}+\alpha^{\prime} p_{k}\right)-f\left(x_{k}\right)=\alpha^{\prime} \nabla f\left(x_{k}+\alpha^{\prime \prime} p_{k}\right)^{T} p_{k}$

3. 根据上面两个等式有

$\nabla f\left(x_{k}+\alpha^{\prime \prime} p_{k}\right)^{T} p_{k}=c_{1} \nabla f_{k}^{T} p_{k}>c_{2} \nabla f_{k}^{T} p_{k}$

此时 $\alpha^{\prime \prime}$ 满足Wolfe conditions

$f\left(x_{k}\right)+(1-c) \alpha_{k} \nabla f_{k}^{T} p_{k} \leq f\left(x_{k}+\alpha_{k} p_{k}\right) \leq f\left(x_{k}\right)+c \alpha_{k} \nabla f_{k}^{T} p_{k}$

The Goldstein Conditions

如同Wolfe conditions，Goldstein Conditions 的目标确认保证步长 $\alpha$ 能够满足 Sufficient decrease 但是又不能太短。Goldstein Conditions 的第一个不等式为

$f\left(x_{k}\right)+(1-c) \alpha_{k} \nabla f_{k}^{T} p_{k} \leq f\left(x_{k}+\alpha_{k} p_{k}\right) \leq f\left(x_{k}\right)+c \alpha_{k} \nabla f_{k}^{T} p_{k}， \space \space 0< c <\frac{1}{2}$

其中第二个不等式为sufficient decrease condition 充分下降条件。第一个不等式则是用于控制步长。

Goldstein Conditions 的一个缺点(相比Wolfe condition)是在第一个不等式中，可能会去除 $\phi$ 的所有最小值。

但是其他和Wolfe 是相似的，并且收敛条件十分相同。 Goldstein Conditions 通常适合牛顿形式的方法，但并不适合使用了正定Hessian 近似的拟牛顿方法。

在此回顾一下，不管是Wolfe 还是 Goldstein 其最终目的都是寻找一个适合的步长 $\alpha$ 。

Sufficient decrease and Backtracking

只是单独的Sufficient decrease condition 不足以保证算法能够沿着搜索方向做出有效的进展，如果算法能通过Backtraking approach 而找到一个合适的候选步长(Candidate step length)，我们则可以免除额外的条件(此处指的是 curvature condition)，而仅仅使用Sufficient decrease condition 来结束一个线搜索过程。

Sufficient decrease and Backtracking 的基本形式为

Convergence of Line search methods 线搜索收敛讨论

为了达到全局最优，我们不仅要选择一个良好的步长 $\alpha$ ，同时一个准确的搜索方向 $p_{k}$ 也是必要的。本小姐小节主要讨论搜索方向的条件， 在算法中有一个良好的搜索方向和步长选择一样重要。

在此我们讨论的重点主要是一个性质： 在一般搜索方向 $p_{k}$ 和最速下降搜索方向 $-\nabla f_{k}$ 之间的角度 $\theta_{k}$ 定义为

$\cos \theta_{k}=\frac{-\nabla f_{k}^{T} p_{k}}{\left\|\nabla f_{k}\right\|\left\|p_{k}\right\|}$

Theorem 3.2 Zoutendijk condition

考虑到迭代 $x_{k+1}=x_{k}+\alpha_{k} p_{k}$ ， $p_{k}$ 是搜索方向而 $\alpha_{k}$ 满足Wolfe condition时。Zoutendijk condition 为

$\sum_{k \geq 0} \cos ^{2} \theta_{k}\left\|\nabla f_{k}\right\|^{2}<\infty$

This implies: $\cos ^{2} \theta_{k}\left\|\nabla f_{k}\right\|^{2} \rightarrow 0$

很多算法都用此性质来找到函数最小值，还有许多对应不同算法的情况，我们在之后再补充。

Rate of Convergence 收敛速度

算法的收敛常常有一个冲突，即是为了考虑如何兼顾满足全局最优和满足快速收敛；这也是算法设计的一个侧重点。 在本小节我们通过讨论最速下降法(The steepest descent method) 来探究收敛速度的问题。

Convergence rate of steepest descent

Suppose: $f(x)=\frac{1}{2} x^{T} Q x-b^{T} x$ , $Q$ is positive definite;

Gradient: $\nabla f(x)=Q x-b$ ; Minimizer $x^*$ is the unique solution of $Q x=b$ .

Compute $\alpha$ by differentiating $f\left(x_{k}-\alpha \nabla f_{k}\right)$ w.r.t $\alpha$ :

$f\left(x_{k}-\alpha \nabla f_{k}\right)=\frac{1}{2}\left(x_{k}-\alpha \nabla f_{k}\right)^{T} Q\left(x_{k}-\alpha \nabla f_{k}\right)-b^{T}\left(x_{k}-\alpha \nabla f_{k}\right)$

$\Rightarrow \alpha_{k}=\frac{\nabla f_{k}^{T} \nabla f_{k}}{\nabla f_{k}^{T} Q \nabla f_{k}}$

If the exact minimizer is used

$\Rightarrow x_{k+1}=x_{k}-\left(\frac{\nabla f_{k}^{T} \nabla f_{k}}{\nabla f_{k}^{T} Q \nabla f_{k}}\right) \nabla f_{k}$

Evaluate Rate of convergence: Wight of norm $\|x\|_{Q}^{2}=x^{T} Q x$

$\Rightarrow \left\|x_{k+1}-x^{*}\right\|_{Q}^{2}=\left\{1-\frac{\left(\nabla f_{k}^{T} \nabla f_{k}\right)^{2}}{\left(\nabla f_{k}^{T} Q \nabla f_{k}\right)\left(\nabla f_{k}^{T} Q^{-1} \nabla f_{k}\right)}\right\}\left\|x_{k}-x^{*}\right\|_{Q}^{2}$ by derivative

Theorem 3.3

当线搜索最速下降法被应用于强凸函数（如上式）时，误差形式为：

$\left\|x_{k+1}-x^{*}\right\|_{Q}^{2} \leq\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2}\left\|x_{k}-x^{*}\right\|_{Q}^{2}$

$0\leq \lambda_1 \leq \lambda_2 \leq .... \leq \lambda_n$ 是Q的 Eigenvalues， Condition number $\kappa (Q)= \lambda_n / \lambda_1$ .

Theorem 3.4

对于 $f$ ：在 $\mathbb{R}^{n}$ 内连续可导，使用最速下降收敛为 $x^*$ 并且Hessian matrix $\nabla^{2} f\left(x^{*}\right)$ 是正定的。

对于任何 $r \in\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}, 1\right)$ ，

$\Rightarrow f\left(x_{k+1}\right)-f\left(x^{*}\right) \leq r^{2}\left[f\left(x_{k}\right)-f\left(x^{*}\right)\right]$ .

为线性收敛速度。

Newton's method

Search direction: $p_{k}^{\mathrm{N}}=-\nabla^{2} f_{k}^{-1} \nabla f_{k}$

Theorem 3.5

当搜索方向为牛顿方向，如果 $\nabla^{2} f_{k}$ 正定，则牛顿法为二次收敛。（但是牛顿方向不总是为正定，因此Hessian在使用时需要进一步调整）。

Quasi-newton method

Search direction： $p_{k}=-B_{k}^{-1} \nabla f_{k}$

Theorem 3.6

Suppose that $f$ : $\mathbb{R}^{n} \rightarrow \mathbb{R}$ is twice continuously differentiable. Consider the iteration $x_{k+1}=x_{k}+\alpha_{k} p_{k}$ , where $p_k$ is a descent direction and $\alpha_k$ satisfies the Wolfe conditions, with c1 ≤ 1/2. If the sequence $\{x_k\}$ converges to a point $x^*$ such that $\nabla f(x^*)=0$ and $\nabla ^2 f(x*)$ is positive definite, and if the search direction satisfies $\lim _{k \rightarrow \infty} \frac{\left\|\nabla f_{k}+\nabla^{2} f_{k} p_{k}\right\|}{\left\|p_{k}\right\|}=0$ , then

如果 $\alpha_k=1 for \space all \space k>k_0$ , 收敛速度为超线性。

Modification 修正式

Newton's method with Hessian modification

Eigenvalue Modification

Adding a multiple of the identity

Modified Cholesky factorization

Modified symmetric indefinite factorization

这几个小节我们将在之后具体章节展开讨论。

Step-length Selection Algorithms 步长选择的算法

函数： $\phi(\alpha)=f\left(x_{k}+\alpha p_{k}\right)$ ， $p_k$ 是下降方向，并且 $\phi^{\prime}(0)<0$ .

1. 如果 $f$ 是二次凸函数， $f(x)=\frac{1}{2} x^{T} Q x-b^{T} x$ 他的一维最小值(沿着射线 $x_{k}+\alpha p_{k}$ ) 则是

$\alpha_{k}=-\frac{\nabla f_{k}^{T} p_{k}}{p_{k}^{T} Q p_{k}}$ 为步长最优解。

2. 如果目标函数是一个非线性问题(Nonlinear functions)，就需要用到迭代算法(Iterative procedure)求解，寻找最优步长或者满足前文提及条件的步长。尤其对于线搜索来说，对于优化方法的鲁棒性和效率有主要影响。求解步骤一般分为两步，一是寻找一个包含解的区间 $[\bar a, \bar b]$ ，二是逐渐放大(Zoom)该步长，直到确定最终步长。

本节主要讨论目标函数的梯度存在的情况，否则使用其他方法处理。

Interpolation 插值

插值法的目标是：在一系列的迭代中使步长逐步减小直到找到一个满足约束的步长情况。

Condition 1

充分减少条件： $\phi\left(\alpha_{k}\right) \leq \phi(0)+c_{1} \alpha_{k} \phi^{\prime}(0)$ ，在此之上设计一个更有效的步骤来使得 $f(x)$ 的导数计算更少。假设初始猜测值为 $\alpha_0$ ，则

$\phi\left(\alpha_{0}\right) \leq \phi(0)+c_{1} \alpha_{0} \phi^{\prime}(0)$

当步长满足此情况时，则寻找过程终止。否则，开始Condition 2

Condition 2

将取值范围变为 $[0,\alpha_0]$ （缩小取值范围），此时构造一个二次近似函数， $\phi_q(\alpha)$ , 并且使用三个函数 $\phi$ 的相关信息: $\phi_{q}(0)=\phi(0), \phi_{q}^{\prime}(0)=\phi^{\prime}(0), \text { and } \phi_{q}\left(\alpha_{0}\right)=\phi\left(\alpha_{0}\right)$ . 得到：

$\phi_{q}(\alpha)=\left(\frac{\phi\left(\alpha_{0}\right)-\phi(0)-\alpha_{0} \phi^{\prime}(0)}{\alpha_{0}^{2}}\right) \alpha^{2}+\phi^{\prime}(0) \alpha+\phi(0)$

则新的 $\alpha_1$ 取值为：

$\alpha_{1}=-\frac{\phi^{\prime}(0) \alpha_{0}^{2}}{2\left[\phi\left(\alpha_{0}\right)-\phi(0)-\phi^{\prime}(0) \alpha_{0}\right]}$

如果此时 $\alpha_{1}$ 满足条件 $\phi\left(\alpha_{0}\right) \leq \phi(0)+c_{1} \alpha_{0} \phi^{\prime}(0)$ ，则终止寻找过程，否则进入Condition 3.

Condition 3

在此情况中，我们构建一个 Cubic function，并且使用四个函数 $\phi$ 的相关信息： $\phi(0)$ ， $\phi^\prime (0)$ , $\phi(\alpha_0)$ , $\phi (\alpha_1)$ ,则可得到：

$\phi_{c}(\alpha)=a \alpha^{3}+b \alpha^{2}+\alpha \phi^{\prime}(0)+\phi(0)$

$\Rightarrow$ $\left[\begin{array}{c}a \\b\end{array}\right]=\frac{1}{\alpha_{0}^{2} \alpha_{1}^{2}\left(\alpha_{1}-\alpha_{0}\right)}\left[\begin{array}{cc}\alpha_{0}^{2} & -\alpha_{1}^{2} \\-\alpha_{0}^{3} & \alpha_{1}^{3}\end{array}\right]\left[\begin{array}{c}\phi\left(\alpha_{1}\right)-\phi(0)-\phi^{\prime}(0) \alpha_{1} \\\phi\left(\alpha_{0}\right)-\phi(0)-\phi^{\prime}(0) \alpha_{0}\end{array}\right]$

通过对 $\phi_c(x)$ 求导，我们可以找到在 $[0,\alpha_1]$ 中的minimizer of $\alpha_2$ of $\phi_c$ ，为

$\alpha_{2}=\frac {-b+\sqrt{b^{2}-3 a \phi^{\prime}(0)}}{3 a}$

如果必要，需要重复此过程。如果任何步长 $\alpha_i$ 对于上一次步长 $\alpha_{i-1}$ 而言过于接近或者过小，则直接定义 $\alpha_i=\frac{\alpha_{i-1}}{2}$ .

Initial step length 初始步长

对于牛顿或者拟牛顿方法来说，初始步长通常定义为 $\alpha_0=1$ ；对于其他非Scale的方法，比如最速下降和共轭梯度，初始化步长非常重要。通常有我们选择使 $\alpha_{0} \nabla f_{k}^{T} p_{k}=\alpha_{k-1} \nabla f_{k-1}^{T} p_{k-1}$ 则：