考虑无约束优化问题:

$ {\rm{min}}\;\;f\left( x \right),\;\;\;\;x \in {R^n}, $

(1)

其中 $f(x):R^n\longrightarrow R$为连续可微函数.求解问题(1) 的算法主要是迭代法, 其基本格式为

$ x_{k+1}=x_k+\alpha _k d_k, $

其中 $d_k$为 $f(x)$在 $x_k$点的搜索方向, $\alpha_k$为 $f(x)$沿此方向上的搜索步长.

共轭梯度法是求解无约束优化问题最常用的方法之一^{[1, 2]}.此类算法有效避免了计算和存储矩阵, 是求解大规模优化问题的有效方法之一, 但很多共轭梯度法不具有全局收敛性^[2].记忆梯度法是共轭梯度法的推广和改进, 此类算法充分利用前面迭代点的信息来产生新的迭代点, 不用计算和存储矩阵, 算法简单, 适于求解大规模优化问题, 并且与共轭梯度法相比, 记忆梯度法增加了参数选择的自由度, 更有利于构造稳定的快速收敛算法^[3-6].

另一方面, 文献[7]提出一种曲线搜索算法, 这种算法沿一条曲线搜索新的迭代点, 每次迭代时同时确定下降方向和步长, 这样可以使算法更容易找到合适的步长.利用曲线搜索技巧可以保证算法具有全局收敛性和较快的收敛速度^[7-9].

本文在文献[3-9]的基础上给出一个新的求解无约束优化问题的下降方法, 在较弱条件下证明了其全局收敛性和线性收敛速率.算法利用当前和前面迭代点的信息以及曲线搜索技巧产生下一个迭代点, 并且不需计算和存储矩阵, 适于求解大规模优化问题.初步的数值试验表明算法是有效的.

在本文中, 设 $g(x)$为 $f(x)$的梯度, 并且简记 $g(x_k)$为 $g_k$, $f(x_k)$为 $f_k$, $f(x^*)$为 $f^*$.

本文采用如下曲线搜索准则:

曲线搜索准则  取 $0 < \mu_1 < \frac{1}{2} < \mu_2 < 1, s_k>0$, 要求 $\alpha_k$满足

$ f(x_k)-f(x_k+\alpha d_k(\alpha))\geq -\mu_1\alpha g_k^{\scriptsize\rm{T}}d_k(\alpha), $

(2)

$ g(x_k+\alpha d_k(\alpha))^{\scriptsize\rm{T}}d_k(\alpha)\geq \mu_2g_k^{\scriptsize\rm{T}}d_k(\alpha), $

(3)

这里

$ d_k(\alpha)=\left\{ \begin{array}{c} -g_{k}, \ \ \ \ \ \ \ \ \ \ \ \ &k=1, \\ -\alpha g_{k}+\alpha s_kg_{k-1},\ \ &k\geq 2. \end{array} \right. $

(4)

算法(A)  取 $0 < \mu_1 < \frac{1}{2} < \mu_2 < 1, \rho\in(0, 1), x_1\in R^n.$令 $k:=1.$

步骤1  若 $||g_k||=0$, 则停止迭代; 否则, 转步骤2.

步骤2   $x_{k+1}=x_k+\alpha_k d_k(\alpha_k)$, 这里 $\alpha_k$由曲线搜索准则确定, 而

$ d_k(\alpha_k)=\left\{ \begin{array}{c} -g_{k}, \ \ \ \ \ \ \ \ \ \ \ \ &k=1, \\ -\alpha_k g_{k}+\alpha_k s_kg_{k-1},\ \ \ &k\geq 2, \end{array} \right. $

(5)

其中

$ s_k= \frac{\rho||g_k||}{||g_{k-1}||}. $

(6)

步骤3  令 $k:=k+1$, 转步骤1.

算法(A)有下面两个性质.

引理2.1  对任意的 $k\geq2$, 有 $-g_k^{\scriptsize\rm{T}}d_k(\alpha_k)\geq\alpha_k(1-\rho)||g_k||^2.$

引理2.2  对任意的 $k\geq2$, 有 $||d_k(\alpha_k)||\leq \alpha_k(1+\rho)||g_k||.$

为了下面证明的需要, 本文作如下假设:

(H₁)目标函数 $f(x)$在水平集 $L_0=\{x\in R^n|f(x)\leq f(x_1)\}$上有下界.

(H₂)梯度函数 $g(x)$在包含 $L_0$的开凸集 $B$上一致连续.

引理3.1  若(H₁)和(H₂)成立, $\{x_k\}$是由算法(A)产生的迭代点列, 则 $\{||d_k(\alpha_k)||\}$和 $\{||g_k||\}$都有界.

证  由引理2.2可知只需证明 $\{||g_k||\}$有界.假设 $\{||g_k||\}$无界, 则存在无穷子列 $N\subset\{1, 2, \cdots\}$使

$ ||g_k||\rightarrow+\infty, (k\in N, k\rightarrow+\infty). $

(7)

由(2) 式和引理2.1知

$ f_k-f_{k+1}\geq -\mu_1\alpha_k g_k^{\scriptsize\rm{T}}d_k(\alpha_k)\geq\mu_1(1-\rho)\alpha_k^2||g_k||^2. $

(8)

因为 $\{f_k\}$单调不增且有下界, 故知 $\{f_k\}$有极限, 从而由(8) 式知

$ \sum \limits_{k\in N }\limits^{\infty}\alpha_k^2||g_k||^2 < \sum \limits_{k=2}\limits^{\infty}\alpha_k^2||g_k||^2 < +\infty. $

(9)

因此

$ \alpha_k^2||g_k||^2\rightarrow0(k\in N, k\rightarrow+\infty). $

(10)

由(7) 和(10) 式可知

$ \alpha_k^2||g_k||\rightarrow0(k\in N, k\rightarrow+\infty). $

(11)

由引理2.2可得 $\alpha_k||d_k(\alpha_k)||\leq \alpha_k^2(1+\rho)||g_k||$, 从而由(11) 式可得

$ \alpha_k||d_k(\alpha_k)||\rightarrow0(k\in N, k\rightarrow+\infty). $

(12)

由(3) 式, 引理2.1及引理2.2可得

$ \begin{eqnarray*} ||g(x_{k+1})-g(x_k)|| &\geq&\frac{(g_{k+1}-g_k)^{\scriptsize\rm{T}}d_k(\alpha_k)}{||d_k(\alpha_k)||}\\ &\geq&\frac{(\mu_2-1)g_k^{\scriptsize\rm{T}}d_k(\alpha_k)}{||d_k(\alpha_k)||}\\ &\geq&\frac{(1-\mu_2)(1-\rho)\alpha_k||g_k||^2}{||d_k(\alpha_k)||}\\ &\geq&\frac{(1-\mu_2)(1-\rho)||g_k||}{1+\rho}, \end{eqnarray*} $

从而由 $(H_2)$和(12) 式可得 $||g_k||\rightarrow0(k\in N, k\rightarrow+\infty), $这与(7) 式矛盾.

定理3.1  假设(H₁)和(H₂)成立, $\{x_k\}$是由算法(A)产生的迭代点列, 则 $\lim\limits_{k\rightarrow\infty}||g_k||=0.$

证  假设 $\lim\limits_{k\rightarrow\infty}||g_k||\neq0$, 则存在无穷子列 $K \subset\{1, 2, \cdots\}$及 $\vartheta>0$有

$ ||g_k||>\epsilon, \forall k\in K. $

(13)

由(9) 和(13) 式知

$ \sum \limits_{k\in K }\limits^{\infty}\alpha_k^2\epsilon^2 < \sum \limits_{k\in K }\limits^{\infty}\alpha_k^2||g_k||^2 < \sum \limits_{k=2 }\limits^{\infty}\alpha_k^2||g_k||^2 < +\infty, $

(14)

从而知 $\alpha_k\rightarrow0 (k\in K, k\rightarrow+\infty)$.又因为 $\{||d_k(\alpha_k)||\}$有界, 故知

$ \alpha_k||d_k(\alpha_k)||\rightarrow0, (k\in K, k\rightarrow+\infty). $

(15)

由引理3.1的证明过程可知

$ ||g(x_{k+1})-g(x_k)|| \geq\frac{(1-\mu_2)(1-\rho)||g_k||}{1+\rho}, $

(16)

从而由 $(H_2)$, (15) 和(16) 式知

$ ||g_k||\rightarrow0, (k\in K, k\rightarrow+\infty), $

(17)

这与(13) 矛盾.因此 $\lim\limits_{k\rightarrow\infty}||g_k||=0.$

假设(H₃): $f(x)$是二次连续可微的一致凸函数.

引理4.1^[3]  若(H₃)成立, 则(H₁)和(H₂)成立, $f(x)$有唯一的极小点 $x^*$, 且存在 $M\geq m>0, $使

$ \frac{m}{2}||x-x^*||^2\leq f(x)-f(x^*)\leq \frac{M}{2}||x-x^*||^2, \\ m||x-x^*||\leq ||g(x)||\leq M||x-x^*||. $

此外, $g(x)$在水平集 $L_0$上Lipschitz连续, 即存在常数 $L>0$, 使

$ || g(x)-g(y)||\leq L||x-y||, \forall x, y\in L_0. $

(18)

定理4.1  若(H₃)成立, $\{x_k\}$是由算法(A)产生的无穷点列, 则 $\{x_k\}$至少线性收敛于 $x^*$.

证  由引理3.1的证明过程可知

$ f_k-f_{k+1}\geq -\mu_1\alpha_k g_k^{\scriptsize\rm{T}}d_k(\alpha)\geq\mu_1 (1-\rho)\alpha_k^2||g_k||^2, $

(19)

并且

$ ||g(x_{k+1})-g(x_k)|| \geq\frac{(1-\mu_2)(1-\rho)||g_k||}{1+\rho}. $

(20)

由(18) 和(20) 式可知

$ \alpha_kL||d_k(\alpha_k)||\geq||g(x_k+\alpha_kd_k(\alpha_k))-g_k|| \geq \frac{(1-\mu_2)(1-\rho)||g_k||}{1+\rho}, $

从而由引理2.2可得

$ \label{e2}\alpha_k^2\geq \frac{(1-\mu_2)(1-\rho)}{L(1+\rho)}\frac{||g_k||\alpha_k}{||d_k(\alpha_k)||} \geq\frac{(1-\mu_2)(1-\rho)}{(L+1)(1+\rho)^2}. $

(21)

由(19) 和(21) 式可得

$ f_k-f_{k+1}\geq \frac{\mu_1(1-\mu_2)(1-\rho)^2}{(L+1)(1+\rho)^2}||g_k||^2. $

(22)

令 $\lambda=\frac{\mu_1(1-\mu_2)(1-\rho)^2}{(L+1)(1+\rho)^2}, $则 $0 < \lambda < \frac{1}{2}, $并且有

$ f_k-f_{k+1}\geq\lambda||g_k||^2. $

(23)

定理余下的证明类似于文献[3]中的定理3, 在此省略.

算法(A)采用的是一种类似于Wolfe线性搜索的曲线搜索准则.我们也可以采用下面类似于Armijo线性搜索的曲线搜索准则.

新的曲线搜索准则  选取 $\alpha_k$为 $\{1, \beta^2, \beta^3, \cdots \}$中满足下式的最大者

$ f(x_k)-f(x_k+\alpha d_k(\alpha))\geq -\sigma\alpha g_k^{\scriptsize\rm{T}}d_k(\alpha), $

这里 $\beta\in (0, 1)$, $\sigma\in (0, \frac{1}{2})$, 而 $d_k(\alpha)$由(4) 式给出.类似于文献[5]中的定理3.1和定理4.1的证明过程, 我们可以得到下面两个结论.

定理5.1  假设(H₁)和(H₂)成立且算法(A)采用新的曲线搜索准则, 则算法(A)或有限步终止于问题(1) 的稳定点; 或产生无穷点列 $\{x_k\}$, 其任意聚点都是问题(1) 的稳定点.

定理5.2  假设(H₃)成立且算法(A)采用新的曲线搜索准则, 如果 $\{x_k\}$是由算法(A)产生的无穷点列, 则 $\{x_k\}$至少线性收敛于 $x^*$.

此外, 算法(A)只利用了当前和前面一步迭代点的信息, 这在算法的设计中似乎是一种信息浪费.因此, 我们可以利用前面多步迭代点的信息来产生新的迭代点, 即采用下多步曲线搜索准则.

多步曲线搜索准则  取 $0 < \mu_1 < \frac{1}{2} < \mu_2 < 1, $ $m\geq3$是一个正整数, 要求 $\alpha_k$满足

$ f(x_k)-f(x_k+\alpha d_k(\alpha))\geq -\mu_1\alpha g_k^{\scriptsize\rm{T}}d_k(\alpha), \\ g(x_k+\alpha d_k(\alpha))^{\scriptsize\rm{T}}d_k(\alpha)\geq \mu_2g_k^{\scriptsize\rm{T}}d_k(\alpha), $

这里

$ d_k(\alpha)=\left\{ \begin{array}{ll}-g_{k}, \ &k\leq m-1, \\ -\alpha g_{k}+\alpha s_k\sum\limits_{i=2}\limits^{m}g_{k-i+1}, \ &k\geq m, \end{array} \right. $

其中

$ s_k=\left\{ \begin{array}{ll} 1, \ \ \ &k\leq m-1, \\ \frac{\rho||g_k||}{\sum\limits_{i=2}\limits^{m}||g_{k-i+1}||}, \ &k\geq m. \end{array} \right. $

类似于定理3.1和定理4.1的证明过程, 我们可以证明当算法(A)采用多步曲线搜索准则时仍具有全局收敛性和线性收敛速率.

为检验算法(A)的实算效果, 我们选取几个算例对本文算法进行数值试验, 并与共轭梯度法和最速下降法进行比较.

例1   $f(x)=(x_1-1)^2+(x_1-x_2)^2+(x_2-x_3)^4, x_0=(-3, 1, 2)^{\scriptsize\rm{T}}, x^*=(1, 1, 1)^{\scriptsize\rm{T}}, f^*=0.$

例2   $f(x)=(1-x_1)^2+(1-x_{10})^2+\sum \limits_{i=1}\limits^{9}(x_i^2-x_{i+1})^2, x_0=(3, 2, \cdots, 3, 2)^{\scriptsize\rm{T}}, x^*=(1, \cdots, 1)^{\scriptsize\rm{T}}, f^*=0.$

例3   $f(x)=(x_1+10x_2)^4+5(x_3-x_4)^4+(x_2-2x_3)^4+10(x_1-x_4)^4, x_0=(-2, 4, -2, 4)^{\scriptsize\rm{T}}, x^*=(0, 0, 0, 0)^{\scriptsize\rm{T}}, f^*=0.$

例4   $f(x)=(x_1-1)^2+(x_1-x_2)^2+(x_3-1)^2+(x_4-1)^4+(x_5-1)^6, x_0=(0, 1, 0, 1, 0)^{\scriptsize\rm{T}}, x^*=(1, 1, 1, 1, 1)^{\scriptsize\rm{T}}, f^*=0.$

例5   $f(x)=(x_1-x_2)^2+(x_2+x_3-2)^2+(x_4-1)^2+(x_5-1)^2, x_0=(-3, 3, -3, 3, -3)^{\scriptsize\rm{T}}, x^*=(1, 1, 1, 1, 1)^{\scriptsize\rm{T}}, f^*=0.$

我们用EX表示算例, NA表示算法(A), 用FR, PRP和LS分别表示FR, PRP和LS共轭梯度法^[2], SM表示最速下降法.在试验中, 共轭梯度法及最速下降法均采用如下Wolfe线性搜索准则.

Wolfe线性搜索准则  取 $0 < \mu_1 < \frac{1}{2} < \mu_2 < 1$, 计算 $\alpha_k$使其满足

$ f(x_k)-f(x_k+\alpha d_k) \geq -\mu_1\alpha g_k^{\scriptsize\rm{T}}d_k, g(x_k+\alpha d_k)^{\scriptsize\rm{T}}d_k\geq \mu_2g_k^{\scriptsize\rm{T}}d_k. $

参数取值为 $\mu_1=0.15, \mu_2=0.88, \rho=0.25$.精度设为 $|f_k-f^*|\leq {\rm eps}$.表格1中的数字为达到相应精度时算法的迭代次数, 表格2中的数字为算法迭代所需的时间(单位:秒).计算结果如下.

从以上数值试验及比较的结果可以看出, 当达到同一精度时, 本文提出的新算法所需的迭代次数及时间都比FR, PRP和LS共轭梯度法及最速下降法少, 表明新算法是有效的.