引言

上一节介绍了从方向角度认识线搜索方法，本节继续介绍：从步长角度认识线搜索方法。

回顾：线搜索方法——方向角度

关于线搜索方法的迭代过程表示如下：
$$x_{k+1}=x_k+{\alpha }_k\cdot {\mathcal{P}}_k$$

关于收敛性的假设

关于目标函数：$f(\mathcal{X})$，我们通过求解一系列数值解 { x k } k = 0 ∞ {x_k}_{k=0}^{infty} {xk​}k=0∞​的方式使得：

• 随着迭代次数$k$的增加，对应的$f(x_k)$能够有效地收敛，最终得到目标函数的最小值：$\begin{array}{r}\underset{\mathcal{X}\in {\mathbb{R}}^n}{\min }f(\mathcal{X})\end{array}$，从而得到数值解的最优值$x^{\ast }$：
  $$x^{\ast }=\underset{\mathcal{X}\in {\mathbb{R}}^n}{\mathrm{argmin}}f(\mathcal{X})$$

关于单调性的假设

为了简化逻辑，我们仅讨论各迭代步骤的数值解 { x k } k = 0 ∞ {x_k}_{k=0}^{infty} {xk​}k=0∞​对应的目标函数结果 { f ( x k ) } k = 0 ∞ {f(x_k)}_{k=0}^{infty} {f(xk​)}k=0∞​服从严格的单调性。即：
其中$N$表示非负整数。
$$\forall k\in N\Rightarrow f(x_{k+1})<f(x_k)$$

下降方向与最速方向

基于上一节的相关假设，我们可以得到如下结论：
$$f(x_{k+1})-f(x_k)\approx {\left[\nabla f(x_k)\right]}^T\cdot {\mathcal{P}}_k<0$$
将上式继续展开：
$$||\nabla f(x_k)||\cdot ||{\mathcal{P}}_k||\cos \theta <0$$
从上式可以看出：

• $||\nabla f(x_k)||$与$||{\mathcal{P}}_k||$分别表示向量$\nabla f(x_k),{\mathcal{P}}_k$的模，因而它们恒正。因而向量$\nabla f(x_k),{\mathcal{P}}_k$之间的夹角 θ ∈ ( π 2 , 3 π 2 ) heta in left(π2,3π2

  $$egin{aligned}frac{pi}{2},frac{3pi}{2}end{aligned}$$ ight) θ∈(2π​,23π​​)。见下图：
  
  其中蓝色虚线上方的部分表示$\theta \in \left(\begin{array}{r}\frac{\pi }{2},\frac{3\pi }{2}\end{array}\right)$的区间，由于${\mathcal{P}}_k$是单位向量，因此蓝色虚线上方圆上的点构成的单位向量${\mathcal{P}}_k$都可以使$f(x_{k+1})<f(x_k)$，我们称这些方向为下降方向$(\text{Descent Direction})$；

• 由于$x_k$是上一次迭代产生的数值解，因而$||\nabla f(x_k)||$是确定的；并且$||{\mathcal{P}}_k||=1$，如何使$||\nabla f(x_k)||\cdot ||{\mathcal{P}}_k||\cos \theta$达到最小，只能通过调整方向($\theta$)来获取最小值。

  当 $\theta =\pi$时，$\cos \theta$取得最小值$-1$。这意味着：当向量${\mathcal{P}}_k$与梯度向量$\nabla f(x_k)$方向相反时，可取得当前迭代步骤的最优方向。该方向也被称作最速下降方向$(\text{Steepest Descent Direction})$。而梯度下降法也被称作最速下降法。

从步长角度观察线搜索方法

关于方向向量的假设

在观察步长的过程中，我们同样需要固定住方向信息。我们首先假定向量${\mathcal{P}}_k$的方向是下降方向而非最速下降方向；

也可以说：下降方向需要向量${\mathcal{P}}_k$与负梯度向量$-\nabla f(x_k)$之间的夹角是锐角：
之所以上一节将其范围描述为 ( − π 2 , π 2 ) (−π2,π2)

$$egin{aligned} left(-frac{pi}{2},frac{pi}{2} ight)end{aligned}$$ (−2π​,2π​)​,是因为这种描述方法是将$-\nabla f(x_k)$方向固定，仅对${\mathcal{P}}_k$方向进行约束。但实际上:向量${\mathcal{P}}_k$与向量$-\nabla f(x_k)$之间夹角和向量$-\nabla f(x_k)$与向量${\mathcal{P}}_k$之间夹角之间没有区别。因而可将其夹角范围描述为$\begin{array}{r}\left(0,\frac{\pi }{2}\right)\end{array}$。
$$-{\left[\nabla f(x_k)\right]}^T{\mathcal{P}}_k>0\Rightarrow {\left[\nabla f(x_k)\right]}^T{\mathcal{P}}_k<0$$

精确搜索过程

关于步长${\alpha }_k$，我们在优化算法——无约束优化概述中介绍过：无论${\alpha }_k$较大还是较小，都会产生负面影响：

• 步长过大，可能会导致即便方向${\mathcal{P}}_k$正确，但依然使得$f(x_{k+1})>f(x_k)$，从而使本次迭代产生的$x_{k+1}$无效；
• 步长过小，相比于步长过大确实能够更少地出现迭代无效的情况，但一直使用较小步长反而在迭代过程中出现不必要的计算代价。

思考：在方向向量${\mathcal{P}}_k$是下降方向的条件下，如何去选择合适的步长${\alpha }_k$$?$一个朴素的想法是：使$f(x_{k+1})$达到最小的步长就是最优步长：
这里的${\mathcal{P}}_k$是给定的，$x_k$也是给定的，说明该优化问题是一个关于$\alpha$的一次的优化问题，因此也将线搜索方法称作一维搜索方法。
α k = arg min ⁡ α > 0 f ( x k + 1 ) = arg min ⁡ α > 0 f ( x k + α ⋅ P k ) = { arg min ⁡ α > 0 ϕ ( α ) ϕ ( α ) ≜ f ( x k + α ⋅ P k ) αk=argminα>0f(xk+1)=argminα>0f(xk+α⋅Pk)={argminα>0ϕ(α)ϕ(α)≜f(xk+α⋅Pk)

$$egin{aligned} alpha_k & = mathop{argmin}limits_{alpha > 0} f(x_{k+1}) \ & = mathop{argmin}limits_{alpha > 0} f(x_k + alpha cdot mathcal P_k) \ & = egin{cases} mathop{argmin}limits_{alpha > 0} phi(alpha) \phi(alpha) riangleq f(x_k + alpha cdot mathcal P_k) end{cases} end{aligned}$$ αk​​=α>0argmin​f(xk+1​)=α>0argmin​f(xk​+α⋅Pk​)=⎩ ⎨ ⎧​α>0argmin​ϕ(α)ϕ(α)≜f(xk​+α⋅Pk​)​​
很明显，这就是仅关于$\alpha$的一元函数，在$\alpha >0$约束条件下求解它的最值是简单的。这种求解步长${\alpha }_k$的方式被称作精确搜索方法。

既然是要计算$\varphi (\alpha )$的最值，首先对该函数的梯度进行描述：
∂ ϕ ( α ) ∂ α = ϕ ′ ( α ) = [ ∇ f ( x k + α ⋅ P k ) ] T ⋅ P k ∂ϕ(α)∂α=ϕ′(α)=[∇f(xk+α⋅Pk)]T⋅Pk

$$egin{aligned} frac{partial phi(alpha)}{partial alpha} & = phi'(alpha) \ & = left[ abla f(x_k + alpha cdot mathcal P_k) ight]^T cdot mathcal P_k end{aligned}$$ ∂α∂ϕ(α)​​=ϕ′(α)=[∇f(xk​+α⋅Pk​)]T⋅Pk​​

虽然我们并不清楚函数$\varphi (\alpha )$的具体形状，但不妨碍我们对该函数中一些特殊点对应的实际意义：

• $\alpha =0\Rightarrow \varphi (\alpha )=f(x_k)$；
  当然，根据$\alpha$的定义域，它是不可能取到$0$的。但确实存在实际意义：当步长为$0$时，$x_{k+1}=x_k$；

  关于$\alpha =0$时的梯度${\varphi }^{\prime }(0)$可以表示为：
  这正是关于方向向量${\mathcal{P}}_k$的假设。也就是说，函数$\varphi (\alpha )$在零点处的斜率是负值。
  $${\varphi }^{\prime }(0)={\left[\nabla f(x_k)\right]}^T{\mathcal{P}}_k<0$$
  我们可以尝试认知一下零点处的切线方程：
  这个关于$\alpha$的一元一次方程斜率是${\left[\nabla f(x_k)\right]}^T{\mathcal{P}}_k$,并且过点$[0,f(x_k)]$点。
  $$\mathcal{L}(\alpha )=[\nabla f(x_k){]}^T{\mathcal{P}}_k\cdot \alpha +f(x_k)$$

从管中窥豹的观察，我们可以做一个简单认知：$\varphi (\alpha )$自身是一个过$[0,f(x_k)]$，初始梯度是负值的一个复杂函数。如果想要求解它的最值，仅需要令 ∂ ϕ ( α ) ∂ α ≜ 0 ∂ϕ(α)∂α≜0

$$egin{aligned}frac{partial phi(alpha)}{partial alpha} riangleq 0 end{aligned}$$ ∂α∂ϕ(α)​≜0​从而求解出$\alpha$的最值结果。

虽然$\varphi (\alpha )$仅包含一个，并且仅有一次的未知项$\alpha$，但实际情况下，它的求解并不简单。其核心原因是：我们不清楚目标函数$f(\cdot )$的复杂程度。
这取决于模型、以及任务类型。

• 首先，目标函数$f(x_k+\alpha \cdot {\mathcal{P}}_k)$自身就是一个复杂函数，并且它的梯度$\nabla f(x_k+\alpha \cdot {\mathcal{P}}_k)$同样也是复杂的。
• 关于梯度$\nabla f(x_k+\alpha \cdot {\mathcal{P}}_k)$并不是仅计算一次，而是每一次迭代过程中都要计算梯度。这使得计算代价可能极高。

该步骤实际上也是一个求解解析解的过程，但实际上我们对每次迭代精确求解最优步长是没有必要的。我们只希望迭代产生的$f(x_k)$收敛即可。

下一节我们将讨论：是否可以使用非精确搜索来近似每次迭代步长的最优解。

相关参考：
【优化算法】线搜索方法-步长-精确搜索