基于简单二次函数模型的求解无约束规划问题的信赖域算法.doc

《基于简单二次函数模型的求解无约束规划问题的信赖域算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于简单二次函数模型的求解无约束规划问题的信赖域算法孙清滢,刘秋中国石油大学数学与计算科学学院，山东，东营王长钰曲阜师范大学(日照校区)运筹与管理学院山东日照摘要基于简单二次函数模型，建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。关键词：无约束最优化；信赖域算法；收敛性；数值实验中图分类号：O221.21.引言考虑无约束最优化问题（1）其中是连续可微函数。众所周知，信赖域算法[1~4]是求解问题（1）的重要算法，具有较强的全局收敛性质和较快的局部收敛速度。

2、信赖域子问题的求解是信赖域算法的一个关键问题，算法的工作量大部分集中在子问题的求解上。通常的信赖域子问题基于如下二次模型：（2）其中，是目标函数在当前点的梯度。是目标函数在当前点的Hesse矩阵或其近似。是信赖域半径。为某一范数，通常采用2-范数。易见，求解问题（2）之困难在于是一个一般的实对称矩阵，如果是一个实对称正定对角矩阵，则可以较方便求出子问题（2）的最优解。即：若，则。若，求解得，国家自然科学基金（）资助项目，中国石油大学博士基金资助项目（Y）则.为了实现这一想法，结合时贞军[6]的稀疏对角拟牛顿方法，保证是一个实

3、对角矩阵及较好的近似在点的Hesse矩阵，取近似满足拟牛顿方程，即为下列问题的解：,（3）其中，。同时为保证是正定矩阵，限制在一定范围内取值，即要求.为此需要求解如下问题.（4）即.（4’）解之得,对，当时，若，则取；若，则取；若，则取.当时，则取.本文取信赖域子问题模型为：（5）其中。是一实对称正定对角矩阵，满足（4）。本文基于简单二次函数模型（5），建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。1.算法保证信赖域算法全局收敛性的关键在于迭代过程中信赖域

4、半径的调整策略。如何选择呢？一般地，当与之间的一致性满足某种要求时，应尽可能选取较大的，否则选取较小的。设子问题（5）的解为，则目标函数在第k步的实际下降量为（6）模型（5）的预估下降量为（7）定义比值（8）它衡量二次模型近似目标函数的程度。如果接近1，表明在当前点与的近似程度较好，因此在下一迭代时，可适当增大信赖域半径。如果或接近于0，表明在当前点与的近似程度较差，因此适当减少信赖域半径，以提高与的近似程度。新的信赖域算法（NTR）：Step0取初始点。令；Step1若，算法终止。得到问题（1）的解为。否则，转Step2；

5、Step2求解信赖域子问题（5），得解；Step3由（8）式计算，若，则令；若，则令；若，则令；Step4：若，令，，，转Step2；否则，令，求解问题（4）得，令，转Step1。引理1设是问题（5）的解，若，则。证明注意到是问题（5）的可行点，故。即。若，即，故0是子问题（5）的最优解。但0是可行域的内点，故，即，矛盾。故。[]引理2设是由算法产生的无穷迭代数列，则序列单调非增。证明对，若，则，此时；若，则由引理1及的定义知故。因此序列单调非增。[]为得到算法的下降性条件，引入Cauchy点：（9）其中（10）引理3对Ca

6、uchy点满足：.（11）证明由（10）知，有两种取值，下面分别讨论：1），此时，，因此有2），此时，因此有因为，故，即。再由（12）知引理4设是问题（5）的精确解，则.证明由问题（5）的精确最优解，则，故有1.算法的全局收敛性定理1设，且在水平集上有下界。若在算法中取，则算法产生的无穷迭代点列满足.证明由的定义知.由Taylor定理有.又因为故有其中随着的减少而任意减少，满足.假设，则和，使得对有.由引理4及的有界性知，对有结合（13）得由的性质知，存在充分小的，使当时有;.再由（15）得.故。因此由算法知信赖域半径发生在

7、时，因此.（16）若存在一个无限指标集K，使得对有。由（14）及算法Step3知，对有又因为单调非增有下界及（17）知.此与（16）矛盾。故这样的不存在，故对充分大的必有.另一方面，由算法Step3知，当时，按比率缩小，故。这同样与（16）矛盾。故而.定理2设，在水平集上有下界，且为Lipschitz连续（常数为L），若在算法中取，则算法产生的无穷迭代点列满足.证明只需考虑对任意的，的情况。任取一个，记则对,.故如果序列，则对成立。由定理1的证明过程知，这种情况不会发生，所以序列最终会离开。设是满足的第一个离开的迭代点，对，

8、由引理4知.如果对，，则否则存在使得，则由于序列单调下降有下界，故有极限，即.由（18），（19）知因而.令得.1.数值试验本节选择了文献[6]的全部算例，利用matlab编制程序在PIII.933机器上对本文算法进行数值试验，如果算法中用DFP公式或BFGS公式校正，分别记为DFPTR和