最优化方法课程设计

《《最最优优化化方方法法》》课课程程设设计计题目：可行方向法分析与实现院系：数学与计算科学学院专业：统计学姓名学号：XXXX12007XXXXX指导教师：李丰兵日期：2015年01月22日摘要在各种优化算法中,可行方向法是非常重要的一种。可行方向法是通过直接处理约束问题，得到一个下降可行方向，从而产生一个收敛于线性约束优化问题的K-T点。本文主要介绍的Zoutendiji可行方向法是求解约束优化问题的一种有代表性的直接解法.在本次实验中，本人对该门课程中的线性约束非线性最优化问题进行了一定程度地了解和研究，而处理线性约束非线性最优化问题的关键是在求解过程中，不仅要使目标函数值单调下降，而且还要保证迭代点的搜索方向为下降可行方向。所以，本人使用利用线性规划方法来确定kd的可行方向法——Zoutendijk可行方向法进行处理。本人通过数学软件MATLAB探讨了优化设计的实现方法及实现验证的效果，更进一步地加深了对它的理解也提高了处理该问题的水平能力。而且该方法初始参数输入简单，编程工作量小，具有明显的优越性．关键词：Zoutendiji可行方向法，约束优化问题，下降可行方向。AbstractInavarietyofoptimizationalgorithms,thefeasibledescentmethodisaveryimportantone.Thefeasibledirectionmethodisbydirectlydealingwithconstraints,gettingafeasibledirection,toproduceaconvergenceinthek-tpointofthelinearconstrainedoptimizationproblems.Zoutendijifeasibledirectionmethodismainlyintroducedinthispapertosolvetheconstrainedoptimizationproblemofakindoftypicalanddirectsolution.Inthisexperiment,Wehaveacertaindegreeofunderstandingandresearchinginthiscourseoflinearconstrainednonlinearoptimizationproblem。Anddealingwithlinearconstrainednonlinearoptimizationproblem，thekeyistheprocessofsolving,weshouldnotonlymakeourobjectivefunctionvaluesdecreased,butalsotoensurethatthesearchingdirectionsofiterationpointsforthefeasibledirection.So,weareusingthelinearprogrammingmethodisusedtodeterminethefeasibledirectionmethod--Zoutendijkfeasibledirectionmethodforprocessing.WethroughmakeuseofthemathematicalsoftwareMATLAB,therealizationoftheoptimizationdesignmethodisdiscussed,andvalidatetheeffectoffurtherdeepeningtheunderstandingofimprovingtheabilitytodealwiththeproblemoflevel.Andthemethodissimpleininitialparametersinputting,Therefore,theprogramstoragelesscomputationalcomplexity.Keywords:Zoutendijifeasibledirectionmethod,Constrainedoptimizationproblems,Feasibledirection.目录1、引言........................................................................................................................12、可行方向法的描述............................................................................................12.1可行方向法.......................................................................................................12.2线性不等式约束的ZOUTENDIJKMETHOD.........................................................22.3算法实现...........................................................................................................33、数值实验..............................................................................................................43.1代码实现...........................................................................................................44、算法比较及缺点................................................................................................84.1随机方向搜索法...............................................................................................84.2复合型法...........................................................................................................84.3可行方向法........................................................................................................94.4缺点...................................................................................................................95、总结.......................................................................................................................95.1总结概括...........................................................................................................95.2个人感言...........................................................................................................96、参考文献：.........................................................................................................9最优化方法课程设计11、引言现在，可行方向法已发展成为求解约束优化问题的一类重要方法，其基本思想是：给定一个可行点(k)x之后，用某种方法确定一个改进的可行方向kd，然后沿方向kd，求解一个有约束的线搜索问题，得极小点k，按迭代公式计算：(k+1)(k)kkx=x+d，如果(k+1)x不是最优解，则重复上述步骤。各种不同的可行方向法的主要区别在于：选择可行方向kd的策略不同。大体上可分为三类：（1）用求解一个线性规划方法来确定kd。（2）利用投影矩阵来直接构造一个改进的可行方向kd。（3）利用既约梯度，直接构造一个改进的可行方向kd。其中ZoutendijkMethod就是利用线性规划方法来确定kd的。2、可行方向法的描述2.1可行方向法可行方向法是通过直接处理约束问题，得到一个下降可行方向，从而产生一个收敛于线性约束优化问题的K-T点。一般地，求解约束优化问题要比求解无约束优化问题复杂、困难，因为在求解过程中，不仅要使目标函数值单调下降，而且还要保证迭代点满足约束条件。因此，在求解过程中，要求产生的迭代点的搜索方向为下降可行方向。由于这时的约束为线性函数，因而可通过利用线性代数的知识和无约束优化方法来设计一些有效算法。2.1.1非线性约束Basicconceptmin()fx..stxFDescentdirectiond:()0.TfxdFeasibledirectiond:,[0,],0.xFxdF定义：非零向量d称为在点xF的一个可行方向,若0[0,]，，都有：,xFxdF。d0称为在点xF的一个改进的可行方向,若0[0,]，，都有：()()fxdfx，xdF2.2线性不等式约束的ZoutendijkMethod(P)min()fxs.t.bAxExe最优化方法课程设计2:kxDenote1122bAbAAb，Suchthat:1212,kkAxbAxbObviously:Descentd:()0.kTfxdFeasibled:10,0.AdEdSolving：01for()0.kTfxdsolve(P)toobtaindescentdirectiond.Since()0.kTfxdthen()()kkfxdfx,0,[0,].sodisthedescentdirection.02for10,0.AdEdsolve(P)toobtainfeasibledirectiond.since11,kAxb10,0AdEd，Exeso1111(),kAxdbAdb()e,0.kkExdExEdsince22kAxb,having2222(),0,[0,].kkAxdAxAdbsodisthefeasibledirection.03setfeasibledirectiond0,solving10,0.AdEdsince111111()=kkAxdAxAdbAdb,[0,]0，so10Ad.since()ee,kkExdExEdEd[0,]0，so0Ed.最优化方法课程设计32.2.1Subproblem(子问题)：（LP）min()kT