最优化课程设计

最优化方法课程设计最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决题目：黄金分割法及其算法实现院（系）：数学与计算科学专业：信息与计算科学课题类型：■验证性口设计性 工综合性 □软件开发2011年12月25日策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、同学、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱(OptimizationToolbox)中的函数，又可以通过算法变成实现相应的最优化计算。在最优化计算中一维最优化方法是优化设计中最简单、最基本的方法。一维搜索，又称为线性搜索，一维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一维问题来处理。一维问题的算法好坏，直接影响到最优化问题的求解速度。而黄金分割法是一维搜索方法中重要的方法之一，它适用于任何单峰函数求最小值的问题，甚至于对函数可以不要求连续，是一种基于区间收缩的极小点搜索算法。关键词：最优化、黄金分割法、MATLAB、算法、一维搜索AbstractOptimizationtheoryandmethodsandmoreattention,havepenetratedintotheproduction,management,business,military,decision-makingandotherfields,andoptimizationmodelsandmethodswidelyusedinindustry,agriculture,transportation,commerce,defense,construction,students,governmentvariousdepartmentsandagenciesandotherfields.Withtherapiddevelopmentofcomputertechnology,optimizationtheoryandmethodsfortherapidprogressoftheoptimizationproblemtosolvepracticalsoftwareisalsodevelopingrapidly.Which,MATLABsoftwarehasbecomethemostoptimizationsoftwareisoneofthemostwidelyused.WiththispowerfulcomputingplatformMATLAB,eitherusingMATLABoptimizationtoolbox(OptimizationToolbox)inthefunction,butalsocanachievetheappropriatealgorithmtooptimizeintothecalculation.Inthecalculationofone-dimensionaloptimizationoptimizationmethodistooptimizethedesignofthesimplest,mostbasicmethod.One-dimensionalsearch,alsoknownaslinearsearch,one-dimensionalproblemismulti-dimensionalproblembasedoniterativemethodsinnumericalcalculation,shouldbeone-dimensionalsearch,canalsomulti-dimensionalproblemintoanumberofone-dimensionalproblemtodealwith.One-dimensionalalgorithmsaredirectlyaffectedbythespeedofsolvingoptimizationproblems.Thegoldensectionmethodisaone-dimensionalsearchmethodisoneimportantmethod,whichappliestoanysinglepeakfunctionfortheminimumoftheproblem,evenonthefunctiondoesnotrequireacontinuous,interval-basedcontractionisaverysmallpointsearchalgorithm.Keywords:Optimization、Goldensectionmethod、MATLAB>Algorithm、One-dimensionalsearch目录摘要 2TOC\o"1-5"\h\z第一章引言 5\o"CurrentDocument"第二章最优化方法原理 62.1无约束问题的最优性条件 6\o"CurrentDocument"第三章黄金分割法的基本思想与原理 7\o"CurrentDocument"3.1黄金分割法基本思路： 7\o"CurrentDocument"3.2黄金分割法的基本原理与步骤 73.30.618法算法 83.4算法流程图 83.5用matlab编写源程序 9\o"CurrentDocument"第四章黄金分割法应用举例 10\o"CurrentDocument"例1 10\o"CurrentDocument"例2 11\o"CurrentDocument"第五章总结 12\o"CurrentDocument"5.1概括总结 12\o"CurrentDocument"5.2具体分工 12\o"CurrentDocument"5.3个人感言 12\o"CurrentDocument"参考文献 15第一章引言数学科学不仅是自然科学的基础，也是一切重要技术发展的基础。最优化方法更是数学科学里面的一个巨大的篇幅，在这个信息化的时代，最优化方法广泛应用于工业、农业、国防、建筑、通信与政府机关、管理等各个部门、各个领域;它主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题。而最优解问题是这些所有问题的中心，是最优化方法的重中之重，在求最优解问题中，有多种方法解决，我们在这里着重讨论无约束一维极值问题，即非线性规划的一维搜索方法之黄金分割法。黄金分割法也叫0.618法，属于区间收缩法，首先找出包含极小点的初始搜索区间，然后按黄金分割点通过对函数值的比较不断缩小搜索区间。当然要保证极小点始终在搜索区间内，当区间长度小到精度范围之内时，可以粗略地认为区间端点的平均值即为极小值的近似值。所以用0.618法得出的是比较精确的最优解了。本实验的运行环境是matlabR2009a版本的运行环境。第二章最优化方法原理2.1无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。定理1设f：RnTR1在点X处可微。若存在peRn，使 Vf(X)Tp<0则向量p是f在点x处的下降方向。定理2设f：RnTR1在点X*eRn处可微。若X*是无约束问题的局部最优解，则Vf(X*)=0由数学分析中我们已经知道，使Vf(x*)=0的点x为函数f的驻点或平稳点。函数f的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数f的鞍点。以上定理告诉我们，x*是无约束问题的的局部最优解的必要条件是：x*是其目标函数f的驻点。现给出无约束问题局部最优解的充分条件。定理3设f:RnTR1在点x*eRn处的Hesse矩阵V2f(X*)存在。若Vf(X*)=0，并且V2f(X*)正定则X*是无约束问题的严格局部最优解。一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。定理4设f：RnTR1，X*eRn，f是Rn上的可微凸函数。若有Vf(X*)=0则x*是无约束问题的整体最优解。第三章黄金分割法的基本思想与原理3.1黄金分割法基本思路：黄金分割法适用于［a,b］区间上的任何单股函数求极小值问题，对函数除要求“单峰”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。

黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间［Q,b］内适当插入两点al，a2，并计算其函数值。al，a2将区间分成三段，应用函数的单峰性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。3.2黄金分割法的基本原理与步骤一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法(0.618法)。如图所示rl=a+0.382(b-a)r2=a+0.618(b-a)如图所以新区间为何,r2］以为新区间，继续求新的试点黄金分割法是用于一元函数f(x)在给定初始区间［a,b］内搜索极小点a*的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。具体步骤是：在区间［a,b］内取点：al,a2把［a,b］分为三段。如果f(al)>f(a2),令a=a1,a1=a2,a2=a+r*(b一a)；如果f(al)<f(a2)，令b=a2,a2=al，al=a+r*(b一a)，如果|(b-a)/b|和|(yl-y2)/y2〔都大于收敛精度£重新开始。因为［a,b］为单峰区间，这样每次可将搜索区间缩小0.618倍或0.382倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区［a,b］逐步缩小，满足预先给定的精度时，即获得一维优化问题的近似最优解。3.30.618法算法给定区间［a,b］，及eps>0;计算r=a+0.382(b-a),u=a+0.618(b-a);;若f(r)>f(u)，转(4)，否则转(5)⑷若u-r<eps，则停，输出X*=u,f*=f(u)否则令a=r，r=u，u=a+0.618(b一a)，转(3)(5)若u-r<eps，则停，输出x*=r,f*=f(r)否则令b=u，u=r，r=a+0.382(b-a)，转(3)3.4算法流程图3.5用matlab编写源程序编写程序，并且输出每次的搜索区间。则源程序如下:f618程序function[x,fval,iter]=f618(a,b)iter=0;whileabs(b-a)>1e-5iter=iter+1;lambda=a+0.382*(b-a);miu=a+0.618*(b-a);[dy,f1]=fun1(lambda);[dy,f2]=fun1(miu);iff1>f2a=lambda;disp(['the'num2str(iter)'iterationsearchareais:['num2str(a)','num2str(b)']'])elseb=miu;disp(['the'num2str(iter)'iterationsearchareais:['num2str(a)','num2str(b)']'])endendx=(a+b)/2;[dy,fval]=fun1(x);funl程序function[dy,val]=fun1(x)%val=exp(-x)+exp(x);%dy=-exp(-x)+exp(x);%val=-((sin(x))八6*tan(1-x)*exp(30*x));%dy=-(6*(sin(x))八5*cos(x)*tan(1-x)*exp(30*x)+(sin(x))八6*(1/cos(1-x))八2*(-1)*exp(30*x)+(sin(x))八6*tan(1-x)*exp(30*x)*30);第四章黄金分割法应用举例4.1例1根据0.618算法编写程序，求函数f(x)=(sinx)6tan(1一x)e30x在区间lo,1]上的极大值。解：令g(X)=一f(x)=一(sinx)6tan(1一x)e30*，求ming(x)妇0,1]funl程序为：function[dy,val]=fun1(x)val=-((sin(x))"*tan(1-x)*exp(30*x));dy=-(6*(sin(x))八5*cos(x)*tan(1-x)*exp(30*x)+(sin(x))八6*(1/cos(1-x))八2*(-1)*exp(30*x)+(sin(x))"*tan(1-x)*exp(30*x)*30);取eps=1e-5运行结果：[x,fval,iter]=f618(0,1)theliteration search area is :[0.382,1]the2iteration search area is :[0.61808,1]the3iteration search area is :[0.76397,1]the4iteration search area is :[0.85413,1]the5iteration search area is :[0.90985,1]the6iteration search area is :[0.94429,1]the7iteration search area is :[0.94429,0.97872]the8iteration search area is :[0.95744,0.97872]the9iteration search area is :[0.96557,0.97872]the10iteration search area is :[0.96557,0.9737]the11iteration search area is :[0.96867,0.9737]the12iteration search area is :[0.96867,0.97178]the13iteration search area is :[0.96986,0.97178]the14iteration search area is :[0.96986,0.97104]the15iteration search area is :[0.97031,0.97104]the16iteration search area is :[0.97031,0.97077]the17iteration search area is :[0.97049,0.97077]the18iteration search area is :[0.97059,0.97077]the19iteration search area is :[0.97059,0.9707]the20iteration search area is :[0.97063,0.9707]the21iteration search area is :[0.97063,0.97067]the22iteration search area is :[0.97065,0.97067]the23iteration search area is :[0.97066,0.97067]the24iteration search area is :[0.97066,0.97067]x=0.9707fval=-4.1086e+010iter=24则ming(x)为4.1086e+010xe[0,1]例2求函数W(t)=e-1+et在[-1,1]内的极小值解：funl程序为：function[dy,val]=fun1(x)val=exp(-x)+exp(x);dy=-exp(-x)+exp(x);令eps=1e-5运行结果；[x,fval,iter]=f618(-1,1)theliterationsearch area is :[-1,0.236]the2iterationsearch area is :[-0.52785,0.236]the3iterationsearch area is :[-0.23606,0.236]the4iterationsearch area is :[-0.055732,0.236]the5iterationsearch area is :[-0.055732,0.12456]the6iterationsearch area is :[-0.055732,0.055688]the7iterationsearch area is :[-0.01317,0.055688]the8iterationsearch area is :[-0.01317,0.029384]the9iterationsearch area is :[-0.01317,0.013129]the10iterationsearch area is :[-0.0031238,0.013129]the11iterationsearch area is :[-0.0031238,0.0069202]the12iterationsearch area is :[-0.0031238,0.0030834]the13iterationsearch area is :[-0.00075262,0.0030834]the14iterationsearch area is :[-0.00075262,0.001618]the15iterationsearch area is :[-0.00075262,0.00071244]the16iterationsearch area is :[-0.00019297,0.00071244]the17iterationsearch area is :[-0.00019297,0.00036658]the18iterationsearch area is :[-0.00019297,0.00015283]the19iterationsearch area is :[-6.0873e-005,0.00015283]the20iterationsearch area is :[-6.0873e-005,7.1195e-005]the21iterationsearch area is :[-6.0873e-005,2.0745e-005]the22iterationsearch area is :[-2.9695e-005,2.0745e-005]the23iterationsearch area is :[-1.0427e-005,2.0745e-005]the24iterationsearch area is :[-1.0427e-005,8.8374e-006]the25iterationsearch area is :[-3.068e-006,8.8374e-006]the26iterationsearch area is :[-3.068e-006,4.2895e-006]x=6.1078e-007fval=2.0000iter=26则原式极小值为：6.1078e-007第五章总结5.1概括总结最开始接触黄金分割法大概要算初中时候学过的黄金分割点，是把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。其比值是一个无理数，取其前三位数字的近似值是0.618，所以也称为0.618法。然后在大学的最优化方法这门课上，我们又重新认识了黄金分割法，知道它不仅是最优化中解决无约束问题的方法中重要的一环，而且是不可或缺的方法。通过这次课程设计，我们重新学习了以前遗忘的知识，加深了记忆和理解。真正做到了理论和实践相结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的不足。为以后毕业设计总结了经验和教训将指导我未来的工作和学习，我会更加努力，取得更大的成绩。5.2具体分工本次课程设计中，我们小组的主要分工形式为：（1） 颜海峰同学主要负责将课本的理论与实际题目结合，并进行论文的撰写与修改；（2） 黄雷同学主要负责题目的求解，特别是利用matlab软件编写程序方便地将复杂的题目求解出来；（3） 蓝田同学主要负责资料的搜索与文献的查阅。以上为大致的分工，然而在实际问题的求解与操作过程中，分工并不是绝对的，大家都常常相互讨论研究，工作常常相互交叉进行，互相配合完成。5.3个人感言本次最优化课程设计中我的主要任务是负责资料的收集和论文的撰写。经过两个队友和我坚持不懈奋斗，最终完成了本次的课程设计。从开始选题到组队，再到组员分工，以及最后的实际操作，我们组的成员都体现出了相当强的凝聚力。在完成各自分工的同时，也与队友协作完成其他部分。但在协作过程中也存在着一些分歧，比如大家都在帮我找资料的时候，大家找到不同的了，会像吵架一样争着要用上自己收集的资料。但在最后，真理战胜了大家小小的虚荣。在收集的资料中，取其精华，去其糟粕。在撰写论文过程中我也得到了队友们的协助，但是各有各的排版风格，在各自的论文排版设计风格面前，我们遵照了老师的要求，完成了本次课程设计至关重要的最后一步。通过完成这次最优化课程设计，在解决问题的过程中，充分体会到了最优化方法对于解决一些实际问题的重要性。一个多星期的课程设计，虽然有些疲劳和困倦，但是带给了我很多我在课本上学不到的知识。实践是检验真理的唯一标准，没有实践，就不会发现和深刻体会知识的真实所在，只有通过了实践检验的真理，在自己的心里，才会得到认可。最优化课程设计的完成，让我懂得了真理重要性，只有理论和实践相结合，才能真正的掌握所学的的知识。——颜海峰在这次课程设计过程中，我不断地成长，不断地累积我的知识。不仅是知识的成长，并且学会了与队友沟通、合作，团队意识也得到了提高。同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致整项工作的失败。通过课程设计我才发现，一个人单单知道知识理论是远远不够的，还有结合实践，这样我们才能更好的掌握所学的知识。在这次设计过程中，体现出自己建模能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。通过这次编程也告诉了我一个问题不仅只有一种方