论文部分内容阅读
信赖域方法和线搜索技术都可以保证非线性优化算法整体收敛,各有优势,信赖域方法能保证算法具有良好的收敛性,线搜索技术在确定新的迭代点时计算量较小.Nocedal和Yuan提出了结合两者的思想,使得算法既能保有信赖域方法良好的收敛性质,又能在确定新的迭代点时降低计算难度,减少计算量.Fletcher和Leyffer提出的过滤技术一般用于求解约束优化问题,基本思想是如果试探点改进了目标函数或约束违反度,就接受该试探点.过滤技术可以嵌入于信赖域或线搜索框架,替代传统的罚函数方法保证优化算法的整体收敛性.本文结合过滤线搜索技术和信赖域方法,建立求解非线性等式约束优化问题的算法,从理论上研究算法整体收敛性与局部收敛速率,用数值实验检验算法的效果.进一步,使用仿射内点方法,将算法拓展到求解带有非线性等式约束和变量非负约束的优化问题. 对于非线性等式约束优化问题,使用结合过滤线搜索技术的信赖域方法的思想,本文给出两种算法.第一种算法基于信赖域序贯二次规划框架,新的迭代步(试探步)被分解为两个部分来计算:法向步和切向步.法向步主要为降低约束违反度,要求它满足线性化约束,同时限制它不能过大,否则切向步不可能提供足够的下降量.如果这样的法向步不存在,算法转向可行性恢复阶段,目的是通过降低约束违反度找到一个新的迭代点使得约束违反度或目标函数有充分下降量.得到法向步后,切向步通过求解相应的信赖域子问题得到,切向步主要为模型的目标函数提供充分的下降量.得到试探步后,使用结合过滤技术的回代线搜索确定适当的步长产生新的迭代点,目标函数实际下降量和预计下降量的比值仅用来调节信赖域半径.在合理的假设下提供算法整体收敛性证明,给出的数值实验结果表明算法可行有效.进一步,引入二阶校正步克服了Maratos效应,使得算法在一定条件下局部超线性收敛. 第二种算法基于Lagrange函数,与前一种算法不同,计算迭代步时将整个信赖域子问题分解为线性化约束值空间和零空间上的一对信赖域子问题,通过求解这一对子问题得到法向步和切向步.在使用过滤线搜索技术确定步长时,用原问题Lagrange函数替代目标函数作为价值函数.算法在合理假设下整体收敛,并且不使用二阶校正步算法也取得超线性收敛速率,最后提供数值实验结果表明算法可行有效. 对于带有非线性等式约束和变量非负约束的优化问题,本文给出一种结合过滤线搜索技术的仿射内点信赖域算法.根据问题最优性条件的特点,引入恰当的仿射矩阵,建立相应的仿射信赖域子问题产生迭代步,利用过滤线搜索技术选取适当的步长.此外,由于问题有变量非负约束的要求,所以需要保证迭代点是严格正的.为此,对回代线搜索初始试探步长加以修正使得只要初始点严格正,则所有迭代点是严格正的.在适当假设下证明了算法整体收敛性,并报告数值实验结果. 最后对全文进行总结,并且提出有待进一步深入研究的一些问题。