一种新的MBFGS算法

A New MBFGS Algorithm

摘要: 本文在MBFGS算法的研究基础上，对该算法进行推广，形成了一种新的MBFGS算法。同时，研究了其全局收敛性并给出相关证明。一些数值实验表明，这种改进的MBFGS方法对于给定的测试问题是有效的。对于一些无约束优化问题，新的MBFGS算法平均比单调或传统的非单调格式的BFGS方法使用更少的函数和梯度求值。

Abstract: Based on the research of MBFGS algorithm, this algorithm is extended to form a new MBFGS algo-rithm. At the same time, its convergence is studied and the relevant proof is given. Some numerical experiments show that the improved MBFGS method is effective for a given test problem. For some unconstrained op-timization problems, the new MBFGS algorithm uses less function and gradient evaluation than the mono-tone or traditional non monotone BFGS method.

1. 引言

在本文中，我们考虑以下无约束优化问题：

$\min f\left(x\right),x\in R^n$，其中 $f:R^n\to R$ 是一个连续可微函数，其梯度用g表示。单调线搜索方法来解决此问题要求每一次的迭代，目标函数值都要有下降，而非单调线搜索就不需要目标函数值连续下降，非单调线搜索最早是由Grippo [1] 于1986年提出。其具体格式如下：

给定常数a>0， $\delta ,\rho \in \left(0,1\right)$ 非负整数M，设定步长 ${\alpha }_k=\max \left\{a{\rho }^0,a{\rho }^1,\cdots \right\}$ 满足下列不等式：

$f\left(x_k+{\rho }^{m}a{d}_k\right)\le \underset{0\le j\le M}{\max }f\left(x_{k-j}\right)+\delta {\rho }^{m}a{g}_k^{\text{T}}{d}_k$

当M = 0时此不等式即变为标准的Armijo线搜索规则，非单调线搜索的一个优点是步长可以尽可能松散地选择，大量的数值实验表明，这种非单调线搜索技术是非常有效的，但也存在一些缺点，首先，由于上述不等式中的最大值函数，在任何迭代中生成的好的函数值基本上被丢弃。其次，在某些情况下，该方法数值性能非常依赖于M的选择，MBFGS [2] 方法中采用的线搜索就是由Grippo [3] 提出的方法，因此我们想通过更改MBFGS方法中的线搜索规则 [4] 来获得一种新的MBFGS方法，从而获得更好的数值性能。

本文其余部分组织如下：第二部分详细介绍了新的MBFGS方法；第三部分证明该算法的全局收敛性；第四部分给出数值实验结果。

2. 新的MBFGS算法

1.给定 $x_0\in R^n$， $B_0=I$， ${\delta }_1\in \left(0,1\right)$， ${\delta }_2>0$， $0\le {\eta }_{\min }\le {\eta }_{\max }<1\prec \rho$， $C_0:=f\left(x_0\right)$， $Q_0:=1$， $k:=0$

$0\le {\eta }_{\min }\le {\eta }_{\max }\le 1<\rho ,{\eta }_k\in \left[{\eta }_{\min },{\eta }_{\max }\right],\mu >0$

2) 由 $B_{K}d+g_k=0$，计算下降方向 $d_k$，如果 $f\left(x_k+d_k\right)\le f\left(x_k\right)+{\delta }_1{g}_k^{\text{T}}{d}_k$，取步长 ${\alpha }_k=1$，否则去步3。

3) 计算步长 ${\alpha }_k=\bar{\alpha }{\rho }^{h_k}$，其中 $h_k$ 是使得下列不等式成立的最大整数：

$f\left(x_k+{\alpha }_k{d}_k\right)\le C_k+{\delta }_1{\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\Vert {\alpha }_k{d}_k\Vert }^2$， (1.1)

其中 $C_{k+1}=\frac{{\eta }_k{Q}_k{C}_k+f\left(x_{k+1}\right)}{Q_{k+1}}$， $Q_{k+1}={\eta }_k{Q}_k+1$，

4) 计算 $x_{k+1}=x_k+{\alpha }_k{d}_k$

5) 迭代更新： $s_k=x_{k+1}-x_k$， $y_k=g_{k+1}-g_k$，

$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{z_k{z}_k^{\text{T}}}{z_k^{\text{T}}{s}_k}$， $z_k=y_k+C{\Vert g\left(x_k\right)\Vert }^r{s}_k+\max \left\{0,-\frac{y_k^{\text{T}}{s}_k}{{\Vert s_k\Vert }^2}\right\}{s}_k$

其中C，r > 0为给定常数。

3. 全局收敛性

在这一部分，为了建立起全局收敛性，需要先做以下几个假设 [5]：

1) 水平集 $\Omega =\left\{x\in R^n|f\left(x\right)\le f\left(x_0\right)\right\}$ 是有界的。

2) 在 $\Omega$ 的某些邻域N里，f是连续可微的且其导数Lipschitz连续 [6]，也就是说存在一个常数L大于0使得 $\Vert g\left(x\right)-g\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in N$，也就是说由本算法产生的序列 $\left\{x_k\right\}$ 是包含于 $\Omega$ 内的，此外，由假设得到，存在常数 ${\gamma }_1$ 使得 $\Vert g\left(x\right)\Vert \le {\gamma }_1,\forall x\in \Omega$。

3) 假定存在正的常数 $c_1,c_2$ 使得 $g_k^{\text{T}}{d}_k\le -c_1{\Vert g_k\Vert }^2$， $\Vert d_k\Vert \le c_2\Vert g_k\Vert$ (2.1)

引理1：假定假设2，3成立，如果 ${\alpha }_k$ 是满足(1.1)的步长，那么存在一个常数c大于0使得对每个k，都有下列不等式成立：

${\alpha }_k\ge \min \left\{\frac{\mu }{\rho },c\frac{\left|g_k^{\text{T}}{d}_k\right|}{{\Vert d_k\Vert }^2}\right\}$ (2.2)

证明：我们将从两个方面来证明。

情况一： $\rho {\alpha }_k\ge \mu$，那么就有 ${\alpha }_k\ge \frac{\mu }{\rho }$ 则(2.2)成立

情况二： $\rho {\alpha }_k<\mu$ 在此种情况下，很明显对于获得的步长 $\rho {\alpha }_k$ 不满足(1.1)，因此，则有：

$f\left(x_k+\rho {\alpha }_k{d}_k\right)>C_k+{\delta }_1\rho {\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\Vert \rho {\alpha }_k{d}_k\Vert }^2\ge f\left(x_k\right)+{\delta }_1\rho {\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\Vert \rho {\alpha }_k{d}_k\Vert }^2$ (2.3)

又由于中值定理，存在 ${\theta }_k\in \left(0,1\right)$ 使得：

$\begin{array}{c}f\left(x_k+\rho {\alpha }_k{d}_k\right)-f\left(x_k\right)=\rho {\alpha }_{k}g{\left(x_k+{\theta }_k\rho {\alpha }_k{d}_k\right)}^{\text{T}}{d}_k\\ =\rho {\alpha }_k{g}_k^{\text{T}}{d}_k+\rho {\alpha }_k{\left(g\left(x_k+{\theta }_k\rho {\alpha }_k{d}_k\right)-g_k\right)}^{\text{T}}{d}_k\\ \le \rho {\alpha }_k{g}_k^{\text{T}}{d}_k+L{\rho }^2{\alpha }_k^2{\Vert d_k\Vert }^2\end{array}$ (2.4)

联立(2.3)，(2.4)，则有：

$\rho {\alpha }_k{g}_k^{\text{T}}{d}_k+L{\rho }^2{\alpha }_k^2{\Vert d_k\Vert }^2\ge {\delta }_1\rho {\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\rho }^2{\Vert {\alpha }_k{d}_k\Vert }^2$

$\left(L+{\delta }_2\right)\rho {\alpha }_k{\Vert d_k\Vert }^2\ge \left({\delta }_1-1\right)g_k^{\text{T}}{d}_k$

${\alpha }_k\ge \left(\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }\right)\frac{g_k^{\text{T}}{d}_k}{{\Vert d_k\Vert }^2}$ (2.5)

其中 $c=\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }$。

引理2：

$\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0$，如果 ${\eta }_{\max }<1$，那么 $\underset{k\to \infty }{\lim }{g}_k=0$。

证明：首先需证明：

$f_{k+1}\le C_k-\beta \Vert g_k^2\Vert$， (2.5.2)

情况1： ${\alpha }_k\ge \frac{\mu }{\rho }$

由(2.1)有：

$\begin{array}{c}{f}_{k+1}\le C_k+{\delta }_1{\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\Vert {\alpha }_k{d}_k\Vert }^2\le C_k-{\delta }_1{\alpha }_k{c}_1{\Vert g_k\Vert }^2-{\delta }_2{c}_2^2{\Vert {\alpha }_k{g}_k\Vert }^2\\ \le C_k-\frac{{\delta }_1\mu c_1{\Vert g_k\Vert }^2}{\rho }-\frac{{\delta }_2{c}_2^2{\mu }^2{\Vert g_k\Vert }^2}{\rho }=C_k-\frac{\mu \left({\delta }_1{c}_1\rho +{\delta }_2{c}_2^2\mu \right)}{{\rho }^2}{\Vert g_k\Vert }^2\end{array}$

于是得证。

情况2：

$\rho {\alpha }_k<\mu$ 则由(2.5)有 ${\alpha }_k\ge \left(\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }\right)\frac{g_k^{\text{T}}{d}_k}{{\Vert d_k\Vert }^2}$。

则由(2.1)和(1.1)

$f_{k+1}\le C_k+{\delta }_1{\alpha }_k{g}_k^{\text{T}}{d}_k-{\delta }_2{\Vert {\alpha }_k{d}_k\Vert }^2$ 有：

$\begin{array}{c}{f}_{k+1}\le C_k+\frac{{\delta }_1\left({\delta }_1-1\right)}{\left(L+{\delta }_2\right)\rho }{\left(\frac{g_k^{\text{T}}{d}_k}{\Vert d_k\Vert }\right)}^2-{\delta }_2{\left(\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }\right)}^2\frac{{\left(\left|g_k^{\text{T}}{d}_k\right|\right)}^2}{{\Vert d_k\Vert }^2}\\ \le C_k+\frac{{\delta }_1\left({\delta }_1-1\right)}{\left(L+{\delta }_2\right)\rho }\frac{c_1^2}{c_2^2}{\Vert g_k\Vert }^2-{\delta }_2{\left(\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }\right)}^2\frac{c_1^2}{c_2^2}{\Vert g_k\Vert }^2\\ =C_k+\left[\frac{{\delta }_1\left({\delta }_1-1\right)}{\left(L+{\delta }_2\right)\rho }-{\delta }_2{\left(\frac{{\delta }_1-1}{\left(L+{\delta }_2\right)\rho }\right)}^2\right]\frac{c_1^2}{c_2^2}{\Vert g_k\Vert }^2\end{array}$

于是(2.5.2)得证。

由(1.2)：

$C_{k+1}=\frac{{\eta }_k{Q}_k{C}_k+f\left(x_{k+1}\right)}{Q{}_{k+1}}$， $Q_{k+1}={\eta }_k{Q}_k+1$

又 $f_{k+1}\le C_k-\beta {\Vert g_k\Vert }^2$ 有：

$C_{k+1}=\frac{{\eta }_k{Q}_k{C}_k+f\left(x_{k+1}\right)}{Q_{k+1}}\le \frac{{\eta }_k{Q}_k{C}_k+C_k-\beta {\Vert g_k\Vert }^2}{Q_{k+1}}=C_k-\frac{\beta {\Vert g_k\Vert }^2}{Q_{k+1}}$ (2.6)

由于f有下界且由 [2] 中引理(1.1)式，

$f_k\le C_k\le A_k$，我们可以得出 $C_k$ 有下界的结论，

由(2.6)可得 ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\frac{{\Vert g_k\Vert }^2}{Q_{k+1}}}<\infty$。如果 $\Vert g_k\Vert$ 在0附近则将违背此式，

因为由 [7] 中(2.14)，

$Q_{k+1}\le k+2$，于是 $\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0$ 成立。

如果 ${\eta }_{\max }<1$，那么由 [8] 中(1.8)：

$Q_{k+1}=1+{\displaystyle \underset{j=0}{\overset{k}{\sum }}{\displaystyle \underset{i=0}{\overset{j}{\prod }}{\eta }_{k-i}}}\le 1+{\displaystyle \underset{j=0}{\overset{k}{\sum }}{\eta }_{\max }^{j+1}}\le {\displaystyle \underset{j=0}{\overset{k}{\sum }}{\eta }_{\max }^j}=\frac{1}{1-{\eta }_{\max }}$

因此 $\underset{k\to \infty }{\lim }{g}_k=0$ 成立

于是得证。

4. 数值实验

实验环境：

硬件：R5 4600CPU、1650ti图形卡；

软件：VMware、Ubuntu系统、Matlab2016软件；

所有代码通过Matlab编程 [9]，本文算法以NMBFGS为代号。

相关参数取值如下：

${\delta }_1={\delta }_2=0.1$， $\rho =0.4$， $C={10}^{-6}$， $r=2$

通过选取一些问题 [8] 进行求解，和标准的BFGS [10] 方法、MBFGS方法进行对比，得出一些数值结果如下：

通过以上实验数据可以看出，相同的无约束优化问题在使用我们的新算法进行计算时，取得了较好的数值结果，和BFGS [10] 以及MBFGS [11] 方法相比，明显减少了迭代次数，对于计算函数值次数和求导次数也有明显减少。

5. 结论

在适当条件下我们证明了这个新的算法对于一些非凸函数具有全局收敛性一些得出的数值结果也表明，相较于传统的单调线搜索，我们这种新的非单调线搜索在数值性能上具有更好的表现。

参考文献