《非线性最优化计算方法与算法》由会员分享，可在线阅读，更多相关《非线性最优化计算方法与算法（37页珍藏版）》请在金锄头文库上搜索。
1、济南大学毕业论文毕业论文题 目 非线性最优化计算方法与算法 学 院 数学科学学院 专 业 信息与计算科学 班 级 计算1201 学 生 陶红 学 号 20120921104 指导教师 邢顺来 二一六年五月二十五日10摘 要非线性规划问题是一般形式的非线性最优化问题。本文针对非线性规划的最优化问题进行方法和算法分析。传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过M
2、ATLAB程序求解最优值，探讨其收敛性和稳定性。另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。关键词：非线性规划；最速下降法；牛顿法；遗传算法ABSTRACTNonlinear programming problem is the general form of the nonlinear optimi
3、zation problem. In this paper, we carry on the analysis of the method and algorithm aiming at the optimization problem of nonlinear programming. The traditional methods of solving nonlinear programming problems include steepest descent method, Newton method, the feasible direction method, function a
4、pproximation method and trust region method. Recent studies found more method of solving nonlinear programming problems, such as genetic algorithm, particle swarm optimization (pso) algorithm. In this paper, the nonlinear programming is analyzed from two aspects: the constraint programming and the u
5、nconstrained programming.We solve unconstrained condition nonlinear programming problem by steepest descent method and Newtons method, and get the optimal value through MATLAB. Then the convergence and stability are discussed. Besides, the damped Newton method is furnished. By discussing the converg
6、ence and stability of the algorithm, the damped Newton method has higher accuracy andfaster convergent speed than Newtons method in solving unconstrained nonlinear programming problems.Punishment function is a classical method for solving constrained nonlinear. This paper solves nonlinear programmin
7、g problem with constraints by using genetic algorithm method, the core of which is SUMT. Get the optimal value through MATLAB, then the convergence and stability are discussed. Improve genetic algorithm, give the fitness function, and improve the convergence and stability of the algorithm through tr
8、ansforming the fitness function.Key words：Nonlinear Programming; Pteepest Descent Method; Newton Method; GeneticAlgorithm目 录摘要IABSTRACTII1 前言11.1 引言11.2 非线性规划的发展背景21.3 国内外研究现状21.4 研究主要内容及研究方案31.4.1 研究的主要内容31.4.2 研究方案31.5 研究难点42 预备知识52.1 向量和矩阵范数52.1.1 常见的向量范数52.1.2 谱范数62.2符号和定义62.3 数值误差72.4 算法的稳定性72.
9、5 收敛性93 非线性规划模型103.1 非线性规划模型103.2 无约束非线性规划113.2.1 最速下降法133.2.2 牛顿法153.2.2 阻尼牛顿法163.3 约束非线性规划173.3.1 惩罚函数法183.3.2 遗传算法183.3.3 自适应遗传算法20结论23参考文献24致谢25附录26- 5 -1 前言1.1 引言我们知道最优化是一门很古老的求极值问题，最优化在求解线性规划，非线性规划，随机规划，多目标规划，非光滑规划，整数规划，几何规划等方面研究得到迅速发展。而且最优化方法在经济计划，交通运输,工程计划，生产管理等方面广泛应用，成为一门比较受欢迎的学科。最优化方法与算法是在
10、本世纪40年代末形成的一门独立学科。早在17世纪的时候，牛顿和莱布尼兹研究出微积分的时代，就已经提出了函数的极大极小值得问题3,4然后出现了拉格朗日乘子法和柯西的最速下降法，到20世纪30年代的时候，最优化理论才开始迅速的发展，成为一门独立的学科，1930年苏联数学家提出了小规模的线性规划问题，1939年hitchcocck在生产管理和交通运输方面研究出了什么是线性规划，并且在1947年Dantzing提出了求解线性规划的方法：单纯形法。后来紧接着又提出了线性规划的对偶性理论，KT条件，奠定了非线性规划的基础，随着时代的发展，非线性最优化问题已经被人们提上了日程，非线性最优化是在20世纪50年
11、代形成了一门数学类的学科。是在线性规划的基础上发展起来的，并且研究出了求解无约束规划的DFP变尺度方法，最速下降法和牛顿法，拟牛顿法，无约束方法研究至今在应用的方法为Powell法，Powell法是一种改进的共轭方向法，也是迄今为止求解无约束非线性规划最有效的方法。而求解约束非线性规划问题最主要的方法主要有可行方向法，惩罚函数法，投影梯度法等方法。最优化计算与方法是一门应用很广泛且很受人欢迎的一门学科，他研究数学意义基础上的问题的最优解，既是对给出的实际问题从很多种方案中选出最优解。最优化理论涉及的内容较为广泛，包括数学分析，数值计算，数值分析，最优化方法，高等代数等学科。且实用性很强，在现实
12、生活中把实际问题转化为最优化问题，在数学建模、数值分析方面上有显著的应用。而我们知道最优化的一般理论是转化为求数学式子的极小值，它的一般形式为：,其中是决策变量，是目标函数，为可行域。而最优化的求解过程一般是迭代过程，就是给出初始值按照某种迭代规律进行计算。最后计算出一个点或者一个极限值就是所求的最优解4,17。我们所采用的计算工具就是使用MATLAB来完成的，我们知道MATLAB比高级语言执行能力低，但编程效率可读性高于高级语言，对于那些对编程不感兴趣的同学来说，这是一个很好的作弊软件。用MATLAB我们可以很容易就得到我们想要的答案，不必再去写那些繁杂又难懂的程序啦。但是我们在计算过程中，
13、会出现数值误差，数值误差对计算结果会产生很大的影响，我们在利用算法求解最优值的时候往往得到的是近似值，他意味在每一次的迭代过程中将会产生数值误差，从而最终的计算结果是不可估量的。算法的稳定性分析对求解非线性的最优值有重要的影响7，18。1.2 非线性规划的发展背景非线性规划是运筹学的分支之一，直到最近以来发展迅速，应用范围越来越广，并且不断产生新的方法和算法，由传统的最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法，到遗传算法，神经网络，蚁群算法，粒子群算法等发生了量的改变，原本求解非线性规划问题是人们的一大难题，随着时代的发展，求解非线性规划问题也被提上日程，在各个领域都有涉及，如经济，
14、管理，最优设计，质量控制，系统控制等方面得到广泛应用17。非线性规划是在线性规划的基础上发展起来的，在1951年库恩和塔克发表了关于最优性条件的论文标志着非线性规划理论的诞生。为非线性最优化的发展奠定了理论基础。在20世纪50年代得出二次规划，目标规划，多目标规划和可分离规划的多种解法。且他们都是以单纯型法为基础的，随着计算机的发展，非线性最优化得到迅速的发展。出现了很多的求解非线性规划最优化的方法和算法3,4,7,11。一般来说非线性规划的建模和求解比较难，大量的研究学者把精力和时间放在这个上面。非线性规划的最优条件，充分和必要条件在1948年被John论证了。后来在1967年被Fromov
15、itz和Mangasarain推广，论证了包含等式和不等式条件的非线性规划。非线性最优化在优化领域是一难点也是重点，而求解非线性最优化的算法也成为人们研究的重点。在非线性最优化中，有些方法的算法收敛速度较慢，计算次数多且较为繁杂，难以满足人们的要求，因而我们需要将无约束优化和约束优化的优点结合起来。得到新的算法，满足问题的要求3,4,13,16,17 。 求解非线性的方法有最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法。近来研究发现了更多的求解非线性最优化问题的方法如遗传算法，蚁群算法，粒子群算法，神经网络。很多非线性最优化问题要比线性问题求解要难得多，多种因素结合起来往往比单个因素要难，非线性最优化的求解方法没有统一固定的，因而相比较线性规划而言，求解非线性最优化是比较难的。1.3 国内外研究现状自1956年以来已经有人从事非线性规划理论的最优化方法和
