论文部分内容阅读
非线性规划问题是数学规划中一类非常重要的问题.一方面,很多实际应用领域(如经济、工程、军事等)的问题部可以直接建模为非线性规划问题;另一方面,许多其它科学领域中的重要问题也可归结为非线性规划问题.所以,不管是从实际应用价值、还是理论意义的角度,设计合理、高效的求解非线性规划问题的算法都是至关重要的.信赖域方法是求解非线性规划问题的一类重要而有效的方法,它具有完善的理论体系以及稳定的数值表现.根据约束的类型来划分,非线性规划问题包括无约束、界约束、等式约束以及一般约束优化问题.其中的每一种问题都具有其特殊的结构,基于它们的特质,可以设计有效的信赖域方法来求解.
本文主要针对带有约束的非线性规划问题进行了研究,设计了若干针对不同约束类型的实用而有效的信赖域算法.具体研究工作如下:
(1)针对界约束优化问题,首先在第二章中设计了一种基于全新的仿射变换技巧的求解算法.受线性规划的启发,我们得到一个关于当前点的梯度、到边界的距离以及信赖域半径之间的巧妙关系,并基于此提出了一种新的处理界约束的仿射变换技巧.这种技巧能够使得算法在靠近解时更快地收敛,从而大大提高了算法的效率.对CUTEr(国际上广泛使用的非线性规划算例库)中所有界约束优化问题的测试表明,新算法比LANCELOT(曾获得国际数学规划协会的最高软件奖)更加有效,并且明显优于fminincon(Matlab)优化工具箱中的函数.在第三章中,我们提出了一种内点信赖域方法.经典的(最早由Dikin提出)仿射变换方法对于非凸问题,并没有很好的理论结果.然而我们充分利用问题的特点,每步迭代中,不仅要在Dikin球中极小化一个二次模型.还要考虑一个近似的投影梯度步,通过与信赖域技巧结合,保证了算法的全局收敛性。同时,文中还给出了算法的局部收敛性分析.在第四章中.我们将积极集技巧与信赖域思想结合,提出了一种求解较大规模界约束优化问题的积极集方法。首先利用仿射变换的梯度步估计了可能积极的约束,然后在积极约束的零空间中进一步减小目标函数.理论上证明了算法的全局收敛性,同时,我们对CUTEr中所有较大规模的界约束优化问题进行了测试,数值结果表明,与国际著名算法LBFGS-B(NEOS优化求解器)相比,新算法的计算机效果更好。
(2)针对等式约束优化问题,我们在第五章中构造了一种新的信赖域方法.传统的罚函数方法通常需要逐步精确或是近似精确地求解非线性子问题,该子问题的非线性程度与原问题相同,所以计算代价仍然很大.而新方法是基于增广Lagrange函数,在每步迭代中只需要在信赖域中极小化它的二次近似,多项式可解,从而问题难度降低.同时引入了一个判断条件,确定何时需要更新Lagrange乘子。并设计了新的更新罚因子的策略,证明了算法的全局收敛性.对于CUTEr中的等式约束优化问题,计算效果相比于LANCELOT.非常好.
(3)针对一般约束优化问题,在第六章中我们首次将滤子思想、k罚函数与信赖域技巧结合,提出了一种新的算法.利用罚函数处理一般约束,从而避免了约束与信赖域结合可能产生的不相容问题:同时结合∫∞罚函数的优点,能更快地减小约束违反度;滤子与罚函数结合,既避免了传统的滤子方法可能导致的滤子元素过多的问题,同时也能够防止罚因子增长过快.数值试验表明,对于测试问题,新算法较LANCELOT有明显优势.