1. 迭代求解的基本流程与停止准则

1.1 迭代求解的基本流程

优化问题的解通常无法直接而精确地求得，因而退而求其数值近似解.数值求解通常通过一个迭代过程来完成，在迭代时必须保证下一个点仍在可行集中，对约束优化问题而言这经常是很大的障碍，但是对于无约束优化问题 $f(x)$ 而言却没有这个障碍，因为无约束优化问题的可行集是全空间 ${\mathbb{R}}^n$，也就是说任意方向都是其可行方向，那么如何才能最快地获取近似解呢？这便是本笔记中要学习的问题.

通常的迭代过程可以叙述如下：先选取一个初始近似值 $x_0$，然后在近似解的周围按某种方式搜索一个新的点 $x_1$ 使得
$f(x_1)<f(x_0)$， 将此过程不断进行下去，直至得到最优解的一个可接受的近似值为止. 用数学表达式的来描述这个过程可以如下表示：$$\begin{array}{rlr}{x}_{k+1}=x_k+{\alpha }_k{d}_k,& & \text{s.t.}f(x_{k+1})<f(x_k)\end{array}$$其中，$d_k$ 称为该迭代算法的搜索方向，${\alpha }_k>0$ 称为搜索步长. 上述的迭代过程包含如下两个基本问题：

(1.1.1) 如何最佳地选择下降方向 $d_k;$

(1.1.2) 如何最佳地选择步长 ${\alpha }_k.$

上述两个问题可以同时进行，但更多的方法是先选择方向再选择步长. 为了使得$f(x_{k+1})<f(x_k)$,必须选择使得 $f$ 函数值能够减少的方向，即下降的方向$d_k$.当 $f$为一阶可微时，由于$$\begin{array}{r}f(x_k+\alpha d_k)=f(x_k)+\alpha \nabla f(x_k{)}^T{d}_k+o(\Vert \alpha d_k\Vert )\end{array}$$所以，使得 $f$在$x_k$ 处下降的方向 $d_k$ 应满足
$$\nabla f(x_k{)}^T{d}_k<0.$$称满足该条件的方向 $d_k$ 称为下降方向.

下降方向的选择对算法的性能有决定性的作用.其中给定下降方向后选择步长的问题称为线搜索问题.

1.2 停止准则

迭代算法往往不能在有限次达到精确解，但实际中无须求得精确解，因此需要设置停止参数来节省计算资源，即当 $x_k$ 与精确解 $x^{\ast }$ 的误差 $\Vert x_k-x^{\ast }{\Vert }_2$ 小于某个给定的精度时就终止迭代，但由于优化问题的解 $x^{\ast }$ 是未知的，所以实际上无法通过
$\Vert x_k-x^{\ast }{\Vert }_2$ 来确定迭代过程在什么时候终止.一般情况下，人们采取如下两种终止指标：

(1.2.1) 用 $\Vert x_{k+1}-x_k{\Vert }_2$ 的大小或 $|f(x_{k+1})-f(x_k)|$ 的大小来作为终止指标. 直观上说就是连续两次的迭代对解的改善很小时即可终止迭代.

(1.2.2) 另一种更常用的终止准则基于如下事实：当 $f$ 一阶可微时，极小点 $x^{\ast }$ 满足$\nabla f(x^{\ast })=0$. 所以如果 $\nabla f(x_k)$ 已经足够小，那么在 $x_k$ 的邻近，无论沿那个方向 $d$ 做迭代，$f(x)$ 的进一步下降的幅度都将非常小. 这表明，沿着这个方向继续迭代下去的改善已经微乎其微了，可以终止. 所以根据此事实，通常使用$$\Vert \nabla f(x_k){\Vert }_2\le ϵ$$来作为迭代算法的终止条件，其中 $ϵ>0$ 为一个给定的常数，称为停止阈值.

但是上述终止条件并不能够保证 $x_k$ 一定是 $f$ 的近似极小值点，因为平稳点(满足 $\nabla f(x^{\ast })=0$ 的点)并一定是极小值，例如 $f(x)=x^3$ 在 $x=0$ 处的一阶导数为0，但显然 $x=0$ 不是 $f(x)=x^3$ 的极小值点.但当在 $f$ 是二阶可微且其 Hessian 矩阵 ${\nabla }^{2}f(x^{\ast })$ 是正定或 $f$ 为凸函数的情形下，满足 $\nabla f(x\ast )=0$ 的$x^{\ast }$ 却是 $f$ 的局部极小点的充分必要条件.

给定停止阈值 $ϵ>0$，在迭代算法中，如果在某一次满足 $\Vert \nabla f(xk)\Vert 2\le ϵ$，那么算法终止，无需进一步迭代.此时称该算法是 $ϵ-$有限终止的.如果对任意 $ϵ>0$ 算法总是 $ϵ-$ 有限终止的，则称该算法是阈值有限终止的.根据阈值有限终止的定义，可以证明阈值有限终止条件等价于如下二者之一成立：

• 存在 k ≥ 0 使得 $\Vert \nabla f(x_k){\Vert }_2=0$,
• $\Vert \nabla f(x_k){\Vert }_2>0,\forall k\ge 0,\text{且}{\underline{\lim }}_{k\to \infty }\Vert \nabla f(x_k){\Vert }_2=0.$

反之，阈值有限终止不成立等价于存在 ${ϵ}_0>0$，使得 $\Vert \nabla f(x_k){\Vert }_2\ge {ϵ}_0,\forall k\ge 0$.

1.3 收敛阶

衡量一个迭代算法的性能的指标主要有, 误差要小，计算量要快，并且对计算空间的要求小.误差用以描述迭代算法的近似程度，一般情况下用如下的收敛阶来刻画：

定义 1.1 (收敛性及收敛阶) 设 { x k } \{x_k\} {xk​} 是计算某个优化问题所生成的迭代点列，$x^{\ast }$ 是优化问题的解，如果 ${\lim }_{k\to \infty }\Vert x_k-x^{\ast }{\Vert }_2=0$,则称 { x k } \{x_k\} {xk​} 收敛于 $x^{\ast }$.此外，如果存在 $q>0$ 和 $\mu \ge 0$,使得，当 $x_k\ne x^{\ast }$ 时，有$$\underset{k\to \infty }{\lim }\frac{\Vert x_{k+1}-x^{\ast }{\Vert }_2}{\Vert x_k-x^{\ast }{\Vert }_2^q}=\mu ,$$

• 当 $q=1$ 且 $\mu \in (0,1)$ 时，称之为线性收敛的.当 $\mu =0$时，则称之为超线性收敛的.
• 当 $q>1,\mu >0$ 时- 称算法是 $q-$阶收敛的，特别地对应于 $p=2,3$ 时，分别称之为平方的与立方的收敛的.

衡量一个迭代算法的优劣的另一个常用的方法是所谓的二次终止性，其基本思想是如果目标函数是一个二次函数
$$f(x):=\frac{1}{2}{x}^{T}Gx+b^{T}x+c,$$其中 $G\in {\mathbb{S}}_{+}^n,b\in {\mathbb{R}}^n,c\in \mathbb{R},$ 若利用该迭代算法能从任意初值出发经过有限次迭代达到最小点，那么称该算法具有二次终止性.二次终止性的意义在于, 对于二次可微的目标函数 $f$，根据 Taylor 展开，$f$ 在极小点邻近可以用一个二次函数来逼近，因此具有二次终止性的算法在极小点邻近将有较理想的收敛速度.

2. 线搜索方法

已知搜索方向而求搜索步长的过程称为线搜索过程.下面对精确搜索算法和非精确搜索算法讨论步长的选择以及迭代算法的收敛性.

2.1 精确线搜索

设迭代的当前状态为 $x_k$,要求下一个点 $x_{k+1}=x_k+{\alpha }_k{d}_k$. 当迭代方向 $d_k$ 为已知，并且迭代方式是目标函数值减小的方向，即 $\varphi (\alpha ):=f(x_k+\alpha d_k)$ 满足

$$\begin{array}{r}{\varphi }^{\prime }(0)=\nabla f(x_k{)}^T{d}_k<0\end{array}$$时，选择合适的步长 ${\alpha }_k$,使得 $\varphi (\alpha ):=f(x_k+{\alpha }_k{d}_k)$ 尽可能小.最好的${\alpha }_k$ 是如下优化问题$$\begin{array}{r}\underset{\alpha >0}{\min }\varphi (\alpha )\end{array}$$的解.这种给定搜索方向$d_k$,根据(2)来选取 ${\alpha }_k$ 的搜索方法称为精确线搜索. 此时由于 ${\alpha }_k$ 是最优步长， 那么必然有 $\frac{d}{dt}f(x_k+t{d}_k){|}_{t={\alpha }_k}=0$ ，从而精确线搜索的迭代点列 $x_{k+1}=x_k+{\alpha }_k{d}_k$ 满足$$\begin{array}{r}\nabla f(x_{k+1}{)}^T{d}_k=0.\end{array}$$一般情况下，满足(3)的解 $x_{k+1}$ 不能够解析求得，这时候便需要采用搜索法求近似值X.其基本思想是先确定极小点所在的区间 $[a,b]$，然后通过如下的方式缩小搜索区间：设搜索的第 $i$ 步所得到的区间是 $[ai,bi]$，取 $p_i,q_i$ 满足 $a_i\le p_i<q_i\le b_i$， 然后按如下规则缩小区间：

• 若 $\varphi (p_i)\le \varphi (q_i)$，则令 $a_{i+1}=a_i$, $b_{i+1}=q_i$

• 若 $\varphi (p_i)>\varphi (q_i)$，则令 $a_{i+1}=p_i$, $b_{i+1}=b_i$

如果 $\varphi$ 为 $[a,b]$ 上单峰函数，也就是一元拟凸函数时，搜索法总能在有限步找到最小值点具有任意精度的近似点.

2.2 非精确搜索

精确搜索在每一步迭代都要求解一个一元函数的极小问题，该极小化问题可以通过确定搜索区间，并在搜索区间里采用搜索算法来求近似值，但由于每一次迭代都需要这么做，所以精确搜索的运算量是相当大的.

正如名字一样，非精确搜索并不要求计算 ${\min }_{\alpha \ge 0}f(x_k+\alpha d_k)$.，而是沿着给定的方向 $d_k$, 找合适的 ${\alpha }_k$,使得 $f(x+{\alpha }_k{d}_k)$ 较之 $f(x_k)$ 有较好的下降.

沿着下降方向 $d_k$, 当步长 $\alpha$ 足够小时，函数值 $f(x_k+\alpha d_k)$ 一定下降.然而，如果 $\alpha$ 取得太小，下降的幅度太小，导致要经过很多次迭代才能收敛到 ${\alpha }^{\ast }$.但如果步长太大，有可能 $f(x_k+\alpha d_k)$ 反而增加，也不是好的选择. 所以，正确的方法是：要保证 $f(x_k+\alpha d_k)$ 有一定程度的下降，且$\alpha$不能太小.

Goldstein 准则

为了保证搜索过程中 $\varphi (\alpha ):=f(x_k+\alpha d_k)$ 有一定比例的下降，搜索步长 $\alpha >0$ 应该满足$$\varphi (\alpha )\le \varphi (0)+{\rho }_1{\varphi }^{\prime }(0)\alpha .$$其中 $0\le {\rho }_1\le 1$ 是预先给定的参数. 这样得到的 ${\alpha }_k$ 保证 $f(x_{k+1})$ 有较好幅度的下降.

同时，为了避免 ${\alpha }_k$ 取值太小而导致 $\varphi$ 下降太慢，还要求 $\alpha$ 满足：$$\begin{array}{r}\varphi (\alpha )\ge \varphi (0)+{\rho }_2{\varphi }^{\prime }(0)\alpha ,\end{array}$$其中 $0\le {\rho }_2\le 1$ 是另一个预先给定的参数. 将此条件前一条结合起来，便可以得到如下的Goldstein 准则：$$\varphi (0)+{\rho }_2{\varphi }^{\prime }(0)\alpha \le \varphi (\alpha )\le \varphi (0)+{\rho }_1{\varphi }^{\prime }(0)\alpha ,$$其直观意义如图 2.1所示.

图 2.1：Goldstein 准则示意图

显然，落在图 2.1中黑色区间内的 $\alpha$ 均满足 Goldstein 准则， 这比找 $\varphi$ 的最小值点要容易得多.由于 ${\varphi }^{\prime }(0)<0$, 所以，为了使得满足上式的 $\alpha$ 存在， 必须 $0<{\rho }_1\le {\rho }_2\le 1$.为了容易求出 $\alpha$,通常取 ${\rho }_1<{\rho }_2$. 为简计，我们取 $0<\rho \le 1/2$, 并令 ${\rho }_1=\rho ,{\rho }_2=1-\rho$.这样 Goldstein 准则可以写成
$$\begin{array}{r}f(x_k)+\alpha (1-\rho )\nabla f(x_k{)}^T{d}_k\le f(x_k+\alpha d_k)\le f(x_k)+\alpha \rho \nabla f(x_k{)}^T{d}_k,\end{array}$$其中 $0<\rho \le 1/2.$

命题 2.2.1 (Goldstein 搜索的存在性) 设 $f$ 在 ${\mathbb{R}}^n$ 上连续且有下界，在 $x_k$ 处可微且$\nabla f(x_k{)}^T{d}_k<0,\rho \in (0,1/2]$, 那么满足 $Goldstein$ 准则的 $\alpha >0$ 一定存在.

证. 记 $\varphi (\alpha ):=f(x_k+\alpha d_k)$. 则 $\varphi$ 是 R 上一阶可微且有下界的函数，${\varphi }^{\prime }(0)=$ $\nabla f(x_k{)}^T{d}_k<0$.记

$$\begin{array}{r}\psi (\alpha ):=\varphi (0)+\alpha (1-\rho ){\varphi }^{\prime }(0)-\varphi (\alpha ).\end{array}$$

将$\varphi$在$\alpha =0$ 点做 Taylor 展开，得 $\psi (\alpha )=-\alpha \rho {\varphi }^{\prime }(0)+o(\alpha )$.由于 ${\varphi }^{\prime }(0)=\nabla f(x_k{)}^T{d}_k<0$ 所以，当$\alpha >0$ 充分小时，有 $\psi (\alpha )>0.$

由于 $\varphi$ 有下界，于是 $\varphi (0)-\varphi (\alpha )$ 有界，且由于${\varphi }^{\prime }(0)=\nabla f(x_k{)}^T{d}_k<0$，于是有当 $\alpha \to \infty$时，$\alpha (1-\rho ){\varphi }^{\prime }(0)\to -\infty$.所以，当 α 足够大时，有 $\psi (\alpha )<0$. 从而存在 $\alpha >0$, 使得 $\psi (\alpha )=0.$ 从而
$$\varphi (0)+\alpha (1-\rho ){\varphi }^{\prime }(0)=\varphi (\alpha )\le \varphi (0)+\alpha \rho {\varphi }^{\prime }(0).$$其中最后一个不等号用到了Goldstein 准则中 $\rho \le \frac{1}{2}$ 的推导.

Wolfe 准则

Goldstein 准则的基本思想是使得 $\alpha$ 不太小，同时 $\varphi (\alpha )$ 较之 $\varphi (0)$ 有一定程度的下降. 基于这个思想还可以提出其他类似的准则，Wolfe 用条件 $f(x_k+\alpha d_k{)}^T{d}_k\ge \sigma \nabla f(x_k{)}^T{d}_k$, 其中 $0<\sigma <1$,来避免 $\alpha$ 太小，并结合 $\varphi (\alpha )\le \varphi (0)+{\rho }_1{\varphi }^{\prime }(0)\alpha$，其中 $0\le {\rho }_1\le 1$ 是预先给定的参数，而提出了如下的 Wolfe 准则
$$\begin{array}{r}\varphi (\alpha )\le \varphi (0)+\alpha \rho {\varphi }^{\prime }(0),{\varphi }^{\prime }(\alpha )\ge \sigma {\varphi }^{\prime }(0).\end{array}$$其中 $0<\rho ,\sigma <1$. Wolfe准则如下图所示：

图 2.2：Wolfe 准则示意图

由于去掉了 Goldstein 准则的第二个条件，所以不必限制 $\rho <1/2.$

同时为了避免 $\alpha$ 使得 ${\varphi }^{\prime }(\alpha )=\nabla f(x_k+\alpha d_k{)}^T{d}_k$ 取正值且朝着增长的方向离开 $\varphi (\alpha )$ 的最小值点太远，可以考虑如下的强 Wolfe 准则：$$\begin{array}{rl}\varphi (\alpha )& \le \varphi (0)+\alpha \rho {\varphi }^{\prime }(0),|{\varphi }^{\prime }(\alpha )|\le -\sigma {\varphi }^{\prime }(0).\end{array}$$其中 $0<\rho ,\sigma <1$.

命题 2.2.2 (Wolfe 搜索的存在性) 设 $f$ 在 ${\mathbb{R}}^n$ 上一阶可微且有下界，$\nabla f(x_k{)}^T{d}_k<0$, $0<\rho \le \sigma <1$,那么满足强 Wolfe 准则的 $\alpha >0$ 一定存在.

证. 记 $\psi (\alpha ):=\varphi (0)+\alpha \rho {\varphi }^{\prime }(0)-\varphi (\alpha )$.如命题 2.2.1的证明所得，对充分小的 $\alpha >0$, 有 $\psi (\alpha )>0$,且存在 $\alpha >0$,使得 $\psi (\alpha )=0$.记 α m i n : = min ⁡ { α > 0 ∣ ψ ( α ) = 0 } . \alpha_{\mathrm{min}}:=\min\{\alpha>0|\psi(\alpha)=0\}. αmin​:=min{α>0∣ψ(α)=0}.那么，${\alpha }_{\min }>0,\psi (0)=\psi ({\alpha }_{\min })=0,$且$\psi (\alpha )>0,\forall \alpha \in (0,{\alpha }_{min})$. 利用微分中值定理，存在 $\tilde{\alpha }\in (0,{\alpha }_{\min })$,使得 ${\psi }^{\prime }(\tilde{\alpha })=0$,即 $\rho {\varphi }^{\prime }(0)-{\varphi }^{\prime }(\tilde{\alpha })=0$.

由于 $\rho \le \sigma$,所以$|{\varphi }^{\prime }(\tilde{\alpha })|=\rho |{\varphi }^{\prime }(0)|\le -\sigma {\varphi }^{\prime }(0).$ 而 $\psi (\tilde{\alpha })>0$ 表明 $\varphi (\tilde{\alpha })<\varphi (0)+\tilde{\alpha }\rho {\varphi }^{\prime }(0)$. 所以 $\tilde{\alpha }$ 满足强Wolfe 条件.

2.3 线搜索算法的收敛性

接下来的内容是给出精确线搜索，以及非精确线搜索 Goldstein 准则和 Wolfe 准则所产生的迭代点列 { x k } \{x_k\} {xk​} 的收敛性. 记 l e v f ( x 0 ) ( f ) : = { x ∈ R n ∣ f ( x ) ≤ f ( x 0 ) } . \begin{aligned}\mathbf{lev}_{f(x_0)}(f):=\{x\in\mathbb{R}^n|f(x)\leq f(x_0)\}.\end{aligned} levf(x0​)​(f):={x∈Rn∣f(x)≤f(x0​)}.​

命题 2.3.1 设 $f\in C^1({\mathbb{R}}^n)$ 有下界，其梯度向量 $\nabla f(x)$ 在凸集 $D\subset {\mathbb{R}}^n$ 上一致连续，$x_0\in D$ 使得 ${\mathbf{lev}}_{f(x_0)}(f)\subset D$.设以 $x_0$ 为初始点，当 $\nabla f(x_k)\ne 0$ 时，采用如下搜索方向和搜索步长：

• 搜索方向：$d_k$ 与 $-\nabla f(x_k)$ 之间的夹角 ${\theta }_k$ 为一致锐角，即 $\exists \mu \in (0,\pi /2)$, 使得
  $$\begin{array}{r}0\le {\theta }_k\le \frac{\pi }{2}-\mu ,\forall k=0,1,\cdots ;\end{array}$$
• 搜索步长：精确搜索，或满足 $Goldstein$ 准则或 $Wolfe$ 准则所得的迭代点列 { x k } \{x_k\} {xk​} 满足：存在 $k\ge 0$ 使得 $\Vert \nabla f(x_k){\Vert }_2=0$,或者 ${\lim }_{k\to \infty }\Vert \nabla f(x_k){\Vert }_2=0.$

证.记 $g_k:=\nabla f(x_k)$.不妨设 $g_k\ne 0,\forall k=0,1,\cdots$, 我们证明 ${\lim }_{k\to \infty }\Vert g_k{\Vert }_2=0$.为简计，设搜索方向 $d_k$ 是单位向量：$\Vert d_k{\Vert }_2=1$. 则可以证明如下几点：

(i) 根据迭代的定义， { f ( x k ) } \{f(x_k)\} {f(xk​)} 单调下降且有下界故收敛，于是$f(x_k)-f(x_k+1)\to 0(k\to \infty );$

(ii) 由微分中值定理可知，存在 ${\theta }_k\in (0,1)$, 使得$$\begin{array}{r}f(x_k)-f(x_k+\beta d_k)=-\beta \nabla f(x_k+{\theta }_k\beta d_k{)}^T{d}_k.\end{array}$$，由于$\nabla f(x)$ 在 $D$ 上一致连续，故
$$\begin{array}{r}|\nabla f(x_k+{\theta }_k\beta d_k{)}^T{d}_k-\nabla f(x_k{)}^T{d}_k|\le \Vert \nabla f(x_k+{\theta }_k\beta d_k)-\nabla f(x_k){\Vert }_2=o(1),\end{array}$$，其中高阶无穷小 $o(1)$ 对 $k$ 是一致的，即 $\forall ϵ>0$，存在与 $k$ 无关的 $\delta >0$，当 $0<\beta <\delta$ 时，$|o(\beta )|/\beta <ϵ$ 对所有 $k$ 成立.

(iii) 且由一致锐角条件有：
$$-g_k^T{d}_k=\Vert g_k{\Vert }_2\cos {\theta }_k\ge \Vert g_k{\Vert }_2\cos (\frac{\pi }{2}-\mu )=\Vert g_k{\Vert }_2\sin \mu .$$，于是 $g_k^T{d}_k\ge \Vert g_k{\Vert }_2\sin \mu$

利用反证法：若命题的结论不成立, 则存在 $ϵ>0$ 及子列 { g k } k ∈ K \{g_k\}_{k\in\mathcal{K}} {gk​}k∈K​，使得 $\Vert g_k{\Vert }_2\ge ϵ,\forall k\in \mathcal{K}$.这里仅以精确搜索为例来说明矛盾，类似地也可以导出 Goldstein准则和 Wolfe准则的矛盾.

如果 {$x_k\}$ 是精确搜索所得的点列，那么根据上述的前提(ii)和(iii)有： $\forall \alpha >0$ 和 $k\ge 0$，$$\begin{array}{r}f(x_k)-f(x_{k+1})\ge f(x_k)-f(x_k+\alpha d_k)=-\alpha g_k^T{d}_k+o(\alpha )\ge \alpha (\Vert g_k{\Vert }_2\sin \mu +\frac{o(\alpha )}{\alpha }).\end{array}$$所以，$\forall k\in \mathcal{K}$, 有
$$\begin{array}{r}f(x_k)-f(x_{k+1})\ge \alpha (ϵ\sin \mu +\frac{o(\alpha )}{\alpha }).\end{array}$$取 $\alpha >0$ 足够小，使得 $\frac{o(\alpha )}{\alpha }<ϵ(\sin \mu )/2$. 由于高价无穷小 $o(\alpha )$ 对 $k$ 是一致成立的，所以这样的$\alpha$ 与$k$ 无关.于是有
$$\begin{array}{r}f(x_k)-f(x_{k+1})\ge \frac{1}{2}\alpha ϵ\sin \mu .\end{array}$$又由于 $k$ 是任意的，则这与 $f(x_k)-f(x_{k+1})\to 0(k\to \infty )$ 矛盾.

实际上，如果函数 $f$ 的光滑性能够被保证，一致锐角条件可以减弱，下面不加证明地给出下面的命题.（我就不贴上证明啦，看得我头疼~）

命题 2.2.4 (Zoutendijk) 设 $f\in C^1({\mathbb{R}}^n)$ 有下界，梯度向量 $\nabla f(x)$ 在凸集 $D\subset {\mathbb{R}}^n$ 上$Lipschitz$ 连续，$x_0\in D$ 使得水平集 ${\mathrm{lev}}_{f(x_0)}(f)\subset D$.设以 $x_0$ 为初始点，当 $\nabla f(x_k)\ne 0$ 时，采用如下搜索方向和搜索步长：

• 搜索方向：$d_k$ 与 $-\nabla f(x_k)$ 成锐角：$\nabla f(x_k{)}^T{d}_k<0$, 且 $\Vert d_k{\Vert }_2=1$,
• 搜索步长：精确搜索或满足 $Wolfe$ 准则

所得的迭代点列 { x k } \{x_k\} {xk​} 满足：
$$\sum _{k=0}^{\infty }\Vert \nabla f(x_k){\Vert }_2^2{\cos }^2{\theta }_k<\infty ,$$其中 ${\theta }_k$ 表示 $-\nabla f(x_k)$ 与搜索方向 $d_k$ 的夹角，即 $-\nabla f(x_k{)}^T{d}_k=\Vert \nabla f(x_k){\Vert }_2\cos {\theta }_k.$

推论 2.2.5 在命题 2.2.4的条件下，若 $\Vert \nabla f(x_k){\Vert }_2\ne 0,\forall k\ge 0$, 且满足条件 ${\sum }_{k=1}^{\infty }{\cos }^2{\theta }_k=\infty .$, 则 ${\underline{\lim }}_{k\to \infty }\Vert \nabla f(x_k){\Vert }_2=0.$

证. 设结论不成立，则存在 $\delta >0$, 使得$\nabla f(x_k){\Vert }_2\ge \delta ,\forall k\ge 0$.于是
$$\begin{array}{rl}\sum _{k=1}^{\infty }\Vert \nabla f(x_k){\Vert }_2^2{\cos }^2{\theta }_k& \ge {\delta }^2\sum _{k=1}^{\infty }{\cos }^2{\theta }_k=\infty ,\end{array}$$这与命题 2.2.4 的结论矛盾.