论文部分内容阅读
摘要：本文提出了一种新的求解无约束优化问题的共轭梯度算法。通过构造新的[θk]， 及[βk]公式，并由此给出一个具有充分下降性的方向，使得算法能够满足下降条件。我们在较弱的条件下证明下算法的全局收敛性。
关键词：无约束优化；共轭梯度法； Armijo线性搜索；全局收敛性
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）14-0191-02
1 概述
考虑无约束优化问题
[min f（x） ， x∈Rn] （1）
其中[f（x）：Rn→R]是连续可微函数.利用共轭梯度法可以有效求解问题（1），尤其对于大规模无约束优化问题。
共轭梯度法的迭代格式为[xk 1=xk αkdk]，其方向[dk]定义为：
[dk=-gk， k=0 -gk βkdk-1， k>0]， （2）
步长[αk]由线性搜索得到。
常用的线性搜索有精确线性搜索：求[αk]满足[f（xk αkdk）=min α>0f（xk αdk）]， Armijo线性搜索：给定[ρ∈（0，1）]，求[αk=max{ρi|j=0，1，2，…}]满足[f（xk αkdk）≤f（xk） δαkgTkdk]， Wolf线性搜索：求[αk]满足[f（xk αkdk）≤f（xk） δαkgTkdkdTkg（xk αkdk）≥σgTkdk]，其中[0<δ≤σ<1].有关这些线性搜索实现方式可参看文献[1]。
迭代式（2）中参数[βk]较著名的计算公式有：
[βHSk=gTk 1ykdTkyk，βFRk=||gk 1||2||gk||2，βPRPk=gTk 1yk||gk||2，βCDk=||gk 1||2-gTkdk，βLSk=gTk 1yk-gTkdk，βDYk=gTk 1ykdTkyk，]
其中[gk=?f（xk）]是函数[f]在[xk]点处的梯度，[yk=gk 1-gk]，[||?||]是欧式范数.
Al-Baali在文献[1]中证明，对于参数[σ<1/2]，FR方法在强Wolf线性搜索下非凸函数的全局收敛性，被认为数值效果最好的方法之一是PRP方法，但是对于一般非凸函数，PRP方法即使在采用精确线性搜索时也不能保证全局收敛，如Powell在文献[2]中给出的例子. 虽然FR方法有全局收敛性，但是在数值试验效果上不如PRP方法，同时HS方法以及文献[3]中给出的DY方法都有类似的情况.综合上述方法中的优点及剔除缺点，Touati-Ahmed和Storey在文献[4]中首先提出了混合PRP-FR方法；Gilbert和Nocedal在文献[5]中进一步研究混合PRP-FR方法，使得参数[βk]允许取负值. Dai和Yuan在文献[6]研究了混合DY-HS共轭梯度法，且在Wolf线性搜索下保证算法的收敛性。
我们称满足[gTkdk<0]的搜索方向[dk]为下降方向，称总是产生下降方向的算法为下降算法。本文的目的是构造一种具有充分下降性质且在较弱条件下保证全局收敛性的算法。
2 算法
本文构造一种新的[dk]迭代格式
[dk=-gk， k=0 -θkgk βTGkdk-1， k>0]， （3）
其中 [θk=2gTkdk-1dTk-1（gk 1-gk），]
[βTGk=2||gk||2dTk-1（gk 1-gk）-||gk||2gTkdk-1]. （4）
引理1假设方向[dk]由（3）产生，则对任意[k≥0]有
[gTkdk=-||gk||2] （5）
证 （i）当[k=0]时，结论显然成立。
（ii） 当[k>0]时，由式（3）知：
[gTkdk=-θkgk2 βTGkgTkdk-1= -2gTkdk-1dTk-1（gk 1-gk）gk2 （2gk2dTk-1（gk 1-gk）-gk2gTkdk-1）gTkdk-1=-gk2].
引理证明完毕。
下面给出求无约束优化问题的共轭梯度法的具体步骤。
算法 A：
步骤0给定常数[δ2]，[ε>0]，[δ1， α∈（0，1）].任意选取初始点[x0∈Rn]，令[k=0]。
步骤1按公式（3）计算[dk]，其中[θk]，[βTGk]由（4）确定.若[gk≤ε]，则停止；否则转步骤2。
步骤2按照如下线性搜索求步长[σk]，使[σk]为[1， α， α2， … ]中最大值满足：
[f（xk αkdk）≤f（xk） δ1σkgTkdk-δ2σkdk2] （6）
步骤3令[xk 1=xk σkdk]，[k=k 1]，转步骤1。
3 算法的良定分析和收敛性证明
在算法分析中需要假设[Ω]：
（a）水平集[L={x∈Rn|f（x）≤f（x0）}]有界，其中[x0]为初始点。
（b）存在[L]的一个邻域[B]。使[f]在[B]上连续可微，且梯度[g]满足Lipschitz条件，即存在常数
[L1>0]，对任意[x， y∈B]有不等式成立[g（x）-g（y）≤L1x-y]，[?x， y∈B].由假设[Ω]知，存在常数
[N>0]，[M>0]，对[?x∈B]下列不等式成立[x≤N]，[gk≤M]。
引理2存在常数[η>0]，使得下面不等式对任意充分大的[k]都成立
[σk≥ηgk2dk2] （8）
证 由（6）及假设[Ω]知[k≥0-δ1σkgTkdk δ2σkdk2<∞].由此及（5）可知[k≥0σ2kdk2<∞]，和 [k≥0αkgk2=-k≥0αkgTkdk<∞] （9）
特别地，[limk→∞δ2σkdk=0]，[limk→∞αkgk2=0]。
下面分两种情形证明（8）成立。
（i）当[σk=1].由（5），有[gk≤dk]，令[η=1]，则不等式（8）成立。
（ii）当[σk<1].由步骤2知[α-1σk]不满足不等式（6），那么就有下面不等式成立。
[f（xk α-1αkdk）>f（xk） δ1α-1σkgTkdk-δ2α-1σkdk2] （10）
由微积分中值定理和假设[Ω]知，存在[lk∈（0， 1）]使得：
[f（xk α-1αkdk）-f（xk）=α-1σkg（xk lkα-1σkdk）Tdk = α-1σkgTkdk α-1σk（g（xk lkα-1σkdk）-gk）Tdk ≤ α-1σkgTkdk L1α-2σ2kdk2]
将最后一个不等式代入式（10），得[σk>（1-δ1）αgk2（L1 δ2）dk2]
取[η=min{1， （1-δ1）αgk2（L1 δ2）dk2}]，则可知不等式（8）成立，引理证明完毕。
那么有引理2和式（9），即可得Zoutendijk..
引理3设目标函数满足假设[Ω]，序列[{xk}]由算法A产生，则[k≥0gk4dk2< ∞]
下面证明算法的全局收敛性。
定理1若假设[Ω]成立，[{xk}]和[{dk}]由算法A产生，则[limk→∞inf||gk||=0]。
证 利用反证法，假设结论不成立，则存在常数[c>0]，使得[||gk||≥][c]，[?k≥0].由式（3）知[gTkdk=-θkgk2 βTGkgTkdk-1]，因此有
[gTkdk-1=θk-1βTGkgk2] （11）
由式（3）和式（11）有
[dk2=θ2kgk2-2θkβTGkgTkdk-1 （βTGk）2dk-12= （2θk-θ2k）gk2 （βTGk）2dk-12]
因此有：
[dk2gk4=（βTGk）2dk-12gk4 （2θk-θ2k）1gk2= dk-12gk4-（θk-1）gk2 1gk2≤ dk-12gk4 1gk2 ≤ j=0k1gj2≤kc2].
上式等价于[gk4dk2≥c2k= ∞]，这与引理3矛盾，定理证明完毕。
参考文献：
[1] M.Al-Baali， Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMAJ. Number. Anal.， 1985（5）：121-124.
[2] Powell M J D. Nonconex Minimization calculations and the conjugate gradient method. Lecture Notes in Math.， 1984， 1066： 121-141.
[3] Dai Y H， Yuan Y X. A nonlinear conjugate gradient with a strong alobal convergence property. SIAM Journal of Optimization， 2000（10）： 177-182.
[4] Touati-Ahmed D， Storey C. Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl.， 1990，64： 379-397.
[5] Gilbert J C， Nocedal J. Global convergence properties of conjugate gradient method for optimization. SIAM. J. Optim.， 1992（2）： 21-42.
[6] Dai Y H， Yuan Y. An efficient hybrid conjugate gradient method for unconstrained optimization. Annals of Operations Research， 2001（103）： 33-47.
[7] 袁亚湘，孙文瑜. 最优化理论与方法[M]. 北京： 科学出版社，1995.
[9] 张丽.求解最优化问题的非线性共轭梯度法[D].湖南：湖南大学，2006.
关键词：无约束优化；共轭梯度法； Armijo线性搜索；全局收敛性
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）14-0191-02
1 概述
考虑无约束优化问题
[min f（x） ， x∈Rn] （1）
其中[f（x）：Rn→R]是连续可微函数.利用共轭梯度法可以有效求解问题（1），尤其对于大规模无约束优化问题。
共轭梯度法的迭代格式为[xk 1=xk αkdk]，其方向[dk]定义为：
[dk=-gk， k=0 -gk βkdk-1， k>0]， （2）
步长[αk]由线性搜索得到。
常用的线性搜索有精确线性搜索：求[αk]满足[f（xk αkdk）=min α>0f（xk αdk）]， Armijo线性搜索：给定[ρ∈（0，1）]，求[αk=max{ρi|j=0，1，2，…}]满足[f（xk αkdk）≤f（xk） δαkgTkdk]， Wolf线性搜索：求[αk]满足[f（xk αkdk）≤f（xk） δαkgTkdkdTkg（xk αkdk）≥σgTkdk]，其中[0<δ≤σ<1].有关这些线性搜索实现方式可参看文献[1]。
迭代式（2）中参数[βk]较著名的计算公式有：
[βHSk=gTk 1ykdTkyk，βFRk=||gk 1||2||gk||2，βPRPk=gTk 1yk||gk||2，βCDk=||gk 1||2-gTkdk，βLSk=gTk 1yk-gTkdk，βDYk=gTk 1ykdTkyk，]
其中[gk=?f（xk）]是函数[f]在[xk]点处的梯度，[yk=gk 1-gk]，[||?||]是欧式范数.
Al-Baali在文献[1]中证明，对于参数[σ<1/2]，FR方法在强Wolf线性搜索下非凸函数的全局收敛性，被认为数值效果最好的方法之一是PRP方法，但是对于一般非凸函数，PRP方法即使在采用精确线性搜索时也不能保证全局收敛，如Powell在文献[2]中给出的例子. 虽然FR方法有全局收敛性，但是在数值试验效果上不如PRP方法，同时HS方法以及文献[3]中给出的DY方法都有类似的情况.综合上述方法中的优点及剔除缺点，Touati-Ahmed和Storey在文献[4]中首先提出了混合PRP-FR方法；Gilbert和Nocedal在文献[5]中进一步研究混合PRP-FR方法，使得参数[βk]允许取负值. Dai和Yuan在文献[6]研究了混合DY-HS共轭梯度法，且在Wolf线性搜索下保证算法的收敛性。
我们称满足[gTkdk<0]的搜索方向[dk]为下降方向，称总是产生下降方向的算法为下降算法。本文的目的是构造一种具有充分下降性质且在较弱条件下保证全局收敛性的算法。
2 算法
本文构造一种新的[dk]迭代格式
[dk=-gk， k=0 -θkgk βTGkdk-1， k>0]， （3）
其中 [θk=2gTkdk-1dTk-1（gk 1-gk），]
[βTGk=2||gk||2dTk-1（gk 1-gk）-||gk||2gTkdk-1]. （4）
引理1假设方向[dk]由（3）产生，则对任意[k≥0]有
[gTkdk=-||gk||2] （5）
证 （i）当[k=0]时，结论显然成立。
（ii） 当[k>0]时，由式（3）知：
[gTkdk=-θkgk2 βTGkgTkdk-1= -2gTkdk-1dTk-1（gk 1-gk）gk2 （2gk2dTk-1（gk 1-gk）-gk2gTkdk-1）gTkdk-1=-gk2].
引理证明完毕。
下面给出求无约束优化问题的共轭梯度法的具体步骤。
算法 A：
步骤0给定常数[δ2]，[ε>0]，[δ1， α∈（0，1）].任意选取初始点[x0∈Rn]，令[k=0]。
步骤1按公式（3）计算[dk]，其中[θk]，[βTGk]由（4）确定.若[gk≤ε]，则停止；否则转步骤2。
步骤2按照如下线性搜索求步长[σk]，使[σk]为[1， α， α2， … ]中最大值满足：
[f（xk αkdk）≤f（xk） δ1σkgTkdk-δ2σkdk2] （6）
步骤3令[xk 1=xk σkdk]，[k=k 1]，转步骤1。
3 算法的良定分析和收敛性证明
在算法分析中需要假设[Ω]：
（a）水平集[L={x∈Rn|f（x）≤f（x0）}]有界，其中[x0]为初始点。
（b）存在[L]的一个邻域[B]。使[f]在[B]上连续可微，且梯度[g]满足Lipschitz条件，即存在常数
[L1>0]，对任意[x， y∈B]有不等式成立[g（x）-g（y）≤L1x-y]，[?x， y∈B].由假设[Ω]知，存在常数
[N>0]，[M>0]，对[?x∈B]下列不等式成立[x≤N]，[gk≤M]。
引理2存在常数[η>0]，使得下面不等式对任意充分大的[k]都成立
[σk≥ηgk2dk2] （8）
证 由（6）及假设[Ω]知[k≥0-δ1σkgTkdk δ2σkdk2<∞].由此及（5）可知[k≥0σ2kdk2<∞]，和 [k≥0αkgk2=-k≥0αkgTkdk<∞] （9）
特别地，[limk→∞δ2σkdk=0]，[limk→∞αkgk2=0]。
下面分两种情形证明（8）成立。
（i）当[σk=1].由（5），有[gk≤dk]，令[η=1]，则不等式（8）成立。
（ii）当[σk<1].由步骤2知[α-1σk]不满足不等式（6），那么就有下面不等式成立。
[f（xk α-1αkdk）>f（xk） δ1α-1σkgTkdk-δ2α-1σkdk2] （10）
由微积分中值定理和假设[Ω]知，存在[lk∈（0， 1）]使得：
[f（xk α-1αkdk）-f（xk）=α-1σkg（xk lkα-1σkdk）Tdk = α-1σkgTkdk α-1σk（g（xk lkα-1σkdk）-gk）Tdk ≤ α-1σkgTkdk L1α-2σ2kdk2]
将最后一个不等式代入式（10），得[σk>（1-δ1）αgk2（L1 δ2）dk2]
取[η=min{1， （1-δ1）αgk2（L1 δ2）dk2}]，则可知不等式（8）成立，引理证明完毕。
那么有引理2和式（9），即可得Zoutendijk..
引理3设目标函数满足假设[Ω]，序列[{xk}]由算法A产生，则[k≥0gk4dk2< ∞]
下面证明算法的全局收敛性。
定理1若假设[Ω]成立，[{xk}]和[{dk}]由算法A产生，则[limk→∞inf||gk||=0]。
证 利用反证法，假设结论不成立，则存在常数[c>0]，使得[||gk||≥][c]，[?k≥0].由式（3）知[gTkdk=-θkgk2 βTGkgTkdk-1]，因此有
[gTkdk-1=θk-1βTGkgk2] （11）
由式（3）和式（11）有
[dk2=θ2kgk2-2θkβTGkgTkdk-1 （βTGk）2dk-12= （2θk-θ2k）gk2 （βTGk）2dk-12]
因此有：
[dk2gk4=（βTGk）2dk-12gk4 （2θk-θ2k）1gk2= dk-12gk4-（θk-1）gk2 1gk2≤ dk-12gk4 1gk2 ≤ j=0k1gj2≤kc2].
上式等价于[gk4dk2≥c2k= ∞]，这与引理3矛盾，定理证明完毕。
参考文献：
[1] M.Al-Baali， Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMAJ. Number. Anal.， 1985（5）：121-124.
[2] Powell M J D. Nonconex Minimization calculations and the conjugate gradient method. Lecture Notes in Math.， 1984， 1066： 121-141.
[3] Dai Y H， Yuan Y X. A nonlinear conjugate gradient with a strong alobal convergence property. SIAM Journal of Optimization， 2000（10）： 177-182.
[4] Touati-Ahmed D， Storey C. Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl.， 1990，64： 379-397.
[5] Gilbert J C， Nocedal J. Global convergence properties of conjugate gradient method for optimization. SIAM. J. Optim.， 1992（2）： 21-42.
[6] Dai Y H， Yuan Y. An efficient hybrid conjugate gradient method for unconstrained optimization. Annals of Operations Research， 2001（103）： 33-47.
[7] 袁亚湘，孙文瑜. 最优化理论与方法[M]. 北京： 科学出版社，1995.
[9] 张丽.求解最优化问题的非线性共轭梯度法[D].湖南：湖南大学，2006.