论文部分内容阅读
自从二十世纪70年代以来,QP-free算法一直是非线性约束优化研究中的一个十分活跃的领域.本文针对带非线性不等式约束的优化问题,对QP-free算法自身的理论进行了深入系统的研究,具体研究成果包括如下四部分.
1.绝大部分QP-free算法,须求解三个线性方程组和一个线性最小二乘问题(有时须求解五个线性方程组)以产生搜索方向.本文进一步研究该类算法,提出了一个新的QP-free内点算法.该算法通过求解具有相同系数矩阵的三个线性方程组获得搜索方向,减少了计算量。
2.通过积极约束集策略,利用部分约束条件,构造了一个规模较小的线性系统,提出了相应的可行QP-Free算法.该算法的搜索方向由三部分组成:下降方向dk0;可行方向sk1;以及克服Maratos效应的二阶校正方向dk1.证明了辅助方向dk=dk0+sk1为一个可行下降方向.线搜索技巧采用两种直线搜索的有机结合.辅助的可行下降方向与Armijo线搜索的结合确保了算法的全局收敛,同时方向dk=dk0+dk1与步长恒为1的试探步线搜索的结合确保了算法的超线性收敛率.理论上证明了当迭代次数充分大时,辅助的可行下降方向与相应的Armijo线搜索不再执行,而步长为1的试探性搜索恒成立.
3.对序列二次规划算法进行了本质上的改进.绝大部分序列二次规划算法,其共同之处在于:牛顿步方向均为通过求解不等式约束二次规划子问题而得.这里,提出了一个可行序列等式约束二次规划算法.首先,直接通过求解仅含线性等式约束二次规划子问题得到下降方向dk0.其次,不同于文[28],为避免定义精确罚函数,避免定义复杂的罚权重和深刻的理论分析,该算法通过求解线性方程组来修正方向dk0,得到目标函数f的可行下降方向dk.且算法在迭代中自动保证了乘子的非负性.
4.以往可行QP-free算法其可行下降方向须求解两个或多个线性方程组(有时包含非线性的子问题).这里,提出了一个改进的可行QP-free算法.该算法只须求解一个线性方程组就可得到可行下降方向,减少了计算量,且用一较弱的假设条件取代近似Hessian阵正定假设,算法仍具有全局收敛性和超线性收敛性。
最后,对上述算法均进行了数值实验,实验结果充分表明所提出的算法具有有效性、可行性和稳定性。