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

基于简单二次函数模型的求解无约束规划问题的 信赖域算法 孙清滢, 刘秋 中国石油大学数学与计算科学学院，山东，东营 257061 王长钰 曲阜师范大学(日照校区)运筹与管理学院 山东 日照 276826 摘要 基于简单二次函数模型，建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。 关键词：无约束最优化；信赖域算法；收敛性；数值实验 中图分类号：O221.2 引言 考虑无约束最优化问题 （1） 其中是连续可微函数。 众所周知，信赖域算法[1~4]是求解问题（1）的重要算法，具有较强的全局收敛性质和较快的局部收敛速度。信赖域子问题的求解是信赖域算法的一个关键问题，算法的工作量大部分集中在子问题的求解上。通常的信赖域子问题基于如下二次模型： （2） 其中，是目标函数在当前点的梯度。是目标函数在当前点的Hesse矩阵或其近似。是信赖域半径。为某一范数，通常采用2-范数。 易见，求解问题（2）之困难在于是一个一般的实对称矩阵，如果是一个实对称正定对角矩阵，则可以较方便求出子问题（2）的最优解。即： 若，则。 若，求解得 ， 国家自然科学基金资助项目，中国石油大学博士基金资助项目（Y040804） 则 . 为了实现这一想法，结合时贞军[6]的稀疏对角拟牛顿方法，保证是一个实对角矩阵及较好的近似在点的Hesse矩阵，取近似满足拟牛顿方程，即为下列问题的解： , （3） 其中，。 同时为保证是正定矩阵，限制在一定范围内取值，即要求 . 为此需要求解如下问题 . （4） 即 . （4’） 解之得, 对，当时， 若，则取； 若，则取； 若，则取. 当时， 则取. 本文取信赖域子问题模型为： （5） 其中。是一实对称正定对角矩阵，满足（4）。 本文基于简单二次函数模型（5），建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。 算法 保证信赖域算法全局收敛性的关键在于迭代过程中信赖域半径的调整策略。如何选择呢？一般地，当与之间的一致性满足某种要求时，应尽可能选取较大的，否则选取较小的。 设子问题（5）的解为，则目标函数在第k步的实际下降量为 （6） 模型（5）的预估下降量为 （7） 定义比值 （8） 它衡量二次模型近似目标函数的程度。如果接近1，表明在当前点与的近似程度较好，因此在下一迭代时，可适当增大信赖域半径。如果或接近于0，表明在当前点与的近似程度较差，因此适当减少信赖域半径，以提高与的近似程度。 新的信赖域算法（NTR）： Step0 取初始点。令； Step1 若，算法终止。得到问题（1）的解为。否则，转Step2； Step2 求解信赖域子问题（5），得解； Step3 由（8）式计算，若，则令； 若，则令； 若，则令； Step4：若，令，，，转Step2；否则，令，求解问题（4）得，令，转Step1。 引理1 设是问题（5）的解，若，则。 证明 注意到是问题（5）的可行点，故 。 即 。 若，即，故0是子问题（5）的最优解。但0是可行域的内点，故，即，矛盾。故。[] 引理2 设是由算法产生的无穷迭代数列，则序列单调非增。 证明 对，若，则，此时；若，则由引理1及的定义知 故。 因此序列单调非增。