欢迎来到天天文库
浏览记录
ID:12588308
大小:684.53 KB
页数:17页
时间:2018-07-17
《无约束非线性规划求解方法及其实现--论文》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、无约束非线性规划求解方法及其实现摘要:非线性规划是具有非线性约束条件或目标函数的数学规划,是运筹学的一个重要分支。非线性规划属于最优化方法的一种,是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题,且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基
2、础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法,70年代又得到进一步的发展。非线性规划在工程,管理,经济,科研,军事等发面都有广泛的应用,为最优设计提供了有力的工具。20世纪80年代以来,随着计算机技术的快速发展,非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果,无约束非线性规划问题是非线性规划的一个重要内容,很多学者对非线性规划问题进行了深入且系统的研究,研究成果丰硕。关键词最优化共轭梯度法非线性无约束1引言1.1无约束非线性规划问题是最基本的非线性规划问题,在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP
3、变尺度法,该算法的研究成功是无约束优化算法的一个大飞跃,引起了一系列的理论工作,并陆续出现了许多新的算法。20世纪80年代以来,随着计算机技术的快速发展,非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容,很多学者对非线性规划问题进行了深入且系统的研究,研究成果丰硕。1.2本文主要研究无约束非线性规划问题,将文章分成四个部分,首先会具体介绍无约束非线性规划的相关概念,并在此基础上研究非线性规划的相关理论与基本算法问题,接着详细介绍无约束非线性规划的几种主要的求解方法,最后举例说明他在实际生活中的应用,
4、并编程实现它。2正文2.1主要介绍无约束非线性规划的相关概念一个非线性规划问题的自变量x没有任何约束,或说可行域即是整个n维向量空间:,则称这样的非线性规划问题为无约束问题:或。一般我们研究的无约束非线性规划问题大都可以归结为求无约束最优化问题。2.2介绍无约束非线性规划的几种主要的求解方法及其实现求解无约束非线性规划问题就是求解无约束非线性规划最优化的问题,可以表述为。它的求解方法有许多种,大体上可以概括为两大类,一是直接法,二是解析法。解析法又被称为代数法,值得是通过计算的一阶,二阶偏导数及其函数的解析性质来实现极值的求解方法。相应的,不必计算的一阶、二阶偏导数及其函数的解析性
5、质,仅用到函数值来实现近似值的求解方法叫直接法。1.先介绍直接法中的一维搜索方法,包括Fibonacci法和0.618法。一维搜索方法就是在用迭代法沿某一已知方向求目标函数极小点的方法,常用的由斐波那契法和黄金分割法。考虑一维极小值问题,若是区间上的下单峰函数,我们将通过不断的缩短的长度,来探索的近似最优解。在中任意取两个关于是对称的点和(不妨设,并称它们为搜索点),计算与并比较它们的大小。对于单峰函数,若,则必有,因而是缩短了的单峰区间,若,则有,故是缩短了的单峰区间,若,则和都是缩短了的单峰。因而通过两个搜索点处目标函数值大小的比较,总可以获得缩短了的单峰区间。对于新的单峰区间
6、重复上述做法,又可以获得更短的单峰区间。如此下去,在单峰区间缩短到充分小时,可以取最后的搜索点作为最优解的近似值,下面介绍斐波那契法来选取搜索点,使给定的单峰区间的长度能尽快缩短。Fibonacci法:若数列满足关系:,,,则称为Fibonacci数列,称为第n个Fibonacci数,称相邻两个Fibonacci数之比为Fibonacci分数。当用斐波那契法以n个探索点来缩短某一区间时,区间长度的第一次缩短率为,其后各次分别为,由此,若和,单峰区间中的第1个和第2个探索点的话,则应有比例关系,,从而,,它们关于是对称的点。如果要求经过一系列探索点搜索之后,使最后的探索点和最优解之间
7、的距离不超过精度,这也要求最后区间的长度不超过,即。由此,按照预先给定的精度,确定使成立的最小整数n作为搜索次数,直到进行第n次探索点为止。用上述不断缩短函数单峰区间的方法来求的近似解是Kiefer(1953年)提出的,叫Fibonacci法。具体步骤如下:选取初始数据,确定单峰区间,给出搜索精度,由确定搜索次数;,,,计算最初两个搜索点,按,计算,;while,if;;;else;;;endend当进行至时,,此时无法比较与的大小来确定最终区间,为此,取,其中为任意
此文档下载收益归作者所有