下载: -
考虑无约束优化问题：
其中目标函数f：
${{\mathbb{R}}^{n}}\to \mathbb{R}$ 连续可微，梯度函数g(x)$\triangleq $ ∇f(x)，gk$\triangleq $ g(xk)，fk$\triangleq $ f(xk).共轭梯度法是求解大型优化问题(1) 的一种有效方法，迭代格式如下其中：dk为搜索方向，αk为步长因子，βk为共轭方向调控参数.共轭参数的选取影响着算法的收敛性和计算效果.著名的共轭梯度法PRP，FR的βk表达式如下
其中‖·‖为欧氏范数. PRP方法具备优秀的数值特性，但即使采用精确线搜索，对非凸目标函数仍不能确保其收敛性[1]，不少研究者对βkPRP公式作了非负性的改进[2-6]，解决了收敛性问题.文献[3]对βkPRP公式修改得到
0≤βkWYL≤2βkFR，WYL方法继承了PRP方法优秀的数值特性.文献[6]对公式(4) 再修改得到
0≤βkVPRP≤βkFR，βkVPRP与βkWYL一样满足文献[2]为PRP方法提出的性质(*)，文献[7]还将公式(5) 的分子部分推广到其他共轭梯度法公式上，也取得了较好的效果.
基于文献[3, 6]的思路，本文考虑对βkPRP公式作如下改进
易得0≤βk≤2βkFR，但βk不再满足性质(*).受文献[8]的启发，对公式(6) 再修正得到
其中
建立在参数βkN公式上的相应共轭梯度算法和谱共轭梯度算法具有良好的收敛性和较为理想的数值表现.
全文HTML
-
基于参数公式(7)，采用强Wolfe-Powell线搜索(SWP)的修正PRP共轭梯度算法如下：
算法1
步骤1 给定初值
${{\mathit{\boldsymbol{x}}}_{1}}\in {{\mathbb{R}}^{n}}$ ，δ∈(0，0. 5)，σ∈(δ，0. 5)，μ≥1，ε≥0，d1：=-g1，k：=1.若‖gk‖≤ε，停止.步骤2 计算步长αk满足以下SWP线搜索准则：
步骤3 计算xk+1=xk+αkdk.若‖gk+1‖≤ε，停止.
步骤4 由(7) 式计算参数βk+1，由(3) 式计算dk+1.
步骤5 k：=k+1，转步骤2.
谱共轭梯度法是一种特殊共轭梯度法[9]，通过调整谱参数θk和共轭参数βk，易使设计的算法满足下降性和收敛性.为降低线搜索条件，受文献[10-16]的启发，设计基于参数公式(7) 并采用弱Wolfe-Powell线搜索(WWP)的修正PRP谱共轭梯度算法如下：
算法2
步骤1 给定初值
${{x}_{1}}\in {{\mathbb{R}}^{n}}$ ，δ∈(0，0. 5)，σ∈(δ，0. 5)，μ≥1，ε≥0，d1：=-g1，k：=1.若‖gk‖≤ε，停止.步骤2 计算步长αk满足WWP线搜索准则：(8) 式和下式
步骤3 计算xk+1=xk+αkdk.若‖gk+1‖≤ε，停止.
步骤4 由(7) 式计算参数βk+1，由下式计算搜索方向dk+1：
其中
步骤5 k：=k+1，转步骤2.
算法的收敛性证明需要共轭梯度法的常规假设条件：
(ⅰ)设水平集Ω={
$\mathit{\boldsymbol{x}}\in {{\mathbb{R}}^{n}}$ |f(x)≤f(x1)}有界，其中x1为初始点.(ⅱ) f(x)在Ω的某邻域N上连续可微且导数满足Lipschitz条件，即存在常数L＞0，使得
本文以下算法的收敛性分析中均假设‖gk‖≠0，否则目标函数的稳定点已获得，算法自动终止.
-
引理1 考虑参数
$\sigma \in \left( 0,\frac{1}{2} \right)$ ，μ≥1，则存在常数${{c}_{1}}=\frac{1-2\sigma }{1-\sigma }\in \left( 0,1 \right),{{c}_{2}}=\frac{1}{1-\sigma }\in \left( 1,2 \right)$ ，使算法1产生的方向序列{dk}满足充分下降条件证 因βkN的调比因子
所以由(7) 式，可知
当k=1时，d1=-g1，g1Td1=-‖g1‖2，显然(13) 式成立.假设k＞1时(13) 式成立，则gkTdk＜0.
(3) 式两端与gk+1T作内积，并利用(9) 和(14) 式，可得
利用(15) 式及(14) 式，可得
上式两边除以-‖gk+1‖2，可得
利用(16) 式递推，可得
由归纳法知，引理成立.
由引理1及文献[1]引理1.4.1，可得以下引理.
引理2 若假设(ⅰ)，(ⅱ)成立，则算法1产生的序列{gk，dk}满足Zoutendijk条件：
$\sum\limits_{k\ge 1}{\frac{{{\left\| {{\mathit{\boldsymbol{g}}}_{k}} \right\|}^{4}}}{{{\left\| {{\mathit{\boldsymbol{d}}}_{k}} \right\|}^{2}}}}＜+\infty $ .定理1 若假设(ⅰ)，(ⅱ)成立，{gk}为算法1产生的序列，则有
证若定理结论不成立，即
则存在常量γ＞0，使得
(3) 式两端取模平方，可得
(18) 式两边除以‖gk‖4，再由(9) 式和(13)，(14)，(17) 式，可得
由(19) 式，可得
-
引理3 考虑算法2产生的序列{gk，dk，βkN}，则∀k≥1有
证 当k=1时，d1=-g1，则g1Td1=-‖g1‖2＜0.假设k≥1时gkTdk＜0，从而由(10) 与(12) 式得dkTyk≥(σ-1)gkTdk＞0.下证gk+1Tdk+1＜0.
(11) 式两端与gk+1作内积，可得
由(14) 式知0≤βk+1N≤βk+1FR.若βk+1N＞0，则上式可得
若βk+1=0，则结合dkTyk＞0可得
由归纳法知，∀k≥1，gkTdk＜0成立.再由(21) 式可得
引理得证.
引理3说明算法2产生的搜索方向dk满足下降性.根据文献[1]引理1.4.1，易得以下结论.
引理4 若假设(ⅰ)，(ⅱ)成立，{gk，dk}为算法2产生的序列，则
定理2 若假设(ⅰ)，(ⅱ)成立，{gk}为算法2生成的序列，则有
证 若定理不成立，则存在常数r＞0，使任意k≥1有‖gk‖≥r.
由(11) 式移项得dk+θkgk=βkdk-1，两端取模平方，再除以(gkTdk)2，并利用(20) 式，可得
从而可得
上式与引理4矛盾，由反证法知定理成立.
-
为检验本文提出的修正PRP共轭梯度法的计算效果，给出算法1和算法2的数值实验结果如表 1.测试函数源于文献[17]，算法运行环境为Matlab 2011b和Windows7操作系统.终止条件为‖gk‖≤10-6，或迭代次数超过9 999. 表 1中NI/NF/NG分别表示算法迭代次数、目标函数计算迭代次数、梯度函数计算迭代次数，其它符号说明如下：
算法1中参数μ=1.15，δ=0.001，σ=0.25；算法2中参数μ=4.2，δ=0.1，σ=0.9；PRP与VPRP采用SWP线搜索，δ=0.001，σ=0.25.
本文对PRP公式进行非负修正并添加适当的调比因子.基于新参数公式的两个算法分别适用SWP和WWP步长线搜索，具有良好的收敛性.虽然新参数βkN不再满足性质(*)，但数值实验结果显示算法1优于表中其他方法，能解决更多的问题.同时，谱共轭梯度形式的算法2比标准共轭梯度形式的算法1收敛条件弱，但计算效果却没算法1好，如何调整两个方向调控参数，使谱共轭梯度算法达到更佳的计算效果，需要进一步的研究.