资源描述：
《大型稀疏无约束最优化问题的行列修正算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、大型稀疏无约束最优化问题的行列修正算法第12卷A辑第1期1997年3月高校应用数学App1.Math.——JCUV01.12Ser.ANO.1March1997lc『大型稀疏无约束最优化问题的行列修正算法'王德人杨永健(上海大学)(二)2Z摘要n本文提出7一类适用于大型稀疏最优化问题的简单易行的行列修正算法,获得了新算法的局部超线性收敛性,大量的数值试骚表明这是一个较为理想的修正算法.新算法同样可以用来求解大型对称非线性方程组.关键词.垄查墨,对称{壅之组,竺型竺兰兰兰分类号(中图)o241.7;(1991MR)90C30,49M10..§1引言最往
2、如果利用Newton法求解无约束最优化问题minf(z),flR一R(11)E矿需要计算,的海色阵及其逆阵,工作量十分巨大.着名的拟一Newton法以各种修正矩阵去近似替代海色阵或它的逆阵,算法的计算复杂性明显下降.但是,对于大型稀疏问题,这些修正算法并无原稀疏结构的传递性,需要对修正矩阵作较为复杂的改造.为此,许多作者曾作过精心的研究.本文提出了一类适用于大型稀疏最优化问题的简单易行的行列修正算法,其修正矩阵同样满足拟一Newton方程,每次修正的函数求值次数与PSB,DFP,BFGS等着名的修正算法相同,但是,这类新修正阵保持了原有对称与稀疏结构
3、的传递性,而且取得了最省的组合代价.在一定的条件下,获得了新算法的局部超线性收敛速度,大量数值试验表明这是一个较*本文1005年12月15日收到国家自然科学基金资助项目高校应用数学第12卷A辑为理想的修正算法.我们还把此新算法用于大型对称非线性方程组中,同样取得了十分满意的数值效果.§2算法与复杂性分析为讨论方便,我们设函数,二次连续可微.其梯度记为V/()一F(),FI—,而,的海色阵,记为H()一V0/()一F(),FlR.一L(R).因此,由最优性条件,问题(1.1)可直接考虑为对称非线性方程组F()一0,FI—(2.1)的求解.对此,我们构造
4、了下面的新算法:[算法RCUMM11.给定初始近似,岛;2.对于一0,1,2,…,计算一一F(一),3.对于一0.1,2,…,取^一Argmax{f(,)forf(,F(z'))f},J∈{1,2,….}}.且取正常数口,使满足f()f≥(口f(ej,sDf)}4.构造修正矩阵B,一0,1,2.…,BH1一BI+(yi～且)矗+ejk(Y~一且)(一且)【一一¨一一,Y^=,(一¨)一F(一).5.在误差范围内收敛,停机.修正矩阵且+的形成,是按照指标^的选择规则,在且中的第^行用酗+一号《(2.s)替代,第^列用Bk%+一专cz.替代.此时,按(2
5、.2)构成且+,只需计算个函数值及+2(+1)个乘法运算,乘法运算次数太大小于PSB,DFP-BFGS等修正,而函数值的计算次数仪为文[7]中算法的一半.因此.本文提出的修正算法(RCUMM)具有较低的计算复杂性,而且对于矩阵F0)仍有较好的近似性质.因为获们容易验证修正矩阵(2.2)同样满足拟一Newton方程+1一Yt,一0,1,….如果矩阵F)V∈具有稀疏性,则获们可以根据F()的稀疏结构,在修正稀疏矩阵且时,只需将(2.3)中的向量第1期王德人,杨永健:太型稀疏无约束最优化问趣的行列修正算法87坼一一号《对照且的稀疏模式,施行非零元素零化手续
6、,并将此记为.此时,矩阵岛+的第^行成为《岛+一《+,而岛+的第^列,则成为B十一B墀+毽,如此所得的修正矩阵且+与矩阵取具有完全相同稀疏结构,计算过程十分方便.所以,利用上述算法去求解大型稀疏无约束最优化问题或大型对称非线性方程组,无论从程序设计或是从计算复杂性去评价,都是十分有利的,大量数值试验亦充分显示了新算法的优越性.§3数值试验在进行算法的理论分析之前,我们先以大量数值倒子说明新算法RCUMM的有效性.对于无约束最优化问题的例子,找们选择了以下几个检验函数,并与PSB算法进行比较,结果是满意的.1,计算函数,(z):∑0)的最优解,其中E一
7、10)一(一2)'+(一2).毫1+(+1+1).,一1,2,…,一1,()一(～2)',初始近似取z一Eo,…,O].2,计算函数,)一∑(2(一H)+(1一而)+0.5(xH+五+什】一3))I一2+2(一1).+(1一).的最优解,取初始近似'一[1,1,…,1].3,计算函数,0)=∑()的最优解,其中
8、=1()一(3—2x)墨一¨一2x,+1+1,=1,2,…,n,0一计】一0,取初始近似.To一[一1'..?,一1].?4,计算函数,()一∑[4q(一).+(1一五).]的最优解,取…15(i1,j12,…,n),初始近似'一[1'..?
9、,1].以上例子的终止条件为!坚{l三:::l!!ml&x(1,(){,1)≤1O高校应用教学第12
