非线性优化中的滤子方法及非单调方法

摘要

解非线性规划问题的滤子方法最早是由Fletcher和Leyffer提出的。由于其良好的数值例子而受到广泛的重视。以往在处理带约束的优化问题时，都要用到拉格朗日函数或罚函数。但是，有时会产生一些新问题，如罚参数的处理。罚参数过大或过小都会引起不好的效果。滤子方法是一种无罚参数的方法。自从关于滤子的第一篇文章发表以来，已有很多人在做这方面的工作，如Fletcher，Dennis，Toint，Leyffer等。关于解非线性规划问题的滤子方法的软件已经出现，并且该软件和其它软件相比，在解有些问题上很有优势。滤子方法现在已经和信赖域方法，序列二次规划(SQP)方法，序列线性规划(SLP)方法，内点法，模式搜索法结合起来，并且还用来解决其它类型的问题，如在[30]中，滤子法被用来解非光滑优化问题。 滤子方法借用了多目标优化的思想，将约束优化问题化为双目标优化问题，即使得目标函数和约束违反度都要减小，但是可以不同时减小，其本质是一种非单调的方法，有利于得到全局最优点。本学位论文对滤子方法作了深入研究，通过对其本质的研究，对其进行改进，并提出新的具有良好性质的算法。 考虑到滤子方法本质上是一种非单调的方法，所以可以设计一种新的非单调的方法来解约束优化问题。在第二章，提出了一种新的非单调的算法。该算法既不需用罚函数或拉格朗日函数来检验步长的可接受性，也不需要用到滤子和可行性恢复阶段。此外，同其它滤子方法相比，本章提出的算法在接受步长方面，具有较强的灵活性。该算法具有全局收敛性和局部超线性收敛性。最后，给出的数值结果表明该算法是有效的。 在第三章，提出了一种求解最大最小值问题的非单调SQP算法，也是第二章中提出的算法在实际问题中的应用。该算法具有全局收敛性和局部超线性收敛性。最后，给出的数值结果表明该算法在解决实际问题中是非常有效的。 目前所提出的滤子方法基本上都是通过SQP方法得到搜索方向的。在SQP方法中，一般用一阶泰勒展开得到约束条件的近似逼近。这对于那些几乎线性(NL)的约束条件来说不失为一个好方法，但对于那些高度非线性(HN)的约束条件来说，仅用一阶逼近，就不太合适了。从数值计算的角度来说，HN约束条件在每一个迭代点的的约束违反度会有较大的变化幅度，而对于NL约束条件来说，这种情况一般不会发生。所以，对于HN约束条件和NL约束条件需区别对待。事实上有许多实际问题同时有HN和NL约束条件。在二维滤子SQP方法中，尽管将目标函数和约束违反度分别考虑，但是它们将所有的约束条件放在一起考虑且只有一个约束违反度。未对具有各自不同性质的HN和NL约束条件充分考虑。在第四章，提出了一种三维滤子信赖域算法。考虑到HN和NL约束条件各自的性态，将约束条件分为HN和NL约束条件两个部分，将它们相应的约束违反度同时最小化作为两个目标。这样就得到一个三维滤子，包括三个分量，即目标函数值、HN和NL约束违反度。这样，与二维滤子相比，一个试探点被接受的条件将大大放松。该算法具有全局收敛性和局部超线性收敛性。最后，给出的数值结果表明该算法是有效的。 另外，还注意到SQP方法本身也有两个不可忽视的缺点，即较大的计算量和子问题的不相容性。而近年来发展起来的序列线性方程组(SSLE)方法可以避免上述SQP方法中的不足。SSLE方法本质上就是用一个或多个具有相同系数矩阵的线性方程组来取代SQP方法中的一个或多个QP子问题。在第五章中，提出了一种新的SSLE算法。该算法无需解QP子问题，只需解三个具有相同系数矩阵的线性方程组。从而，于[31]相比，计算量大大减少。通过利用滤子的技巧，无需罚函数，避免了罚参数的选取。对初始点不作特殊要求，可以是任意的点。算法中还使用了X-有效集的技巧。只有在X-有效集中的不等式约束条件和等式约束条件才被考虑，可以减少算法的计算量。另外，该算法还对[39，40]算法进行改进，克服了在某些特殊情况下，其算法不具有下降性的不足。由此可以看出，本章算法既保持了[31]和[39，40]中算法好的性质，也具有其独自的特点。该算法具有全局收敛性和局部超线性收敛性。最后，给出的数值结果表明该算法是有效的。

目录

文摘

英文文摘

声明

第一章引言

1.1约束非线性规划基本理论

1.2滤子方法

1.3无序列二次规划方法

1.4非单调方法

第二章一种无需罚函数的非单调SQP算法

2.1引言

2.2算法

2.3全局收敛性

2.4局部收敛性

2.5数值结果

5.小结

第三章一种求解最大最小值问题的非单调SQP算法

3.1引言

3.2算法

3.3全局收敛性

3.4局部收敛性

3.5数值结果

第四章一种三维滤子信赖域SQP算法

4.1引言

4.2算法

4.3全局收敛性

4.4数值结果

第五章一种不可行序列线性方程组滤子算法

5.1引言

5.2算法

5.3全局收敛性

5.4局部收敛性

5.5数值结果

致谢

参考文献

个人简历 在读期间发表的学术论文与研究成果