引言

上一节对优化问题进行了简单描述，并从逻辑认知的角度介绍了线搜索方法与信赖域方法。本节将关注线搜索方法，并重点关注它的方向部分。

回顾：线搜索方法

线搜索方法是一种通过求解数值解来计算最优解的方法。其特点是：在数值解的迭代求解过程中，分为方向与步长分别执行，并且先定方向，后定步长。对应的数学符号表达如下：
$$x_{k+1}=x_k+{\alpha }_k\cdot {\mathcal{P}}_k$$
其中${\alpha }_k$表示步长，${\mathcal{P}}_k$表示方向。并且步长的重要程度高于方向。

从方向角度观察线搜索方法

我们首先对优化问题(场景)进行一系列的假设以达到简化作用。

场景构建

假设1：目标函数结果的单调性

关于变量$\mathcal{X}$的目标函数$f(\mathcal{X})$，我们最终目标是选择一个合适的$\mathcal{X}=x$，使得目标函数达到最值。这里以最小值为例，对应数学符号表示如下：
$$\underset{\mathcal{X}\in {\mathbb{R}}^n}{\min }f(\mathcal{X})$$

迭代之前，我们给定关于$\mathcal{X}$的初始化信息：$x_0$，并在迭代过程中通过策略得到一系列数值解： { x k } k = 1 ∞ {x_k}_{k=1}^{infty} {xk​}k=1∞​，它们对应的目标函数结果表示如下：
{ f ( x k ) } k = 0 ∞ {f(x_k)}_{k=0}^{infty} {f(xk​)}k=0∞​

上一节介绍过，目标函数结果所描述的数列存在单调性，但这个单调性可能是不严格的：

• 如果数列满足严格的单调性，有：
  f ( x k + 1 ) < f ( x k ) f ( x k ) , f ( x k + 1 ) ∈ { f ( x k ) } k = 0 ∞ f(x_{k+1}) < f(x_k) quad f(x_k),f(x_{k+1}) in {f(x_k)}_{k=0}^{infty} f(xk+1​)<f(xk​)f(xk​),f(xk+1​)∈{f(xk​)}k=0∞​
• 相反，如果数列的单调性不严格，有：
  f ( x k + 1 ) < f ( x k − m ) f ( x k + 1 ) , f ( x k − m ) ∈ { f ( x k ) } k = 0 ∞ ; m ∈ [ 0 , k ] f(x_{k+1}) < f(x_{k-m}) quad f(x_{k+1}),f(x_{k-m}) in {f(x_k)}_{k=0}^{infty};m in [0,k] f(xk+1​)<f(xk−m​)f(xk+1​),f(xk−m​)∈{f(xk​)}k=0∞​;m∈[0,k]

也就是说，严格的单调性需要数列中的元素按照顺序严格递减；而不严格的单调性仅需要趋势递减即可，局部元素之间的大小关系并不是关注的重点。
在真实情况下，单调性的严格/不严格并不是绝对的。在迭代之前，初始化信息$x_0$一般是随机初始化，从而导致$x_0$到最优解$x^{\ast }$的距离是随机的。因此在迭代初期，我们通常会采用不严格的递减方式，随着数值解$x_k$逐步逼近最优解$x^{\ast }$,我们会调整参数$m$,使其逐步地向严格的递减方式转化。

在方向角度观察线搜索方法之前，为简化运算，设定 { 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)$$

假设2：屏蔽步长${\alpha }_k$对线搜索方法过程的影响

上一节同样介绍了：线搜索方法对于步长的要求比较严格，较大或者较小的步长都会对线搜索方法产生负面影响。

不否认的是：较大的步长可能会影响方向，从而使线搜索方法失效；但较小的步长仅会使计算(迭代)代价提升，从而在真实情况中不太可用，但并不会使算法失效，也不会对其收敛性产生太大影响。

• 较小的步长仅仅使收敛速度慢了，而不是不收敛了。
• ‘较大步长可能影响方向’示例见文章末尾。

由于这里仅讨论方向角度的线搜索方法，因此这里关于步长的假设是：在线搜索方法的迭代过程中，其步长${\alpha }_k$足够小，小到可以忽略不计。
由于‘步长’${\alpha }_k$的实际意义，因而它一定是一个正值。

假设3：限定向量${\mathcal{P}}_k$的大小

向量${\mathcal{P}}_k$既包含大小，也包含方向。而观察方向角度的线搜索方法中，${\mathcal{P}}_k$的大小同样不是我们关注的对象。因此我们需要将${\mathcal{P}}_k$简化为单位向量。即：
$$||{\mathcal{P}}_k||=1k=1,2,3,\cdots$$
关于向量大小的约束我们早在支持向量机——模型构建思路中关于约束条件，消除等比例缩放对函数间隔$(\text{Functional Margin})$的影响时使用的方法：
$$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)>0\Rightarrow y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1$$
实际上，假设$2$与假设$3$可以进行合并。当${\mathcal{P}}_k$化简为相应的单位向量时，该向量一定与${\mathcal{P}}_k$线性相关。化简后产生的标量系数可以与步长做乘法，从而被忽略掉。

下降方向的推导过程

基于上述假设，我们可以对数值解$x_{k+1}$对应的目标函数结果$f(x_{k+1})$通过泰勒公式进行展开：
仅展开至$2$阶。
f ( x k + 1 ) = f ( x k + α k ⋅ P k ) = f ( x k ) + 1 1 ! [ ∇ f ( x k ) ] T ⋅ ( x k + 1 − x k ) + 1 2 ! ( x k + 1 − x k ) T [ ∇ 2 f ( x k ) ] ( x k + 1 − x k )

$$egin{aligned} f(x_{k+1}) & = f(x_k + alpha_k cdot mathcal P_k) \ & = f(x_k) + frac{1}{1!} left[ abla f(x_k) ight]^T cdot (x_{k+1} - x_k) + frac{1}{2!} (x_{k+1} - x_k)^T left[ abla^2 f(x_k) ight](x_{k+1} - x_k) end{aligned}$$ f(xk+1​)​=f(xk​+αk​⋅Pk​)=f(xk​)+1!1​[∇f(xk​)]T⋅(xk+1​−xk​)+2!1​(xk+1​−xk​)T[∇2f(xk​)](xk+1​−xk​)​
将$x_{k+1}-x_k={\alpha }_k{\mathcal{P}}_k$代入，化简有：
$$\begin{array}{r}f(x_{k+1})=f(x_k)+{\left[\nabla f(x_k)\right]}^T\cdot {\alpha }_k{\mathcal{P}}_k+\frac{1}{2}({\alpha }_k{\mathcal{P}}_k{)}^T\left[{\nabla }^{2}f(x_k)\right]{\alpha }_k{\mathcal{P}}_k\end{array}$$
观察后一项：$\begin{array}{r}\frac{1}{2}({\alpha }_k{\mathcal{P}}_k{)}^T\left[{\nabla }^{2}f(x_k)\right]{\alpha }_k{\mathcal{P}}_k\end{array}$，其中${\alpha }_k{\mathcal{P}}_k$是$n\times 1$的向量，这意味着：该项的结果是一个标量。并且是与$||{\alpha }_k{\mathcal{P}}_k||$相关的一个标量(这里将$\begin{array}{r}\frac{1}{2}\end{array}$与标量${\alpha }_k$合并到一起)，我们直接将其记作$\mathcal{O}(||{\alpha }_k{\mathcal{P}}_k||)$。又因为上述假设$2$与假设$3$的合并，这里直接将$\mathcal{O}(||{\alpha }_k{\mathcal{P}}_k||)$忽略掉，简化为如下形式：
这里的$\mathcal{O}(||{\alpha }_k{\mathcal{P}}_k||)$指与${\alpha }_k{\mathcal{P}}_k$相关的复杂项。
$$\begin{array}{rl}f(x_{k+1})& =f(x_k)+{\left[\nabla f(x_k)\right]}^T\cdot {\alpha }_k{\mathcal{P}}_k+\mathcal{O}(||{\alpha }_k{\mathcal{P}}_k||)\\ & \approx f(x_k)+{\left[\nabla f(x_k)\right]}^T\cdot {\alpha }_k{\mathcal{P}}_k\end{array}$$
从而有：
$$f(x_{k+1})-f(x_k)\approx {\left[\nabla f(x_k)\right]}^T\cdot {\alpha }_k{\mathcal{P}}_k$$
又因为假设$1$：严格的单调性，因而有：
$$\forall k\in N\Rightarrow f(x_{k+1})<f(x_k)\Rightarrow {\left[\nabla f(x_k)\right]}^T\cdot {\alpha }_k{\mathcal{P}}_k<0$$
由于${\alpha }_k$自身是一个正值，因而可以不等号两侧同时除以${\alpha }_k$，不改变不等号的方向。因而有：
$${\left[\nabla f(x_k)\right]}^T\cdot {\mathcal{P}}_k<0$$
可以观察：$\nabla f(x_k)$是数值解$x_k$对应的目标函数的梯度向量；而${\mathcal{P}}_k$是数值解$x_k$在当前迭代步骤中更新的方向向量(单位向量)。根据上式，我们就可以反过来对${\mathcal{P}}_k$的约束条件进行描述：

基于上述假设，如果存在这样的${\mathcal{P}}_k$，使得 [ ∇ f ( x k ) ] T ⋅ P k < 0

$$egin{aligned}left[ abla f(x_k) ight]^T cdot mathcal P_k < 0end{aligned}$$ [∇f(xk​)]T⋅Pk​<0​，那么该${\mathcal{P}}_k$一定满足$f(x_{k+1})<f(x_k)$。

并满足条件的${\mathcal{P}}_k$方向称作下降方向$(\text{Descent Direction})$。

下降方向的几何意义

观察上面的公式：
[ ∇ f ( x k ) ] T ⋅ P k < 0

$$egin{aligned}left[ abla f(x_k) ight]^T cdot mathcal P_k < 0end{aligned}$$ [∇f(xk​)]T⋅Pk​<0​
不等式左侧的本质上就是向量$\nabla f(x_k)$与向量${\mathcal{P}}_k$之间的内积结果。将其继续展开：
$$||\nabla f(x_k)||\cdot ||{\mathcal{P}}_k||\cdot \cos \theta <0$$
其中$||\nabla f(x_k)||,||{\mathcal{P}}_k||=1$分别表示上述两向量的大小，均恒正；这意味着$\cos \theta <0$，而$\theta$表示向量$\nabla f(x_k)$与向量${\mathcal{P}}_k$之间的夹角。这意味着：向量$\nabla f(x_k)$与向量${\mathcal{P}}_k$的夹角范围在$\begin{array}{r}\left(\frac{\pi }{2},\frac{3\pi }{2}\right)\end{array}$之间。

观察上述图像：

• 其中蓝色虚线表示$\mathcal{X}$变量空间中，过点$x_k$与目标函数等高线的切线；
• 与蓝色虚线垂直，并向远离目标函数的黑色箭头是梯度方向$\nabla f(x_k)$，与其相反的黑色箭头就是梯度的负方向。
• 以$x_k$为圆心，$1$为半径作圆(因为${\mathcal{P}}_k$是单位向量)，在蓝色虚线上方并且落在圆上的点(橙色点)与$x_k$相连接构成的向量就是${\mathcal{P}}_k$可能选择的向量。图中的红色弧线表示夹角。

在优化算法——无约束优化概述中提到线搜索方法方向中的与负梯度方向相关的方向就是与负梯度方向夹角在 ( − π 2 , π 2 )

$$egin{aligned}left(-frac{pi}{2},frac{pi}{2} ight)end{aligned}$$ (−2π​,2π​)​之间的方向(与梯度方向的情况正好相反)。

• 继续观察上图，如果方向在蓝色虚线或者是蓝色虚线以下的范围内，那么更新后的梯度目标函数结果必然大于当前等高线的数值结果。
• 可以想象一下：如果更新的${\mathcal{P}}_k$方向与切线方向非常接近(例如图中最右侧的橙黄色点),如果稍微控制不好步长从而使步长过大，那么最终同样导致更新后的目标函数结果大于之前的结果，从而导致本次迭代无效。从侧面也能看出合理步长的重要性。

同理，如果${\mathcal{P}}_k$方向恰好与$\nabla f(x_k)$之间的夹角为$\pi$(与$\nabla f(x_k)$方向完全相反)，那么此时的$\cos \theta =-1$，对应更新后的$f(x_{k+1})$相比$f(x_k)$减小的程度是最强烈的，也是当前迭代步骤最优的优化方向：
f ( x k + 1 ) − f ( x k ) ≈ α k ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos ⁡ θ = − α k ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ 1 ⋅ ( − 1 ) = − α k ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣

$$egin{aligned} f(x_{k+1}) - f(x_k) & approx alpha_k cdot || abla f(x_k)|| cdot ||mathcal P_k|| cdot cos heta \ & = - alpha_k cdot || abla f(x_k)|| cdot 1 cdot (-1) \ & = -alpha_k cdot || abla f(x_k)|| end{aligned}$$ f(xk+1​)−f(xk​)​≈αk​⋅∣∣∇f(xk​)∣∣⋅∣∣Pk​∣∣⋅cosθ=−αk​⋅∣∣∇f(xk​)∣∣⋅1⋅(−1)=−αk​⋅∣∣∇f(xk​)∣∣​

实际上，梯度下降法$(\text{Gradient Descent,GD})$，它每一次迭代(更新步骤)中总会选择最优的优化方向(与梯度方向相反的方向)作为下降方向，因为在当前迭代步骤中，该方向目标函数下降的效果最明显。因此梯度下降法也被称作最速下降法。

相关参考：
【优化算法】线搜索方法-方向