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

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

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

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

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

5、法又 被称为代数法，值得是通过计算f （人）的一阶，二阶偏导数及其 函数的解析性质来实现极值的求解方法。相应的，不必计算 f （工）的一阶、二阶偏导数及其函数的解析性质，仅用到函数值 来实现近似值的求解方法叫直接法。1.先介绍直接法中的一维搜索方法，包括Fibonacci法和0.618 法。一维搜索方法就是在用迭代法沿某一已知方向求目标函数极小 点的方法，常用的由斐波那契法和黄金分割法。考虑一维极小值问题min f （t），若f G）是a,b区间上的下单 a t b峰函数，我们将通过不断的缩短a，b的长度，来探索mm f （t） 1r 1a t 的近似最优解。在a，b中任意取两个关于a，b是对

6、称的点11（不妨设,t2 （不妨设,t2 t1并称它们为搜索点），计算f(t1) 与 f (t2 )并比较它们的大小。对于单峰函数，若）/&2）则必有t* g a, t Ja, t/ t f t J1因而 是缩短了的单峰区I日，若 21则有产虹”，故2,b J是缩短了的单峰区间，若 f匕）=f，则。七和L 2,b J都是缩短了的单峰。因而通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单 峰区间。对于新的单峰区间重复上述做法，又可以获得更短的单 峰区间。如此下去，在单峰区间缩短到充分小时，可以取最后的搜索点作为min /。）最优解的近似值，下面介绍斐波那契法 a t F, f ,f，由

7、此，有11和12，21单峰区间n 1n 2 . . .2a , b J中的第1个和第2个探索点的话，则应有比例关系j_a =2a n - 2t = a Ei ( 。- ab - a Fb - a F 从而 i Ft2 = a +早(b a)，它们关于b是对称的点。n如果要求经过一系列探索点搜索之后，使最后的探索点和最优解 之间的距离不超过精度$0，这也要求最后区间的长度不超过&，即拦 *。由此，按照预先给定的精度$，确定使宴5FFnn成立的最小整数n作为搜索次数，直到进行第n次探索点为止。用上述不断缩短函数/ G)单峰区间的方法来求minf (t)的近似atb解是Kiefer(1953年)提出

8、的，叫Fibonacci法。具体步骤如下： 】。选取初始数据，确定单峰区间k，b01给出搜索精度50，由 b - ab=b0，计算最初两个搜索点，按 t b=b0，计算最初两个搜索点，按 t = a + n-2 (b - a)计.算ttn，t = a+_ ni (b-a)i Fn2 k ，t = a+_ ni (b-a)i Fn3。while k0.000001p=-g/norm(g);t=1.0;f=deta f(x+t*p);endx=x+t*pf0,g=deta f(x) end（2）.牛顿法：牛顿法是求无约束最优解的一种古典解析算法，其基本思想是 在寻找收敛速度最快的无约束最优化方法中

9、，在每次迭代时，用 适当的二次函数去近似目标函数f，并用迭代点指向近似二次 函数极小点的方向来构造搜索方向，然后精确地求近似二次函数 心上,-,、人上,f 4 r 心、上 的极小点，以这个极小点作为的极小点的近似值。牛顿法的迭代步骤：1）给定初始点和收敛精度；2）计算WS，H （七），:H顷小3）求x = x -K H（x ）t Vf （x ）4） 检查收敛精度，若口气+1 x 口V，则x X+1，停止；否则k=k+1，返回2）继续。牛顿法的优点是每次迭代都在牛顿方向进行一维搜索，避免了迭 代后函数值变大的现象，从而保持了牛顿法的二次收敛性，而对 初始点的选择没有严格要求。但是牛顿法也有缺点，

10、它对目标函 数要求严格，函数必须具有连续的一、二阶导数；海赛矩阵必须 正定且非奇异。还有牛顿法的计算复杂，存储量大。.共轭梯度法：共轭梯度法最早是由计算数学家Hestenes和几何学家Stiefel在20世纪50年代初为求解线性方程组AxA而各自独立提出的。在AxA而各自独立提出的。在为对称正定阵时，方程组A * 尤等价于最优化问题1min 1min xrAx brx 2 口xeRn 匕，由此，Hestenes和Stief的方法也可以看做是求二次函数极小值得共轭梯度法。在1964年Fetcher 和Reeves将这种方法推广到了非线性优化，得到了求一般函数minf (x)极小值的共轭梯度法。对

11、于无约束最优化问题xeRn，其f: R tR中连续可微有下界，共轭梯度法是解决这类问题中的最有效的数值方法之一。特别是在大规模问题上，共轭梯度法 因为算法简便、所需存储量小、收敛速度快等特性而在许多工程 科学领域采用。x对于无约束优化问题，给出一个初始值0，算法迭代产生点ix, x , J x列 12。假设某一 k是无约束优化问题的解，或者该 . x点列收敛于最优解。在第k +1次迭代中，当刖迭代点为k，产生下一个迭代点4+1产生下一个迭代点4+1 %吧，其中e Rn是搜索方向，ak 0是步长因子，它满足某线搜索终止条件。显然，每步迭代主要由两部分组成：一是搜索方向k ；另一是步长因子七。 求

12、解无约束优化问题的共轭梯度法是从求解线性方程组的线性 共轭梯度法推广而来的，其搜索方向是负梯度方向与上一次迭代 的搜索方向的线性组合，它表示为 d g , d = g + p dp00 k kk1 k-1，关于参数 k的不同取法对应于不同的共轭梯度法，著名的有HS方法,FR方法,PRP方 法,CD方法,LS方法，DY方法。其中FR方法、DY方法和CD方法 具有很好的收敛性质，但数值表现结果却差强人意，而PRP方法、 HS方法和LS方法对一般函数不具备收敛性，但当收敛时，往往 数值表现却很好。因此近年来研究出了混合共轭梯度法，许多学 者作出了尝试。焦宝聪、陈兰平和李娟对求解无约束优化问题提 出一

13、类三项混合共轭梯度算法，新算法将HS算法与DY方法相结 合，并在不需给定下降条件的情况下，证明了算法在Wolfe线搜 索原则下的收敛性，数值试验亦显示出这种混合共轭梯度算法较 之HS和PRP的优势。焦宝聪、陈兰平和潘翠英III。结合FR算法 和DY算法，给出了一类新的混合共轭梯度算法，并结合 Goldstein线搜索，在较弱的条件下证明了算法的收敛性。共轭 梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共貌方向去搜索，可以由较快的收敛速度找到最优 解求得极小点。.变尺度法：变尺度法也称为拟牛顿法，它是基于牛顿法的思想而又作 出了重大改进的一种方法，是由Davidon提出，经过 Fle

14、tcher和Powell加以发展和完善的，称为DFP变尺度 法。拟牛顿法的一般步骤为:a.给定初始点，初始对称正定矩阵a.给定初始点，初始对称正定矩阵0=精度0;b,计算搜索方向k)=b,计算搜索方向k)=Hkk;s=g）顼）y=g -kk kl kud判断终止准则是否满足；H =H +Ee令 k k置，转步骤(b).(不同的拟牛顿E法对应不同的k)DFP变尺度法的算法原理:_SSHyyTHH H + k k k k k kdfp算法中校正公式为 奸1k STykyHkyH为了保证k的正定性，在下面的算法迭代一定的次数后， 重置初始点和迭代矩阵再进行迭代。DFP变尺度法的算法步骤：X (0)H

15、 I 8 0给定初始点x ，初始矩阵0乃及精度；2)若口fX)春，停止，极小点为x(0)；否则转步骤3)；取沸=耳伽),令k - 0 ；维搜产法求t fX +t p)=mivfyt +tp)X(k+1) = X(k )+ tp(k)，转步骤5)；、Nf、Nf(Xk+Dg5)，停止，极小值点为x (k+1)X ；否则转步骤6)；qk+1= 乃人&工、 一 、若 ，令 ，转步骤3);否则转步骤7);令Hk LHk LHkf （而）0 （Xkyf X+i）vX）xM）fXk）H 侦而）-W）k, 取3=-气3=-气Yf（Xk+1） 置 k=k+1,步骤4)。DFP变尺度法的算法MATLAB程序：调用

16、格式：x,min f=min DFP(f,x0,var,eps) 其中，f：目标函数x0:初始点var自变量向量eps精度乂：目标函数取最小值时的自变量值min f :目标函数的最小值DFP的MATLAB程序代码如下：fuction x,min f=minDFP(f,x0,var,eps)%目标函数：f;%初始点：x0;%自变量向量：var;%目标函数取最小值时的自变量值:X；%目标函数的最小值:min f;format long;If nargin=3eps=1.0e-6;endx0=transpose(x0);n=length(var);syms l;H=eye(n,n);grad f=jacobian(f,var);v0=Funval(gradf,var,x0);p=-H*transpose(v0);k=0;while 1v=Funval(gradf,var,x0);tol =norm(v);if tol=epsx=x0;break;endy=x0+l*p;yf=Funval(f,var,y);a,b=minJT(yf,0,0.1);xm=minHJ(yf,a,b);x1=x0+xm*p;vk=Funval(gradf,var,x1);tol=norm(vk);if tol=epsx=x