求解信赖域子问题的折线算法分析

《求解信赖域子问题的折线算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论帚一早珀T匕本文主要从信赖域子问题的角度，讨论了无约束非线性优化的信赖域算法．针对信赖域子问题的类型，构造了不同类型的信赖域算法，并做了相应的收敛性与数值试验．1．1非线性优化的信赖域算法信赖域方法(Trust—RegionMethods)是求解非线性规划的一类较新的方法，在近二十年来的发展历程中，它受到最优化研究者的高度重视，一直以来是非线性规划的研究热点．其研究起始于20世纪六十年代的Powell[1]，其基本技巧在一定意义上等价于著名的求解非线性最小二乘问题的Levemberg．rlarquadt算法‘21．信赖域算法与传统的线搜索不同，它可

2、以用非凸函数逼近模型，具有可靠、稳健性的特点，可用于“病态”问题求解，具有较强的收敛性，它可以用来代替一维搜索，解决Hessian矩阵最不正定和孔为鞍点等困难，既有牛顿法的快速局部收敛性，又具有理想的总体收敛性．考虑无约束优化问题minf(x)，x∈R”(1．1)其中厂：R”--}R二次连续可微．信赖域方法的基本思想是：在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点x。的一个小邻域．然后在信赖域上求解一个子问题，我们称这个解S。为试探步(trialstep)．然后再利用某一评价函数来决定是否接受该试探步以确定下一个迭代的信赖域．如果试探步被接受，则吒

3、+l=％+s☆，否则xk“=讫．新的信赖域的大小取决于试探步的好坏．粗略的说，如果试探步较好，则信赖域的大小保持不变或者扩大：否则，将缩小信赖域．对于无约束优化问题(1．1)，利用二次逼近，可构造如下的信赖域子问题：rainqtk)S)=／(t)+gtTs+i1sT色ssJ．0s0≤‰(1．2)其中g。∈R”为目标函数厂G)在当前迭代点x。的梯度，反∈R“”为目标函数厂b)在当前迭代点z。的Hessian矩阵或其近似，h。为信赖域半径，s为待求变量．设S。是信赖域子问题(1．2)的解，一般情况下，我们称目标函数y(x)在第k步求解信赖域子问题的折线算法研究的

4、实际下降量为Ared。=：f(x。)．．／(x。+。)称二次模型函数g‘‘’(&)的下降量Pred。=∥(0)一q‘‘’G。)为预估计下降量，定义比值rk=Ared女／Predl它衡量了二次模型g(‘’(＆)与目标函数厂G)的逼近程度．，：}越接近于1，表明逼近程度越好．下面给出无约束优化问题的一般信赖域算法：Stepl．给出初始值而，s，0<乞

5、lgoJJ，k=0．Step2．如果恬。1l≤s，则停止．Step3．解信赖域子问题(1．2)，求出＆．Step4。求出rk，根据rk的大小决定是否接受试探步&以及如何

6、调节信赖域半径h々：f％，‰12t坼+Sk．如果％≤Co；否则．选择hk满足：‰∈№Ec3鹏11skll,≯c,1’嚣㈣2；Step5．修正B¨，k：=k+1；转Step2．1．2无约束信赖域算法的研究现状信赖域子问题是信赖域方法的关键组成部分，它的有效求解直接影响算法的效率．求解信赖域子问题(1．2)的方法主要有：(1)解信赖域子问题的折线法：对于无约束问题(1．1)，当(1．2)中的玩变化2第一章绪论时，S的解形成一条空间曲线，称为最优曲线，求解子问题(1．2)比较有效和实用的信赖域方法是折线法，该方法构造折线近似最优曲线，然后得到子问题(1．2)的近似

7、解．这种组合曲线路径和信赖域的思想最早出现在Powell的单折线算法【3】中，现在各种曲线路径信赖域算法层出不穷，例如，双折线算法【41，Sorensen[51提出的算法，More和Sorensen的算法【61，限制梯度路径算法【7】，步长函数算法偈1，不定折线路径算法【91，徐成贤等提出了切线单折线法【10】．在这些基础上，张立【111等在2001年提出了混合折线法，数据表明，混合折线法优于单折线法．(2)解信赖域子问题的拟牛顿法：拟牛顿法具有许多优点，比如：迭代中仅需一阶导数，不必计算Hessian阵，除DFP算法外的Broyden族算法具有超线性收敛性

8、，以及它具有n步二阶收敛速率的性质．拟牛顿法的应用主要是{鼠1的秩校正公式以避免Marotos效应，集中于{反}的拟牛顿型秩校正，如BFGS，SRI，DFP以及邓乃扬等提出的基于新拟牛顿方程的拟牛顿算法Il21．李换琴等提出改进的SRI拟牛顿算法的2刀步Q二次收敛性【13I；KbalfanH．F的SRI校正的理论与实验分析m1；陈兰平，焦宝聪对非拟Newton的非凸族作了收敛性分析【15】；NiQin提出的有限内存的拟牛顿算法【16】；ZhangJianzhong等人提出一类新的拟牛顿方程：Bk+1&=或=M+仇乱／(s；&)及其收敛性n71；Benedet

9、taMotini等人在其文献中给出的不精确拟牛顿算法