无约束非线性规划求解方法及其实现.doc

1、 无约束非线性规划求解方法及其实现 作者：杨玲 指导老师：陈素根 摘要 : 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个 n 元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20 世 纪 50 年代才形成的一门新兴学科。 1951 年 H.W 库恩和A.W 塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在 50 年代还得出了可分离规划和二次规划的 n 种解法，

2、它们大都是以 G.B.丹齐克提出的解线性规划的单纯形法为基础的。 50 年代末到 60 年代末出现了许多解线性规划问题的有效的算法， 70 年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。 20 世纪 80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点 法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 关键词 最优化 共轭梯度法 非线性 无约束 1 引言 1.1 无约束非线性规划问题是最基本的

3、非线性规划问题，在19591963 年幼三位数学家共同研究成功求解无约束问题的DFP 变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。 20 世纪 80 年代以来，随着计算机技术的快速发展，非线性 规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问

4、题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1 主要介绍无约束非线性规划的相关概念 一个非线性 规划问题的自变量 x 没有任何约束，或说可行域即是整个 n 维向量空间： nxR 错误 !未找到引用源。 ,则称这样的非线性规划问题为无约束问题： 错误 !未找到引用源。或 错误 !未找到引用源。 。 一般我们研究的无约束非线性规划问题大都可以归结为求无约束最优化问题。 2.2 介绍无约束非线性规划的几种主要的求解方法及其实现 求解无约束非线性规划问题就是求解无约束非线性规划最优化的问题，可以表述为 m in , nf x x

5、 R 。 它的求解方法有许多种，大体上可以概括为两大类，一是直接法，二是解析法。解析法又被称为代数法，值得是通过计算 fx 的一阶，二阶偏导数及其函数的解析性质来实现极值的求解方法。相应的，不必计算 fx 的一阶、二阶偏导数及其函数的解析性质，仅用到函数值来实现近似值的求解方法叫直接法。 1. 先介绍直接法中的一维搜索方法，包括 Fibonacci 法和 0.618法。 一维搜索方法就是在用迭代法沿某一已知方向求目标函数极小点的方法，常用的由斐波那契法和黄金分割法。 考虑一维极小值问题 mina t b ft，若 ft 是 ,ab 区间上的下单峰函数，我们将通过不断的缩短 ,ab 的长度，来探

6、索 mina t b ft的近似最优解。在 ,ab 中任意取两个关于 ,ab 是对称的点 1t和 1t (不妨设 , 21tt 并称它们为搜索点 )，计算 1ft 与 2ft 并比较它们的大小。对于单峰函数，若 12f t f t ,则必有 1*,t a t ， 因而 1,at 是缩短了的单峰区间，若 21f t f t ,则有 2*,t t b ， 故 2,tb 是缩短了的单峰区间，若 21f t f t ，则 1,at 和 2,tb 都是缩短了的单峰。因而通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，又可以获得更短的单峰区间。如此下去，在单

7、峰区间缩短到充分小时，可以取最后的搜索点作为 mina t b ft最优解的近似值，下面介绍斐波那契法来选取搜索点，使给定的单峰区间的长度能尽快缩短。 Fibonacci 法： 若数列 nF 满足关系： 011FF ， 21n n nF F F ，2 , 3 ,n ， 则称 nF 为 Fibonacci 数列， nF 称为第 n 个Fibonacci 数，称相邻两个 Fibonacci 数之比 1nnFF 为 Fibonacci 分数。当用斐波那契法以 n 个探索点来缩短某一区间时，区间长度的第一次缩短率为 1nnFF ，其后各次分别为 23 11 2 2, , ,nnnnFF FF F F，

8、由此，若 1t 和 2t ， 21tt 单峰区间 ,ab 中的第 1 个和第 2个探索点的话，则应有比例关系 11 nnFtab a F ， 22anntFb a F，从而 11 nnFt a b aF ， 22 n nFt a b aF ，它们关于 ,ab 是对称的点。 如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超过精度 0 ，这也要求最后区间的长度不超过 ，即nbaF 。由此，按照预先给定的精度 ，确定使nbaF 成立的最小整数 n 作为搜索次数，直到进行第 n 次探索点为止。用上述不断缩短函数 fx 单峰区间的方法来求 mina t b ft的近似解是 Kief

9、er(1953 年 )提出的，叫 Fibonacci 法。具体步骤如下： 1 选取初始数据，确定单峰区间 00,ab ,给出搜索精度 0 ，由nbaF 确定搜索次数 n ； 2 1k ， 0aa ， 0bb ，计算最初两个搜索点，按 11 nnFt a b aF ， 22 n nFt a b aF 计算 1t ， 2t ； 3 while 1kn 11f f t , 22f f t if 12ff 2at ； 21tt ； 11 nknkFt a b aF ； else 1bt ； 12tt ； 12 nknkFt b b aF ； end 1kk end 4 当进行至 1kn 时， 12 1

10、2t t a b ，此时无法比较 1ft 与 2ft 的大小来确定最终区间，为此，取 211212t a bt a b a ，其中 为任意小点的数，在 1t 和 2t这两点中，以函数值较小者为近似极小值，相应的函数值为近似极小值，并得最终区间 1,at 或 2,tb 。 由上述分析可知，斐波那契法使用对称搜索方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数达到预定的某一缩短率。 2. 下面介绍解析法中的最速下降法、牛顿法、共轭梯度法和 变尺度法。 （ 1)最速下降法： 对基本迭代格式 1k k kkx x t p ，我们一般考虑从点kx 出发沿哪一个方向 kp ，使目标函数下 f 降得最

11、快。由微积分的相关知识我们可以知道，点 kx 的负梯度方向 ()kkp f x 是从点 kx 出发使 f 下降最快的方向。为此，负梯度方向 ()kfx 为 f 在点 kx 处的最速下降方向，按基本迭代式 1k k kkx x t p 每一轮从点 kx 出发沿最速下降方向 ()kfx 作一维搜索，来建立求解无约束极值问题的方法称之为最速下降法。该方法的特点是每轮的搜索方向都是目 标函数在 当前点 下降最快 的方向。 同 时，( ) 0kfx 或 ()kfx 作为停止条件。其具体的步骤为： (a).选取初始数据。选取初始点 0x ，给定终止误差，令 k:=0. (b).求梯度向量。计算 ()kfx

12、 ，若 ()kfx ，停止迭代，输出 kx 。否则进行 (c)。 (c). 构造负梯度方向。取()kkp f x 。 (d). 进行 一 维 搜 索 。求 kt ，使得0( ) m i n ( )k k k kktf x t p f x t p ，令1k k kkx x t p ，=1kk： 进行 (b). 例 题 ： 用 最 速 下 降 法 求 解 无 约 束 非 线 性 规 划 问 题 ， 2212m in 2 5f x x x，其中 12, Tx x x ，要求选取初始点 0 2, 2 Tx ，终止误差 610 。 解： 1） 122 , 50 Tf x x x ,编写 M 文件 det

13、a f.m 如下： function.f,df=deta f(x); f=x(1)2+25*x(2)2; df(1)=2*x(1); df(2)=50*x(2)2; 2)编写 M 文件 zuisu.m clc x=2,2; f0,g=deta f(x); while norm(g)0.000001 p=-g/norm(g); t=1.0;f=deta f(x+t*p); end x=x+t*p f0,g=deta f(x) end (2). 牛顿法： 牛顿法是求无约束最优解的一种古典解析算法，其基本思想是在寻找收敛速度最快的无约束最优化方法中，在每次迭代时，用适当的二次函数去近似目标函数 f

14、，并用迭代点指向近似二次函数极小点的方向来构造搜索方向，然后精确地求近似二次函数的极小点，以这个极小点作为 f 的极小点的近似 值。 牛顿法的迭代步骤： 1） 给定初始点和收敛精度； 2） 计算 kfx ， kHx ， 1kHx 3） 求 11k k k k kx x K H x f x ； 4） 检查收敛精度，若 1kkxx ，则 1* kxx ，停止；否则1kk ，返回 2）继续。 牛顿法的优点是每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值变大的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有严格要求。但是牛顿法也有缺点，它对目标函数要求严格，函数必须具有连续的一、二阶导数

15、；海赛矩阵必须正定且非奇异。还有牛顿法的计算复杂，存储量大。 (3). 共轭梯度法： 共轭梯度法最早是由计算数学家 Hestenes 和几何学家 Stiefel 在 20世纪 50年代初为求解线性方程组 , nA x b x R 而各自 独 立 提 出 的 。 在 A 为 对 称 正 定 阵 时 ， 方 程 组, nA x b x R 等价于最优化问题 1m i n 2n TTxR x A x b x ，由此， Hestenes 和 Stief 的方法也可以看做 是求二次函数极小值得共轭梯度法。在 1964 年 Fetcher 和 Reeves 将这种方法推广到了非线性优化，得到了求一般函数极小值的共轭梯度法。对于无约束最优化问题 minnxR fx ，其中 : nf R R 连续可微有下界，共轭梯度法是解决这类问题中的最有效的数值方法之一。特别是在大规模问题上，共轭梯度法因为算法简便、所需存储量小、收敛速度快等特性而在许多工程科学领域采用。 对于无约束 优化问题，给出一个初始值 0x ，算法迭代产生点列 12,xx 。假设某一 kx 是无约束优化问题的解，或者该点列收敛于最优解。在第 1k 次迭代中，当前迭代点为 kx ，产生下一个迭代点 1k k k kx x a d ，其中 nkdR 是搜索方向，