对非线性规划单纯形算法的研究

摘要

求解非线性规划问题的通常算法中，都必须求其函数的导数。但很多实际问题其函数均仅连续非光滑或无法求导数。这时，就放弃了求梯度的方法，而采用直接法。非线性规划单纯形算法(以下简称单纯形算法)是较早的直接方法之一。并且非线性规划单纯形算法是无约束最优化问题中对解决大量实际问题比较有效的直接搜索算法，它构思直观，编程简单，因而乐于被实际工作者采用。因此对非线性规划单纯形算法的研究引起了非线性优化领域研究者的关注。近几年对非线性规划单纯形算法的研究同趋成熟，但是对其理论的研究还不够完善。 本课题主要对单纯形算法进行深入的研究，在第二部分介绍了经典单纯形算法和Multi-direction Search方法(简称MDS方法)的结构步骤，对这两种算法的优缺点进行理论分析；为了对单纯形算法进行进一步的改进，在本文的第三部分中对经典单纯形算法进行了修改，并给出了修改后的新的算法的计算步骤；在第四部分通过众多的测试函数证明，修改的单纯形算法对初值的适应范围更宽，能加速计算收敛速度，可以避免迭代过程中的单纯形退化现象。 本文的创新之处在于： (1)对经典非线性规划单纯形算法和MDS算法进行了全面的研究、分析，并对这两种算法进行了收敛性分析。 (2)在经典非线性规划单纯形算法的研究基础上，又提出了一种修改的新算法。修改的新算法采用了求除最坏点以外的其余各点的加权平均值作为反射中心，这样有利于加快收敛速度：并结合“平移单纯形”方法，这样可以保证单纯形在迭代过程中不退化，不变形。 (3)对新的算法与经典的单纯形算法进行了数值实验比较，得出了新的算法是一种有效的算法。

目录

文摘

英文文摘

声明

致谢

1绪论

1.1研究意义

1.2研究现状

1.3最优化问题

1.4直接搜索法

1.5本文的结构

2非线性规划单纯形算法

2.1经典的非线性单纯形算法

2.1.1方法

2.1.2终止条件

2.1.3算法流程

2.1.4算法图示

2.1.5算法分析

2.2 Multi-directional Search算法(即MDS方法)

2.2.1算法流程

2.2.2算法图示

2.2.3MDS算法收敛性分析

3对单纯形算法的改进

3.1平移单纯形方法

3.2新的算法

3.2.1新的算法流程

3.2.2新的算法图示

4数值实验和算法分析

4.1实验数据与分析

4.2结果与算法分析

5总结

参考文献

附录

作者简历、硕士在读期间曾发表论文