增广拉格朗日乘子法及其在约束优化问题的应用

毕业论文题目增广拉格朗日乘数法及在其在约束优化问题的应用学院数学科学学院专业信息与计算科学班级计算1001班学生高亚茹学号20100921032指导教师邢顺来二〇一四年五月二十五日济南大学毕业论文——I摘要增广拉格朗日乘子法作为求解约束优化问题的一种重要方法，近年来研究增广拉格朗日乘子法的应用显得更加重要。本文首要介绍了增广拉格朗日乘子法的产生，通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合，引出了现在对增广拉格朗日法的发展状况，概述了增广拉格朗日乘子法基本理论。然后具体说明了增广拉格朗日法在科学领域上的实际应用，如在供水系统和图像复原的应用，也证明了增广拉格朗日乘子法的实际应用性。关键词：增广拉格朗日乘子法；罚函数法；供水系统；图像复原济南大学毕业论文——IIABSTRACTAugmentedlagrangemultipliermethodsasanimportantmethodforsolvingconstrainedoptimizationproblems,recentstudiesinapplicationsofaugmentedlagrangemultipliermethodsisevenmoreimportant.Thispaperdescribesthegenerationofprimaryaugmentedlagrangemultipliermethod.ByinterpretingtheaugmentedlagrangianmultipliermethodsisthecombinationofpenaltyfunctionmethodsandLagrangemultipliermethods,Itisgiventoarecentdevelopmentofaugmentedlagrangianmethods.Thenisshownthebasictheoriesofaugmentedlagrangianmultipliermethods.Finallyitisspecifiedtheaugmentedlagrangianmethodonthepracticalapplicationsofscientificfields,suchaswatersupplyystemsandimagerestorations,alsoprovedaugmentedlagrangianmultipliermethodsofpracticalapplication.Keywords：AugmentedLagrangeMultiplierMethods；PenaltyFunctionMethodsWaterSupplySystems；ImageRestorations济南大学毕业论文——III目录摘要………………………………………………..…….….……………...IABSTRACT……………………………………….……………………..…………….II1前言…………………….…………………………………………….….……………..11.1增广拉格朗日函数法的产生与应用………………………………………..11.2研究增广拉格朗日函数法应用的意义………………………………………..12增广拉格朗日乘子法......……..….……………………….…..….………….32.1约束非线性规划…………………………………………………………………..32.2罚函数外点法…………………………….………………...………………..42.3拉格朗日乘子法………………………………………...…………………...62.4增广拉格朗日乘子法………………………………...…………………...72.4增广拉格朗日乘子法的计算……………………………...…………………...103增广拉格朗日乘子法的应用……………………………………….…………………123.1供水系统调度的增广拉格朗日函数优化方法……..………………………....123.2图像复原的增广拉格朗日函数优化方法………...…………………………….14结论......................………….………….……………………..….……...…..….………...17参考文献......................…………….…………………..….…..……………….………….18致谢......................………………….……………………..…….…………...…………….19济南大学毕业论文1--1前言1.1增广拉格朗日函数法的产生与应用在求解有约束条件的优化题目时，有一个重要方法，便是用适合的方法把约束优化问题，转变成无约束优化问题来进行求解。在求最佳的解的题目中，以美国知名学者约瑟夫起名的拉格朗日乘数法是一种探索三元以上函数的极值的方法，其中有若干个条件制约着这类函数的变量。它的主要解决方式就是，把一个具备n个变量与k个约束条件的求最佳解的问题，转换为一个具备kn个变量的方程组的极值问题，这里面的变量有一个特点，没有任何制约，就称为无约束变量。这种方法引入了一种没有过的的标量未知数，也就是拉格朗日函数参数[1]。罚函数方法是将具备约束条件然后求最好的解的问题变成为不具备制约条件的一种重要的方式，它们首先求解一个，也有可能是一系列的罚问题来得到最末的限制最好的解的问题的解。这样我们可以把罚问题中的目标函数称为一个罚函数。从这里看，增广拉格朗日函数法，我们还有另一种叫法便是使用增广拉格朗日函数来当成罚函数的不间断的可微准确罚函数法，跟序列罚函数法比一下，不可微准确罚函数法具备明显的长处。增广拉格朗日乘子法，是在拉格朗日乘子法的基础上，联合了罚函数外点法，把它们综合在一块的方法，它的本质上最根本的思想就是在之前的罚函数中，考虑引入拉格朗日乘子，这样做就有了增广拉格朗日函数。在寻找最优解的过程中，通过一直连续不断的改变拉格朗日乘子和惩罚因子来求解各异的拉格朗日函数，换句话说也就是使用无约束最小优化方法得到此拉格朗日函数的极小值点，再加上有这样的拉格朗日函数极值点就会不断的向一开始的目标函数的约束最好的点靠拢，根据收敛准则能够得到差不多近似的最优解[1]。增广拉格朗日乘子法，从本质上讲就是对拉格朗日乘子方法的延伸，要不就称为是一种序列没有制约的最小化技术。它的最初的想法是对执行可行性的限制标准给予了一个惩罚，在迭代自适应切换惩罚因子可以是拉格朗日乘子，解决了一系列的最小化问题后，以求目的可以逼近原问题的最优解，这样就逃避了单一使用拉格朗日乘子法或单一使用罚函数外点法有可能会出现的不好的地方。在实际遇到的问题中，增广拉格朗日乘子法被当成求解约束优化问题的一种重要方法，近年来的应用遍及工程、国防、经济、金融和社会科学等很多紧要的科学领域[1]。比方说，基于拉格朗日乘子法的水平井射孔优化设计问题，就是首先一开始采用了增广拉格朗日乘子法，然后结合油藏渗流模型，在考虑水平井井底流压或者定产量情况下，以获得最大产量还有最小井底流压为研究需求，对数不清的导流来对水平井射孔密度遍布情况来优化。增广拉格朗日乘子法的应用涉及很多的方面，因此，对增济南大学毕业论文2--广拉格朗日乘子法的应用的研究具有很大的意义。1.2研究增广拉格朗日函数法应用的意义关于增广拉格朗日乘子法的研究是一个重要的研究课题，其在很多领域具有广阔的应用前景。首先，近些年来，随着计算机的快速发展，增广拉格朗日乘子法对于求解变分不等式问题在构造数值算法时能起到很重要的作用。另外，增广拉格朗日乘子法可以用于许多实际问题中的优化设计，通过编写程序构造乘子函数，求解精度较高，是一种非常切实可行的设计优化方法。使用增广拉格朗日乘子法去解决别的实际问题中的变化的分量不等式问题，是值得我们继续研究的课题。济南大学毕业论文3--2.增广拉格朗日乘子法2.1约束非线性规划解决平常的不是线性的规划问题，比无约束问题和线性规划问题都要麻烦不简单的多。用一个简单的例子来说明这点，考虑问题[2],01,01,01..,)(min21212221xxxxtsxxxf这个问题的可行域是一个三角形，以及它的内部区域，)(xf的等值线则是以原点为圆心的同心圆。问题的最优解为Tx21,21*，最优值为21)(*xf。线性规划的最优解总是能够在可行域的顶点中找到，而顶点的数量是有限的，这就是单纯形法的基本出发点。而上面的例子说明：对于非线性规划问题，即使约束都是线性的，最优解也不一定在顶点。这就给求解它们带来了困难。另一方面，由于约束的存在，如果不存在约束，从任一个初始点)0(x出发，沿)(xf的负梯度方向进行一维搜索，便求得目标函数的无约束极小点T0,0。但是，有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，我们最远只能跑到边界上的一个点，当所取)0(x不在直线021xx上时，)1(x点就不会是最优解*x。因此，继续迭代下去寻求一个没见过的可行点是有必要的，使目标函数有更小的值。可是，沿)(xf在)1(x处的负梯度方向已经找不到可行点，所以梯度迭代已不能继续进行，尽管离最优解还可能很远。这正是约束非线性规划与无约束非线性规划的本质区别，也是求解约束问题的根本问题所在。为了克服这样的困难，也就是换另一句话说，当现有已经存在的点在区域的边缘上时，为了使迭代能不断的继续进行下去，不仅有需求搜索方向拥有使目标函数下降的可能性，还有要求在这个方向上有可行点。例如，有一个小线段整个包含在可行域内，像这样的方向称为可行方向。所以，在求解约束非线性规划迭代法的设计中，主要应在每个迭代点)(kx处构造出一个下降可行方向)(kd。解决约束非线性规划的另外一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题用其最优解作为原来问题的新的近似解。例如将目标函济南大学毕业论文4--数及约束条件中的非线性函数分别以他们的一阶泰勒多项式或二阶泰勒多项式近似替代，或以一无约束非线性规划近似代替等。2.2罚函数外点法根据现在已存在的制约特征情况，约束有两类情况，一种情况是等式，另一种情况是不等式，构建一种有可能的惩罚项，继而把它加到目标函数中去，让约束问题的求解，变换成为无约束问题的求解，这类惩罚的方式，在没有约束题目求解的过程当中，和其相关的那些小概率违反约束的迭代点，给它很大的目的数值，强制性的使这些没有约束问题的极小点，一直向可行的区域凑近，也可以不停坚持不断的在可行域内移动，终止到收敛于原来的约束问题的极小点[2]。罚函数方法中有一类情况是在可行性区域外进行的惩罚函数法，也能够叫为外点法，它对不遵守约束的迭代点在目标函数中加入符合的惩罚，但是针对可行点就不给予惩罚。这种方法的迭代点往往是在可行域的外部移动。考虑一般约束最优化问题.,,1,0)(,,,1,0)(..)(minljxhmixgtsxfji(2.1)定义辅助函数),()(),(xPxfxF其中)(xP可取如下形式miljjixhxgxP11,)()(,0max)(其中1,均为常数，通常取2。这样，转化为无约束问题),()(,minxPxfxFdef其中是很大的正数[2]。一般来讲我们将)(xP称为惩罚项，则被叫为惩罚因子，,xF被叫成惩罚函数。例2.1.1求解非线性规划.1)(..,)1()(min22221xxgtsxxxfdef定义惩罚函数济南大学毕业论文5--,1,)1()1(,1,)1()1(,0max)1(),(222222122221222221xxxxxxxxxxxF当当用解析法求解),(minxF，有,1),1(22,12),1(22222,2211xxxxxxFxxF当当令,0,021xFxF得到,112