Armijo搜索下求解无约束优化问题的扰动BFGS方法

The Perturbed BFGS Method for the Unconstrained Optimization with the Armijo Line Search

摘要: 文献[1]提出了一种求解无约束优化问题的扰动BFGS方法，并在Wolfe搜索下证明了其全局收敛性。本文证明了该扰动BFGS方法在较弱的Armijo线性搜索下求解非凸问题也具有全局收敛性。数值结果表明在Armijo搜索下该方法也具有较好的数值效果。

Abstract: In [1], a perturbed BFGS method was proposed to solve the unconstrained optimization and was proved to be globally convergent when the Wolfe line search was used. In this paper, we show that the perturbed BFGS method also possesses global convergence for nonconvex problems with the relatively weaker Armijo line search. Numerical results show that this method with the Armijo search is also promising.

1. 引言

本文主要研究无约束优化问题：

$\min f\left(x\right),x\in R^n,$ (1.1)

其中 $f:R^n\to R$ 是一个连续可微的函数。BFGS方法是求解无约束优化问题的一种非常有效的拟牛顿方法 [2] ，该方法具有如下迭代格式：

$x_{k+1}=x_k+{\alpha }_k{d}_k,k\ge 1,$ (1.2)

其中步长 ${\alpha }_k$ 可通过某种线性搜索得到，搜索方向 $d_k$ 是以下线性方程的解，

$B_k{d}_k+\nabla f\left(x_k\right)=0,$ (1.3)

这里 $\nabla f\left(x\right)$ 是f在x处的梯度， $B_k$ 是拟牛顿矩阵，由下面BFGS公式进行校正：

$B_{k+1}=B_k-\frac{B_k{s}_k{s}_k^{\text{T}}{B}_k}{s_k^{\text{T}}{B}_k{s}_k}+\frac{y_k{y}_k^{\text{T}}}{y_k^{\text{T}}{s}_k},$ (1.4)

其中 $s_k=x_{k+1}-x_k$ ， $y_k=\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)$ 。BFGS校正公式的一个重要性质当 $y_k^{\text{T}}{s}_k>0$ ，且 $B_k$ 对称正定时， $B_{k+1}$ 也对称正定 [3] 。

Powell在文献 [4] 中证明了求解凸优化问题的BFGS方法只有全局收敛性。但对非凸优化问题，Dai [5] 和Mascarenhas [6] 给出例子说明采用Wolfe型非精确线性搜索和精确线性搜索的BFGS方法不一定具有全局收敛性。在文献 [1] 中，Liu提出了一种扰动的BFGS方法，简称PBFGS，在该算法中，搜索方向 $d_k$ 由以下线性方程组确定。

$\left(B_k+{\mu }_{k}Q\right)d_k+\nabla f\left(x_k\right)=0,$ (1.5)

这里的Q是一个给定的对称正定阵， ${\mu }_k$ 是扰动因子，满足 ${\mu }_k>0$ ，Liu [1] 证明了该扰动方法在Wolfe搜索下求解非凸问题具有全局收敛性。对Armijo搜索，该文未讨论其收敛性，原因是在Armijo搜索下 $y_k^{\text{T}}{s}_k$ 不一定大于0。

本节，我们给出具体的Armijo搜索下扰动的BFGS方法，我们采用Li在文献 [7] 中给出的BFGS公式校正迭代矩阵 $B_k$ 。

$B_{k+1}=\{\begin{array}{l}{B}_k-\frac{B_k{s}_k{s}_k^{\text{T}}{B}_k}{s_k^{\text{T}}{B}_k{s}_k}+\frac{y_k{y}_k^{\text{T}}}{y_k^{\text{T}}{s}_k}, 如果y_k^{\text{T}}{s}_k>0\hfill \\ B_k, 其他\hfill \end{array}$ (1.6)

其中 $s_k$ 与 $y_k$ 的取值与(1.4)式一致。值得指出的是，(1.6)式中只要 $B_0$ 对称正定，则得到的迭代矩阵序列 $\left\{B_k\right\}$ 总是对称正定的。在第二节中，我们给出具体算法并分析其全局收敛性。在第三节中，我们进行数值实验，验证在Armijo搜索下该扰动方法的计算效果。

2. 算法与收敛性分析

本文考虑该扰动的BFGS方法在Armijo搜索下的全局收敛性。下面我们给出算法的具体步骤。

算法1 (Armijo搜索下的PBFGS算法)：

步0：选择初始点 $x_1\in R^n$ 和初始的对称正定矩阵 $B_1\in R^{n\times n}$ 以及 $Q=I$ 。选取常数 $0<{\sigma }_1<{\sigma }_2<1$ ， $\rho ,\tau ,\eta \in \left(0,1\right),{\epsilon }_1>0$ 以及 $M_B>1$ 。令 ${\mu }_1={\epsilon }_1$ ， $\delta =\Vert \nabla f\left(x_1\right)\Vert$ 以及 $k=1$ 。

步1：解线性方程组

$\left(B_k+{\mu }_{k}Q\right)d_k+\nabla f\left(x_k\right)=0,$ (2.1)

解得 $d_k$ 。转步2。

步2：由Armijo线性搜索 [8]

$f\left(x_k+{\alpha }_k{d}_k\right)-f\left(x_k\right)\le {\sigma }_1{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k,$ (2.2)

来确定 ${\alpha }_k$ ，其中 ${\alpha }_k$ 的取值为集合 $\left\{\rho ,{\rho }^2,{\rho }^3,\cdots \right\}$ 中使上面不等式成立的最大者。然后令 $x_{k+1}=x_k+{\alpha }_k{d}_k$ 。

步3：由修正公式

$B_{k+1}=\{\begin{array}{l}{B}_k-\frac{B_k{s}_k{s}_k^{\text{T}}{B}_k}{s_k^{\text{T}}{B}_k{s}_k}+\frac{y_k{y}_k^{\text{T}}}{y_k^{\text{T}}{s}_k},如果y_k^{\text{T}}{s}_k>0\hfill \\ B_k, 其他\hfill \end{array}$ (2.3)

确定 $B_{k+1}$ 。

步4：如果 $\Vert \nabla f\left(x_{k+1}\right)\Vert /\delta \le \eta$ ，令 ${\epsilon }_{k+1}=\tau {\epsilon }_k$ ， ${\mu }_{k+1}={\epsilon }_{k+1}$ ， $\delta =\Vert \nabla f\left(x_{k+1}\right)\Vert$ 。否则令 ${\epsilon }_{k+1}={\epsilon }_k$ 以及

${\mu }_{k+1}=\{\begin{array}{l}{\epsilon }_{k+1}{\Vert B_{k+1}\Vert }_F,如果{\Vert B_{k+1}\Vert }_F\ge M_{k+1}\hfill \\ {\epsilon }_{k+1},其它\hfill \end{array}$ (2.4)

其中， $M_k=\max \left\{M_B,1/\Vert \nabla f\left(x_k\right)\Vert \right\}$ 。

步5：令 $k=k+1$ 然后转步1。

在以上的算法中， ${\epsilon }_k$ 按照如下规则逐渐减小

${\epsilon }_{k+1}=\{\begin{array}{l}\tau {\epsilon }_k,如果\Vert \nabla f\left(x_{k+1}\right)\Vert /\delta \le \eta \\ {\epsilon }_k,否则\end{array}$ (2.5)

其中 $\tau ,\eta \in \left(0,1\right)$ ，并且 $\delta =\Vert \nabla f\left(x_i\right)\Vert$ ，i取值是 $\left[1,k\right]$ 中的一个指标。所以 $\left\{\Vert \nabla f\left(x_k\right)\Vert \right\}$ 中必存在一个公比不超过 $\eta$ 的几何子序列，如果

$\underset{k\to \infty }{\lim \inf }\Vert \nabla f\left(x_k\right)\Vert =0$ (2.6)

成立，那么 $\left\{{\epsilon }_k\right\}$ 为单调非增序列，并且当 $k\to \infty$ 时，有 ${\epsilon }_k\to 0$ 。由此可得，当 ${\Vert B_k\Vert }_F$ 有界时， ${\epsilon }_k{\Vert B_k\Vert }_F\to 0$ ，从而 ${\mu }_k\to 0$ ，(2.1)式逐渐逼近于(1.3)式。

下面证明算法的全局收敛性，在证明之前需作如下假设：

假设1：存在一个水平集 $\Omega =\left\{x\in R^n|f\left(x\right)\le f\left(x_1\right)\right\}$ 是一个有界集，函数 $f\left(x\right)$ 在 $\Omega$ 上有Lipschitz连续的梯度，即存在常数 $L>0$ 使得

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert ,\left(\forall x,y\in \Omega \right).$ (2.7)

由(2.3)式所产生的矩阵 $B_k$ 总是正定的，从而序列 $\left\{f\left(x_k\right)\right\}$ 是单调递减的，由假设可知 $\Omega =\left\{x\in R^n|f\left(x\right)\le f\left(x_1\right)\right\}$ 是有界的，因而 $f\left(x\right)$ 有下界。由Armijo线性搜索不等式(2.2)可得

$\begin{array}{l}f\left(x_1+{\alpha }_1{d}_1\right)-f\left(x_1\right)\le {\sigma }_1{\alpha }_1\nabla f{\left(x_1\right)}^{\text{T}}{d}_1\\ ⋮\\ f\left(x_k+{\alpha }_k{d}_k\right)-f\left(x_k\right)\le {\sigma }_1{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k\end{array}$

将上面k个式子累加

$f\left(x_k+{\alpha }_k{d}_k\right)-f\left(x_1\right)\le {\sigma }_1{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k}.$

因此

$-{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k}\le -\frac{C_1}{{\delta }_1}<+\infty .$

其中常数 $C_1=f\left(x_k+{\alpha }_k{d}_k\right)-f\left(x_1\right)<0$ ，由此可推出

$-\underset{k\to +\infty }{\lim }{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k=-\underset{k\to +\infty }{\lim }\nabla f{\left(x_k\right)}^{\text{T}}{s}_k=0.$ (2.8)

为了方便证明收敛性，根据步4可定义指标集合

$K_{\tau }=\left\{k:{\epsilon }_{k+1}=\tau {\epsilon }_k\right\},$ $K_B=\left\{k:{\Vert B_k\Vert }_F\ge M_k\right\}.$ (2.9)

下面为了证明算法的全局收敛性，我们先证明几个重要的引理。

引理1：假定集合 $K_{\tau }$ 是有限集，则算法所产生的步长序列 $\left\{{\alpha }_k\right\}$ 有非零的下界，并且当 $k\to \infty$ 时， $d_k\to 0$ 。

证明：假定 $K_{\tau }$ 是有限集，即 ${\epsilon }_k$ 被减小有限次，也就是说存在一个整数 $k_1$ 使得对任意的 $k\ge k_1$ 都有 ${\epsilon }_k={\epsilon }_{k_1}$ 。由于 $B_k$ 是正定的，那么对于所有的k，有

$-\nabla f{\left(x_k\right)}^{\text{T}}{d}_k=d_k^{\text{T}}\left(B_k+{\mu }_{k}I\right)d_k\ge {\epsilon }_k{\Vert B_k\Vert }_F{\Vert d_k\Vert }^2\ge {\epsilon }_k\min \left\{1,M_B\right\}{\Vert d_k\Vert }^2.$ (2.10)

由Armijo型线性搜索准则知，当 ${\alpha }_k\ne 1$ 时， ${\rho }^{-1}{\alpha }_k$ 不满足(2.2)式 [5] [9] ，那么我们有 [9]

$f\left(x_k+{\rho }^{-1}{\alpha }_k{d}_k\right)-f\left(x_k\right)>{\sigma }_1{\rho }^{-1}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k.$ (2.11)

通过中值定理以及 $\nabla f\left(x\right)$ 的Lipschitz连续性，存在一个 ${\theta }_k\in \left(0,1\right)$ ，可得

$\begin{array}{l}f\left(x_k+{\rho }^{-1}{\alpha }_k{d}_k\right)-f\left(x_k\right)\\ ={\rho }^{-1}{\alpha }_k\nabla f{\left(x_k+{\theta }_k{\rho }^{-1}{\alpha }_k{d}_k\right)}^{\text{T}}{d}_k\\ ={\rho }^{-1}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k+{\rho }^{-1}{\alpha }_k\left[\nabla f{\left(x_k+{\theta }_k{\rho }^{-1}{\alpha }_k{d}_k\right)}^{\text{T}}-\nabla f\left(x_k\right)\right]d_k\\ \le {\rho }^{-1}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k+L{\rho }^{-2}{\alpha }_k^2{\Vert d_k\Vert }^2\end{array}$ ， (2.12)

这里的 $L>0$ 是 $\nabla f\left(x_k\right)$ 的Lipschitz常数。再将(2.12)式代入(2.11)式可得

$\begin{array}{l}{\alpha }_k\ge \frac{-\left(1-{\sigma }_1\right)\rho \nabla f{\left(x_k\right)}^{\text{T}}{d}_k}{L{\Vert d_k\Vert }^2}=\frac{\left(1-{\sigma }_1\right)\rho d_k^{\text{T}}\left(B_k+{\mu }_{k}I\right)d_k}{L{\Vert d_k\Vert }^2}\\ \ge \frac{\left(1-{\sigma }_1\right)\rho {\epsilon }_k{}_{{}_1}}{L}\min \left\{1,M_B\right\}>0.\end{array}$ (2.13)

当 ${\alpha }_k=1$ 时，显然可得 ${\alpha }_k>0$ 。又由(2.8)，(2.10)可得

$0=-\underset{k\to +\infty }{\lim }{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k=\underset{k\to +\infty }{\lim }{\alpha }_k{d}_k^{\text{T}}\left(B_k+{\mu }_{k}I\right)d_k\ge \underset{k\to +\infty }{\lim }{\alpha }_k{\epsilon }_k\min \left\{1,M_B\right\}{\Vert d_k\Vert }^2>0,$

因此， $k\to \infty$ 时， $d_k\to 0$ 。

引理2. 如果 $K_B$ 是无限集，而 $K_{\tau }$ 是有限集，则必有

$\underset{k\to \infty }{\lim }\inf \Vert \nabla f\left(x_k\right)\Vert =0.$ (2.14)

证明：令 ${\hat{\alpha }}_k={\alpha }_k/{\Vert B_k\Vert }_F$ 和 ${\hat{d}}_k={\Vert B_k\Vert }_F{d}_k$ ，那么有 ${\hat{\alpha }}_k{\hat{d}}_k={\alpha }_k{d}_k$ 。当 $K_{\tau }$ 为有限集时，可从集合 $K_B$ 的定义 $K_B=\left\{k:{\Vert B_k\Vert }_F\ge M_k\right\}$ ，这里 $M_k=\max \left\{M_B,1/\Vert \nabla f\left(x_k\right)\Vert \right\}$ 以及算法的步4知，对任意的 $k\ge k_1$ ，并且 $k\in K_B$ ，有 ${\mu }_k={\epsilon }_{k_1}{\Vert B_k\Vert }_F$ 。又由修正的拟牛顿方法 $\left(B_k+{\mu }_{k}I\right)d_k+\nabla f\left(x_k\right)=0$ ，那么 $d_k$ 也满足

$B_k{d}_k+{\epsilon }_{k_1}{\Vert B_k\Vert }_F{d}_k+\nabla f\left(x_k\right)=0.$

所以有

$-\nabla f{\left(x_k\right)}^{\text{T}}{\hat{d}}_k=d_k^{\text{T}}{B}_k{\hat{d}}_k+{\epsilon }_{k_1}{\Vert {\hat{d}}_k\Vert }^2.$ (2.15)

由(2.11)式和(2.12)式可得

$L{\rho }^{-2}{\alpha }_k^2{\Vert d_k\Vert }^2\ge \left(\sigma -1\right){\rho }^{-1}{\alpha }_k\nabla f{\left(x_k\right)}^{\text{T}}{d}_k.$

由上面不等式及 ${\hat{\alpha }}_k{\hat{d}}_k={\alpha }_k{d}_k$ ，我们可推出

$L{\rho }^{-2}{\hat{\alpha }}_k^2{\Vert {\hat{d}}_k\Vert }^2\ge \left(\sigma -1\right){\rho }^{-1}{\hat{\alpha }}_k\nabla f{\left(x_k\right)}^{\text{T}}{\hat{d}}_k,$

将(2.15)式代入上式，从而

${\hat{\alpha }}_k\ge \frac{-\left(1-{\sigma }_1\right)\rho \nabla f{\left(x_k\right)}^{\text{T}}{\hat{d}}_k}{L{\Vert {\hat{d}}_k\Vert }^2}=\frac{\left(1-{\sigma }_1\right)\rho \left(d_k^{\text{T}}{B}_k{\hat{d}}_k+{\epsilon }_{k_1}{\Vert {\hat{d}}_k\Vert }^2\right)}{L{\Vert {\hat{d}}_k\Vert }^2}\ge \frac{\left(1-{\sigma }_1\right)\rho {\epsilon }_{k_1}}{L}>0.$

进一步由(2.8)式及上面的结论有

$0=-\underset{k\to +\infty }{\lim }{\hat{\alpha }}_k\nabla f{\left(x_k\right)}^{\text{T}}{\hat{d}}_k=\underset{k\to +\infty }{\lim }\hat{\alpha }\left(d_k^{\text{T}}{B}_k{\hat{d}}_k+{\epsilon }_{k_1}{\Vert {\hat{d}}_k\Vert }^2\right)\ge \underset{k\to +\infty }{\lim }{\hat{\alpha }}_k{\epsilon }_{k_1}{\Vert {\hat{d}}_k\Vert }^2>0.$

可得

$\underset{k\to \infty ,k\in K_B}{\lim }{\hat{d}}_k=0.$ (2.16)

并且对所有的 $k\in K_B$ ，我们有

$\Vert \nabla f\left(x_k\right)\Vert \le \Vert B_k\Vert \Vert {\hat{d}}_k\Vert /{\Vert B_k\Vert }_F+{\epsilon }_{k_1}\Vert {\hat{d}}_k\Vert \le \left(1+{\epsilon }_{k_1}\right)\Vert {\hat{d}}_k\Vert .$

因此由(2.16)式的结论可得

$\underset{k\to \infty }{\lim }\inf \Vert \nabla f\left(x_k\right)\Vert =0.$

引理3：如果 $K_B$ 是有限集并且 $K_{\tau }$ 也是有限集，那么有

$\underset{k\to \infty }{\lim }\inf \Vert \nabla f\left(x_k\right)\Vert =0.$

证明：反设存在一个正数 $\gamma$ 使得对所有的k有 $\Vert \nabla f\left(x_k\right)\Vert \ge \gamma$ 成立。由算法的步4可知，当 $k\notin K_B$ 时，有 ${\mu }_k={\epsilon }_k$ ，且

${\Vert B_k\Vert }_F<\max \left\{M_B,1/\Vert \nabla f\left(x_k\right)\Vert \right\}\le \max \left\{M_B,1/\gamma \right\}.$ (2.17)

当 $K_{\tau }$ 为有限集时，对所有的 $k\ge k_1$ 有(2.10)式成立。由引理1和(2.8)可知，当 $k\to \infty$ 时， $d_k\to 0$ 。进一步由修正后的拟牛顿公式(2.1)以及(2.17)式可得，对所有的 $k\notin K_B$ 有下面不等式

$\Vert \nabla f\left(x_k\right)\Vert \le \left(\Vert B_k\Vert +{\epsilon }_k\right)\Vert d_k\Vert \le \left({\Vert B_k\Vert }_F+{\epsilon }_1\right)\Vert d_k\Vert \le \left(\max \left\{M_B,1/\gamma \right\}+{\epsilon }_1\right)\Vert d_k\Vert$

以上结论说明

$\underset{k\to \infty ,k\notin K_B}{\lim }\inf \Vert \nabla f\left(x_k\right)\Vert =0,$

但是这与假设矛盾，所以必定有(2.14)成立。

在引理2和引理3的基础上，下面我们证明算法1的全局收敛性。

定理1：设序列 $\left\{x_k\right\}$ 由算法产生且满足假设1，那么

$\underset{k\to \infty }{\lim }\inf \Vert \nabla f\left(x_k\right)\Vert =0.$ (2.18)

证明：这里需要考虑两种情形：(i) $K_{\tau }$ 是无限集和(ii) $K_{\tau }$ 是有限集。

对情形(i)：由 $K_{\tau }$ 的定义 $K_{\tau }=\left\{k:{\epsilon }_{k+1}=\tau {\epsilon }_k\right\}$ 及(2.4)式可知 $\left\{\Vert \nabla f\left(x_k\right)\Vert \right\}$ 中必存在一个公比不超过 $0<\eta <1$ 的几何子序列，那么此时必有(2.18)式成立。

对情形(ii)：这时需要考虑 $K_B$ 是无限集还是有限集这两种情况。在引理2和引理3中，我们已证明在这两种情况下，结论(2.18)总是成立的，即 ${\epsilon }_k$ 被减小无穷多次。因此，由 $K_{\tau }$ 的定义可知情形(ii)是不可能出现的。

由定理1可以得到， ${\epsilon }_k$ 一定无限次的减小，即 $k\to +\infty$ 时， ${\epsilon }_k\to 0$ 。当 $B_k$ 有界，且k充分大时，有 ${\mu }_k={\epsilon }_k$ ，显然当 $k\to +\infty$ 时，也可得到 ${\mu }_k\to 0$ 。

3. 数值试验及结果分析

为了验证本文提出的算法对实际问题的可行性，我们进行了数值实验及结果分析。数值实验是通过MATLAB7.0编程，程序在3.2 GHZ处理器，2 GB内存的电脑上实现。本文的所有测试问题以及问题的初始点均选自参考文献 [10] 。这些问题也被文献 [1] 采用来测试扰动的BFGS方法。为了体现算法的有效性，本文将计算结果与文献 [1] 提出的扰动的BFGS方法(PBFGS)和原始的BFGS方法的计算结果作比较。同时规定 $\Vert \nabla f\left(x_k\right)\Vert \le {10}^{-6}$ 为算法的终止条件，并规定算法中的常数和参数的取值为： ${\sigma }_1=0.001,{\sigma }_2=0.9,\eta =0.5,\tau =0.7,{\epsilon }_1=1.0,M_B={10}^{10},B=I$ 。测试问题如下：

问题1： $\min f\left(x\right)=100{\left(x_1^2-x_2\right)}^2+{\left(x_1-1\right)}^2$ 。

问题2： $\min f\left(x\right)={\left({10}^4{x}_1{x}_2-1\right)}^2+{\left({\text{e}}^{-x_1}+{\text{e}}^{-x_2}-1.0001\right)}^2$ 。

问题3： $\min f\left(x\right)=100{\left(x_1^2-x_2\right)}^2+{\left(x_1-1\right)}^2$ 。

问题4： $\min f\left(x\right)=100{\left(x_3-10\theta \left(x_1,x_2\right)\right)}^2+100{\left({\left(x_1^2+x_2^2\right)}^{1/2}-1\right)}^2+x_3^2$ ，其中

$\theta \left(x_1,x_2\right)=\{\begin{array}{l}\frac{1}{\text{2π}}\arctan \left(\frac{x_2}{x_1}\right),x_1>0\\ \frac{1}{\text{2π}}\arctan \left(\frac{x_2}{x_1}\right)+0.5,x_1<0\end{array}$ 。

问题5： $\min f\left(x\right)={\left(x_1+10x_2\right)}^2+5{\left(x_3-x_4\right)}^2+{\left(x_2-2x_3\right)}^4+10{\left(x_1-x_4\right)}^4$ 。

问题6： $\min f(x)=100{\left(x_2-x_1^2\right)}^2+{\left(1-x_1\right)}^2+90{\left(x_4-x_3^2\right)}^2+{\left(1-x_3\right)}^2+10{\left(x_2+x_4-2\right)}^2+10{\left(x_2-x_4\right)}^2$ 。

Table 1. Experimental results of algorithm

表1. 算法的数值实验结果

表1中表头的各个变量的具体意义如下：pro表示被测问题序号，ite表示迭代次数，gn表示目标函数梯度的计算次数，BFGS表示使用Wolfe搜索下的BFGS方法，PBFGS表示使用Wolfe搜索下的扰动的BFGS方法，PBFGS (Armijo)表示本文提出的Armijo搜索下的扰动的BFGS方法。

从表1的各项数据可以看出，本论文提出的算法能有效地解决各类问题并且能保持BFGS的仿射不变性。虽然在求解其中几个问题时，Armijo搜索下扰动的BFGS方法的迭代次数相对于PBFGS方法多几步，是因为PBFGS方法采用的是Wolfe搜索，对于步长的搜索优于Armijo搜索。与BFGS方法的迭代次数相比，本文研究的算法数值效果会优于Wolfe搜索下的BFGS方法。总的来说，我们的Armijo搜索下扰动的BGFS方法效果较好。

致谢

本篇论文，我首先要感谢我的导师周伟军教授及我的同班同学，从论文选题、论文的撰写、修改到最终完稿，他们都给予了我很大的帮助。其次，我要感谢我父母对我的支持，是父母的辛勤培育，才造就我现在的学习成果。