下载: -
考虑如下无约束最优化问题
其中：x为决策变量，目标函数f：
${{\mathbb{R}}^{n}}\to \mathbb{R}$ 是连续可微函数.共轭梯度法是解决上述无约束优化问题的常用方法.由于其迭代简单，储存量低，所以常用于解决大规模优化问题.其基本迭代格式为其中：αk是步长，dk是搜索方向. dk的基本迭代格式为
记g(xk)=∇f(xk)，βk为标量，关于βk的计算有多种形式，不同的βk对应着不同的共轭梯度算法.一些著名的βk公式有：
其中：yk-1=gk-gk-1，‖·‖表示Euclid范数.关于这6种著名的共轭梯度法的详细内容可以参考文献[1-7].
本文主要研究一种FR型共轭梯度方法.众所周知FR方法是求解无约束优化问题最有效的方法之一.文献[8]首先证明了FR方法在精确线搜索下对一般非线性函数是全局收敛的，由于精确线搜索代价比较大，所以在实际的计算中人们通常使用非精确线搜索.例如文献[9]首先给出了在非精确线搜索下的非线性共轭梯度算法的全局收敛性结果，并证明了在强Wolfe线搜索下，当
$\sigma ＜ \frac{1}{2}$ 时FR方法满足充分下降性条件，同时全局收敛.文献[10-11]进一步将上面的收敛结果推广到$\sigma = \frac{1}{2}$ 的情形.后来许多学者开始对FR方法产生了兴趣，做出了对FR方法的修正以及变形，得到了比较好的结果.例如文献[12]推广了FR方法，得到了一种修正的FR型共轭梯度方法，其中βk为本文在文献[12]的基础之上，进一步研究FR型方法，提出了另外一种修正的FR型共轭梯度方法，改进的修正FR型公式记为βkXMFR，
其中u＞1.在Wolfe线搜索下证明了其全局收敛性.
在证明算法的全局收敛性时，一般采用Wolfe线搜索来计算步长αk，即典型的Wolfe非精确线搜索为：
其中δ和σ是满足0＜δ＜σ＜1的常数.
全文HTML
-
算法1
步骤1 初始化.给定初始点
${{\mathit{\boldsymbol{x}}}_{1}}\in {{\mathbb{R}}^{n}}$ ，u＞1，令d1=-g1，k：=1，设${{a}_{1}}=\frac{1}{\left\| {{\mathit{\boldsymbol{g}}}_{1}} \right\|}$ ，如果‖g1‖≤ε，则停止.步骤2 线搜索.计算步长αk，使得αk满足Wolfe非精确线搜索(6).
步骤3 令xk+1=xk+αkdk，gk+1=g(xk+1).如果‖gk+1‖≤ε，则停止.
步骤4 计算dk，dk满足(3) 和(5) 式.如果Powell重开始条件
成立，则重新开始，令
计算
步骤5 令k：=k+1，转步骤2.
首先，在无任何线搜索条件下证明由(3) 和(5) 式所确定的方向满足充分下降条件
定理1 考虑(2) 和(3) 式的迭代方法，βk由(5) 式产生，u＞1，对任意k≥1，总有下式成立
证 若gkTdk-1=0，则由gk与(3) 式两端作内积得：
则(7) 式显然成立.
若gkTdk-1≠0，则有
因此，对所有的k≥1，(7) 式总是成立的.
定理2 对于所有的k≥1，参数βkXMFR满足
$0\le \beta _{k}^{\rm{XMFR}}\le \frac{{{\left\| {{\mathit{\boldsymbol{g}}}_{k}} \right\|}^{2}}}{{{\left\| {{\mathit{\boldsymbol{g}}}_{k-1}} \right\|}^{2}}}$ .证 根据βkXMFR的定义，有
其中θk是gk和dk-1的夹角.
另一方面，由于
所以有
因此，结论是成立的.
-
为了获得算法1的全局收敛性，需要下面两个常用的假设：
(H1) 假设目标函数f(x)在水平集E={
$\mathit{\boldsymbol{x}}\in {{\mathbb{R}}^{n}}$ |f(x)≤f(x1)}上有界，其中x1为算法初始点.(H2) 在E的某个邻域N内，目标函数f(x)连续可微且梯度函数g(x)满足Lipschitz条件，即存在常数L＞0，使得
引理1[13] 设目标函数f(x)满足(H1)和(H2)，{xk}由(2) 和(3) 式产生，dk满足下降方向，αk满足Wolfe线搜索，则有
根据(7) 式可得
假设(H1)，(H2) 成立，迭代序列{xk}由(2) 和(3) 式产生，{gk}为算法产生的序列，则有
证 利用反证法来证，假设结论不成立，则存在常数γ＞0，使得
对(3) 式两端取模平方得：
由于
可得
从而有
(9) 式两端都除以‖gk‖4得
进而有
因此
由此可知
这与(8) 式矛盾.因此结论成立.
-
为了验证提出的新共轭梯度算法的有效性，从文献[14]中选取几个测试函数测试，并与FR方法和MFR方法做比较，程序代码用Matlab编写.测试的环境为Matlab7.10.0，Win7.0操作系统，Intel(R) Core(TM) i5-2450M CPU @ 2.50 GHz 2.00 GB内存.参数的选取为：δ=0.001，σ=0.1，u=1.1.算法的终止条件为：
3种算法的实验结果见表 1，其中Dim为测试函数的维数；NI为迭代次数；NF为函数值计算的次数；NG为函数梯度计算的次数.
从表 1可知，本文算法数值性能最好.