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

业论文题目增广拉格朗日乘数法及在其在约束优化问题的应用学院数学科学学院专业信息与计算科学班级计算1001班学生高亚茹学号指导教师邢顺来二0一四年五月二十五日摘要增广拉格朗日乘子法作为求解约束优化问题的一种重要方法，近年来研究增广拉格朗日乘子法的应用显得更加重要。本文首要介绍了增广拉格朗日乘子法的产生，通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合，引出了现在对增广拉格朗日法的发展状况，概述了增广拉格朗日乘子法基本理论。然后具体说明了增广拉格朗日法在科学领域上的实际应用，如在供水系统和图像复原的应用，也证明了增广拉格朗日乘子法的实际应用性。关键词：增广拉格朗日乘子法；罚函数法；供水系统；图像复原ABSTRACTAugmentedlagrangemultipliermethodsasanimportantmethodforsolvingconstrainedoptimizationproblems,recentstudiesinapplicationsofaugmentedlagrangemultipliermethodsisevenmoreimportant.Thispaperdescribesthegenerationofprimaryaugmentedlagrangemultipliermethod.ByinterpretingtheaugmentedlagrangianmultipliermethodsisthecombinationofpenaltyfunctionmethodsandLagrangemultipliermethods,Itisgiventoarecentdevelopmentofaugmentedlagrangianmethods.Thenisshownthebasictheoriesofaugmentedlagrangianmultipliermethods.Finallyitisspecifiedtheaugmentedlagrangianmethodonthepracticalapplicationsofscientificfields,suchaswatersupplyystemsandimagerestorations,alsoprovedaugmentedlagrangianmultipliermethodsofpracticalapplication.Keywords：AugmentedLagrangeMultiplierMethods；PenaltyFunctionMethodsWaterSupplySystems；ImageRestorations目录TOC\o"1-5"\h\z摘要IABSTRACTII\o"CurrentDocument"1前言1\o"CurrentDocument"1.1增广拉格朗日函数法的产生与应用1\o"CurrentDocument"1.2研究增广拉格朗日函数法应用的意义1\o"CurrentDocument"2增广拉格朗日乘子法3\o"CurrentDocument"2.1约束非线性规划3\o"CurrentDocument"2.2罚函数外点法4\o"CurrentDocument"2.3拉格朗日乘子法6\o"CurrentDocument"2.4增广拉格朗日乘子法72.4增广拉格朗日乘子法的计算103增广拉格朗日乘子法的应用12\o"CurrentDocument"3.1供水系统调度的增广拉格朗日函数优化方法12\o"CurrentDocument"3.2图像复原的增广拉格朗日函数优化方法14吉^论17\o"CurrentDocument"参考文献18致谢191前言1.1增广拉格朗日函数法的产生与应用在求解有约束条件的优化题目时，有一个重要方法，便是用适合的方法把约束优化问题，转变成无约束优化问题来进行求解。在求最佳的解的题目中，以美国知名学者约瑟夫起名的拉格朗日乘数法是一种探索三元以上函数的极值的方法，其中有若干个条件制约着这类函数的变量。它的主要解决方式就是，把一个具备〃个变量与上个约束条件的求最佳解的问题，转换为一个具备nk个变量的方程组的极值问题，这里面的变量有一个特点，没有任何制约，就称为无约束变量。这种方法引入了一种没有过的的标量未知数，也就是拉格朗日函数参数⑴。罚函数方法是将具备约束条件然后求最好的解的问题变成为不具备制约条件的一种重要的方式，它们首先求解一个，也有可能是一系列的罚问题来得到最末的限制最好的解的问题的解。这样我们可以把罚问题中的目标函数称为一个罚函数。从这里看，增广拉格朗日函数法，我们还有另一种叫法便是使用增广拉格朗日函数来当成罚函数的不间断的可微准确罚函数法，跟序列罚函数法比一下，不可微准确罚函数法具备明显的长处。增广拉格朗日乘子法，是在拉格朗日乘子法的基础上，联合了罚函数外点法，把它们综合在一块的方法，它的本质上最根本的思想就是在之前的罚函数中，考虑引入拉格朗日乘子，这样做就有了增广拉格朗日函数。在寻找最优解的过程中，通过一直连续不断的改变拉格朗日乘子和惩罚因子来求解各异的拉格朗日函数，换句话说也就是使用无约束最小优化方法得到此拉格朗日函数的极小值点，再加上有这样的拉格朗日函数极值点就会不断的向一开始的目标函数的约束最好的点靠拢，根据收敛准则能够得到差不多近似的最优解⑴。增广拉格朗日乘子法，从本质上讲就是对拉格朗日乘子方法的延伸，要不就称为是一种序列没有制约的最小化技术。它的最初的想法是对执行可行性的限制标准给予了一个惩罚，在迭代自适应切换惩罚因子可以是拉格朗日乘子，解决了一系列的最小化问题后，以求目的可以逼近原问题的最优解，这样就逃避了单一使用拉格朗日乘子法或单一使用罚函数外点法有可能会出现的不好的地方。在实际遇到的问题中，增广拉格朗日乘子法被当成求解约束优化问题的一种重要方法，近年来的应用遍及工程、国防、经济、金融和社会科学等很多紧要的科学领域⑴。比方说，基于拉格朗日乘子法的水平井射孔优化设计问题，就是首先一开始采用了增广拉格朗日乘子法，然后结合油藏渗流模型，在考虑水平井井底流压或者定产量情况下，以获得最大产量还有最小井底流压为研究需求，对数不清的导流来对水平井射孔密度遍布情况来优化。增广拉格朗日乘子法的应用涉及很多的方面，因此，对增广拉格朗日乘子法的应用的研究具有很大的意义。1.2研究增广拉格朗日函数法应用的意义关于增广拉格朗日乘子法的研究是一个重要的研究课题，其在很多领域具有广阔的应用前景。首先，近些年来，随着计算机的快速发展，增广拉格朗日乘子法对于求解变分不等式问题在构造数值算法时能起到很重要的作用。另外，增广拉格朗日乘子法可以用于许多实际问题中的优化设计，通过编写程序构造乘子函数，求解精度较高，是一种非常切实可行的设计优化方法。使用增广拉格朗日乘子法去解决别的实际问题中的变化的分量不等式问题，是值得我们继续研究的课题。2.增广拉格朗日乘子法2.1约束非线性规划解决平常的不是线性的规划问题，比无约束问题和线性规划问题都要麻烦不简单的多。用一个简单的例子来说明这点，考虑问题[2]minf(x)=X2+X2,s.t.x+x-1>0,1-x>0,1-x2>0,这个问题的可行域是一个三角形，以及它的内部区域，f(x)的等值线则是以原.,一…一一(11V—1点为圆心的同心圆。问题的最优解为x*=土,1，最优值为f(x*)=1op22j2线性规划的最优解总是能够在可行域的顶点中找到，而顶点的数量是有限的，这就是单纯形法的基本出发点。而上面的例子说明：对于非线性规划问题，即使约束都是线性的，最优解也不一定在顶点。这就给求解它们带来了困难。另一方面，由于约束的存在，如果不存在约束，从任一个初始点x(0)出发，沿f(x)的负梯度方向进行一维搜索，便求得目标函数的无约束极小点G,0>。但是，有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，我们最远只能跑到边界上的一个点，当所取x(0)不在直线xi-x2=0上时，x(1)点就不会是最优解x*。因此，继续迭代下去寻求一个没见过的可行点是有必要的，使目标函数有更小的值。可是，沿f(x)在x(1)处的负梯度方向已经找不到可行点，所以梯度迭代已不能继续进行，尽管离最优解还可能很远。这正是约束非线性规划与无约束非线性规划的本质区别，也是求解约束问题的根本问题所在。为了克服这样的困难，也就是换另一句话说，当现有已经存在的点在区域的边缘上时，为了使迭代能不断的继续进行下去，不仅有需求搜索方向拥有使目标函数下降的可能性，还有要求在这个方向上有可行点。例如，有一个小线段整个包含在可行域内，像这样的方向称为可行方向。所以，在求解约束非线性规划迭代法的设计中，主要应在每个迭代点x以)处构造出一个下降可行方向d(k)o解决约束非线性规划的另外一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题用其最优解作为原来问题的新的近似解。例如将目标函数及约束条件中的非线性函数分别以他们的一阶泰勒多项式或二阶泰勒多项式近似替代，或以一无约束非线性规划近似代替等。2.2罚函数外点法根据现在已存在的制约特征情况，约束有两类情况，一种情况是等式，另一种情况是不等式，构建一种有可能的惩罚项，继而把它加到目标函数中去，让约束问题的求解，变换成为无约束问题的求解，这类惩罚的方式，在没有约束题目求解的过程当中，和其相关的那些小概率违反约束的迭代点，给它很大的目的数值，强制性的使这些没有约束问题的极小点，一直向可行的区域凑近，也可以不停坚持不断的在可行域内移动，终止到收敛于原来的约束问题的极小点［2］。罚函数方法中有一类情况是在可行性区域外进行的惩罚函数法，也能够叫为外点法，它对不遵守约束的迭代点在目标函数中加入符合的惩罚，但是针对可行点就不给予惩罚。这种方法的迭代点往往是在可行域的外部移动。考虑一般约束最优化问题minf(x)s.t.g(x)>0,i=1,・・・，m,(2.1)h(x)=0,j=1,…,l.定义辅助函数F(xq)=f(x)+bP(x),其中P(x)可取如下形式P(x)=工Imaxh-g(x)}L+X|h(x)|，，i=1J=1其中a,P>1均为常数，通常取a=P=2。这样，转化为无约束问题minF(x,^y^f(x)+bP(x),其中b是很大的正数［2］一般来讲我们将。P(x)称为惩罚项，b则被叫为惩罚因子，F(x,。)被叫成惩罚函数。例2.1.1求解非线性规划minf(x)d=(x-1)2+x2,s.t.g(x)=x>1.定义惩罚函数F(x,a)=(x-1)2+x2+almaxh—(x-1))1f(x-1)2+x2,当x>1,(x-1)2+x2+a(x-1)2,当x<1,用解析法求解minF3,a)，有dF=2(x-1),竺=!2x2当x2>:dxidx2'2。。2x+2a(x2-1),当x2<1,dxidx2'2令F。,牙=0,12得到rn「1]x1=ax1-2」_1+a_x*a易见，当aT+3时丁xa-x*=1。x*恰巧就是所求非线性规划的最优解⑵。用像这样的方法得到的没有约束问题的最优解，在平时普通的情况下是不会满足约束条件的，它是在可行域外部，当a的增大的时候，然后不断接近x*，所以称这种方法为外点法。在实际计算的过程中，考虑怎样选择惩罚因子a是非常有必要的。平时遇到这种情形时，我们的方式是取一个不断接近无穷大和严格递增的正数列｛r一个一个的求解minf(x)+a『(x),如此得到一个极小点的序列｛；｝在合适的条件下，最佳的顺序收敛域约束的解决方案。像如此行使一系列无约束题目，来取得限制问题最优解的方式，我们把它称叫为序列没有约束极小化方法，简称为SUMT方法。外点法的具体步骤为⑵：一开始给定初始点x(0)，初始化罚因子a1，把系数c>1放大，可以接受的误差8>0，k=1；以x(k-1)为初始点，解无约束问题

minf(x)+。kP(x)，设其极小点为x(k)；3.若QP(x(k))<£，则停，得近似解x(k)；否则，令bki=2k,k=k+1,回2。2.3拉格朗日乘子法若f,g「h.都是可微的，对于问题(2.D，能够成立拉格朗日函数L(x,L(x,人,日)=f(x)—工人g(x)一£日h(x).iii=1jjj=1Kuhn-Tucher条件[3]对于非线性规划(2.1)对于非线性规划(2.1)，f，g「h都是可微的’且则x*为(2.1)最优解的必要条件为:Vg(x*),ieI(x*),Vh.(x*),j='•••,l互为线性无关都有相对应的拉格朗日乘子人*和R*使VlC*,X*,日*)=Vf(x*)-2EX：Vg(x*)-2E日*Vh(则x*为(2.1)最优解的必要条件为:i=1j=1人*g(x*)=0,i=1,2,—,m,人.*>0,i=1,2,…,m,其中I(x*)={Ig(x*)=。}称为x*的有效约束指标集。i把满足K-T条件的可行点成为K-T点，最优点必定是K-T点。例2.2.1解非线性规划，并且求它的K-T点minf(x)=x2+x,s.t.g(x)=一x2一x2+9>0,

g(x)=-x一x+1>0.解非线性规划的K-T条件在这里为一人-2xI911-2x1-2」一人人(-x2-x2+9)=0,人(-x-x+1)=0,=0,(2.2)(2.3)(2.4)

(2.5)再加上约束条件-X2-X2+9>一人-2xI911-2x1-2」一人人(-x2-x2+9)=0,人(-x-x+1)=0,=0,(2.2)(2.3)(2.4)(2.5)(2)若(2.7)式等号不成立，则由(2.4)式有人广0，代入(2.2)式得(2.8)x(1+X)=0,1+2人x=0,(2.8)由气>0和(2.8)中第一式，得x1=0。再代入(2.6)式(等号成立)中和联系(2.8)中第二式，得X=6，x=—3。(3)若(2.7)式等号成立，则有(2.6)、(2.7)两个等式解得两个点「1+而1-而注意到s式，由心)式中第一行等式，知x1不能取官，而若取y，则x2就应取^ilH，这使(2.2)中第二行等式不能成立。所以，对于所求的非线性规划，存在唯一的K-T点。2.4增广拉格朗日乘子法增广拉格朗日乘子法，是在拉格朗日乘子法的基础上，联系了罚函数外点法的一种方式，它的基本思想就是把拉格朗日乘子放入惩罚函数中去，来建立增广拉格朗日函数，在过程中的最优解的搜索，通过不断的惩罚因子和拉格朗日通过调整乘法器，为了能够得到拉格朗日的作用是不同的，通过求解无约束最小优化来的最低点拉格朗日函数，和拉格朗日函数的极值点附近的原始目标函数的限制最优点的基础上，得到一个接近最优解的收敛标准[4]考虑问题(2.1)，可构造增广拉格朗日函数FG,X,口q)=f(x)+上工L(0,…(x))l-X2M口h(x)+宜h2(x).2bi，ijj2ji=1j=1j=1

1.考虑只存在等式约束的非线性优化问题(2.9)minf(x)h(x)=0i=1,,mi则优化问题的拉格朗日函数为FG,日函数，和拉格朗日函数的极值点附近的原始目标函数的限制最优点的基础上，得到一个接近最优解的收敛标准[4]考虑问题(2.1)，可构造增广拉格朗日函数FG,X,口q)=f(x)+上工L(0,…(x))l-X2M口h(x)+宜h2(x).2bi，ijj2ji=1j=1j=1(2.9)i=1i=1其中，c是一正的罚系数。增广拉格朗日函数法的基本思想就是通过求解给予人及c值下的没有约束最佳问题(2.10)和调整人及c的值的轮换进行，逐步接近优化问题(2.9)的解。所以将有约束优化问题的求解可以变为无约束优化问题的求解。这样，这个方法一方面具有了拉格朗日函数法还有罚函数法所具有的优点，另一方面较好的克服了它们所存在的不好的地方，叫成一种更有用的解决非线性约束优化题目的方法。例2.3.1用乘子法求解问题min2x2+x2-2xx,s.t.h(x)=x+x—1=0.解甲Cx,日,b)=2x2+x2—2xx—日(x+x—1)2，取b=2，h⑴=1，用解析法解min中(x,1,2)，得极小点为x⑴「+]x(1)=1=2x⑴3L2JL4J，修正h有H(2)=M1)—bh(x(1))=1—2-1=上。然后再解min中(x,+,2)，得到x(2)，像这42样继续。一般情况下，到了第k样继续。一般情况下，到了第k次迭代时，平(x,h(k),2)的极小点为x(k)「1(h(k)+2)_x(k)=1=6,x(k)L2J+(h(k)+2)L4」TOC\o"1-5"\h\z11H(k+1)=一H(k)+—.63—、一一一..一...一2(23¥即分别计算出的最优很容易看到，在那个时候kT+3，h(k)T—，x(k)——,—5^55)非线性规划，最优乘子和最优解。即分别计算出的最优2.考虑不等式约束情形先考虑只有不等式约束的问题minf(x),s.t.g(x)>0,i=1,2，…,m.利用等式约束的结果，引入变量y,，把上式化为等式约束问题minf(x),st.g(x)—y2>0,i=1,2,…,m.TOC\o"1-5"\h\zii这样，可定义增广拉格朗日函数0(x,y,日q)=f(x)-工日(g(x)-y2)+：工(gi(x)-y2)2,iii2ii=1i=1从而把问题转化为求解min(p(x,y,目q),为此，将(p的形式改写为1-，、、y2——9g(x)—日)ibii((1-，、、y2——9g(x)—日)ibiii=1I由<p的形式，可见为使<p取极小，y2的取值必定是iblmaxhbg.(x)—p.H.于是，可以上式代入成消去y，因此定义增广拉格朗日函数i0(x,p,b)=f(x)+二工lnaX0,p-bg(x))l-p21

2biiii=1总结以上，不等式约束问题也就可以变为没有约束问题min<p(x,p,b).例2.3.2问题一・1.1min2x2+—x2,s.t.x+x=1.最优解是x*=(0.25,0.75)，然后利用惩罚函数法和乘子法两种方法解决出它的迭代点列。解1.惩罚函数法，对于11c/

minF(x)=—x2+—x2+〜(x+x—1)2,

xck2162212

可求得最优解为Xk可求得最优解为Xk*二二I1+4c1+4c)kk2.乘子法，对于•,,、11c.八,八ckx可求得最优解为minL(x)=§X2+—x2+-k(x+x-1)2-^(k)(x+x-ckx可求得最优解为xk=3(c+日(k))——k1+4cxk=2.5增广拉格朗日乘子法的计算首先半光滑函数的定义[4]设G:宙n—宙m,是部分Lipschitz连续映射。我们把它叫为G在xe宙n是半光滑的，当①G在x处是方向可微的；(ii)对任意的Axe汕和HedG(x+Ax)且Ax—0，有G(x+Ax)-G(x)-H(Ax)=o(|A^||)进一步地，称G在xe宙n处是强半光滑的，如果G在x处是半光滑的，且对任意的Axe宙n和HedG(x+Ax)且Ax—0，有G(x+Ax)-G(x)-H(Ax)=o(||Ax||2)若C是沉n的一个非空闭的凸子集，对任何一个xe宙n，都有且只有的xeC使得||x-x|=minjx-圳:yec}称x是x在集合c上的投影，记作nC(x)。因此，投影算子nc:汕—c对于每一个xe宙n是有定义的，且是非扩张的。算法：选取原始问题的初始点x1e。,uke沛m，则第k+1步迭代点xk+1,uk+1通过+下式计算：

xk+ieargmin12|卜-xk|2+gF(xk+1,y,uk)|yeO,,uk+1=n(uk+bg(Xk+i))收敛性定理：设问题(2.1)解集乎是非空的，f:宙n♦宙n是单调的映射，g:宙n♦沛m是凸且可微的映射。O为欧式空间沉n的非空的闭凸子集及a>0。则按照增广拉格朗日方法解得的序列1*｝的聚点就是变分不等式问题(2.1)的解。3.增广拉格朗日乘子法的应用3.1供水系统调度的增广拉格朗日函数优化方法城市供水系统的优化调整的优化问题是一个大规模，非线性。基于对库恩一塔克的最优性必要条件，所提出的解决该问题的方法⑸要求其数学模型具有凸结构，也即就是要求将数学模型中的目标函数构造成凸函数⑹。以增广拉格朗日函数法为基础，对于城市供水系统的具体特点，用二级递阶结构，找出解决该优化调度问题的一种新的算法。3.1.1供水系统优化调度问题的数学模型城市供水系统是由给水泵站与供水管道按特定的配置式样结合而成的，供水泵站将水源中的水经过供水管道输送到用户⑸。具有n个节点的供水管网的运行情况可以用一下n-1个节点方程描述。(3.1)u-9一£Ssgn(p-p)p-p1/2=0,i=1,,n-1式中iiijij'ijieljI,与节点相邻的节点标号集合；u.供水泵站所在的第i个节点的供水流量；气第i个节点的需水量(负荷)；pi第i个节点的压力;sgn符号函数。定义为:|1,当a>0

冲⑷=1-1,当aV0;

(3.1)式中sgn符号函数。定义为:气摩阻系数，常数;a常数。对于城市供水系统的优化调度问题，一般以总供水成本作为目标函数。它包含两个部分：一部分是进入供水泵站内的水成本；另一部分是供水泵站内的电能消耗费用[7]其数学表达式为式中f(u,p)=£lvu+ru(p—ph)式中f(u,p)=£lvu+ru(p—ph)]iiiiiiieX供水泵站所在节点标号的集合；(3.2)进入第，个供水泵站水成本的价格;单位转换系数，常数;第i个供水泵站的地面标高。phi供水系统的调度方案除了必须满足(3.1)中的n-1个方程外，还必须满足下列不等式约束。首先必须保证系统的服务质量。也即p>pmin,i=1,…,n(3.3)Pmin为根据系统服务程度要求确定的第i个节点的压力下限值。其次，各供水泵站的i供水量必须满足下式Umin<U<Umax,ieX(3.4)这里，Umax及Umin为第i个给水泵站供水流量的上限，还有下限。(3.1)-(3.4)就建成了地方给水系统调度情况的数学模型。这样，该优化调度问题就是在系统的负荷0G=1,…n)都已知的条件下，确定满足方程(3.1)及不等式(3.3)、(3.4)i的各供水泵站的供水流量u(ieX)及节点压力pi(i=1,...,n)，使式(3.2)的值为最小。为了便于说明所提出的优化算法，令g(P,U,0)=u—0—Zssgn(p—p)|p—piiiijijijielj则这个优化调度问题的数学模型能够表示为minf(p,u)g(p,u,0)=0p—pmin>0U—Umin>01/2(3.5)城市给水系统优化调度问题(3.5)是一个复杂的非线性优化问题。这里，以增广拉格朗日函数法为基础，利用城市供水系统的具体特点，提出了解决该问题的一种新的算法⑻。对于一般的城市供水系统，在问题(3.5)最优解的轨迹上，必存在且仅存在一个节点k使得pk-pmin=0,而对另外的节点都有p>pmin,i。k;i=1,,n称第k个节点为控制点。关于供水系统的该特点，不失一般性，然后假定节点n为控制点，即P=Pmm。该优化问题基于增广拉格朗日乘子法的函数为F(p,u,习g(p,u,0)了i=1人,c)=f(p,u)+习W(F(p,u,习g(p,u,0)了i=1由增广拉格朗日函数基本原理，通过调整交替C,人的值，再求解无约束优化问题，最后则可求出供水系统优化调度问题的解。3.2图像复原的增广拉格朗日函数优化方法3.2.1图像复原模型的成立图像的还原，为的就是根据退化的图像，重新构建质量较好的一开始的图像，其中，还原的程度以及速度情况，一直以来都是图像办理范畴中考虑的要紧目标⑼。按照它的图像边缘保持特殊的性质，在图像复原里面中，全变分最小化模型具有明显的优先选择权［10］。可能存在的局限性，在帧丢失现象［12］中非合作和传输目标图像传感装置，难以满足后续加工及应用。在图像的传输和采集的过程中，我们有必要思考许多有可能图像质量退化的因素，例如外界因素，环境的动态性和复杂性、图像本身方面，可能存在的局限性，在帧丢失现象［12］中非合作和传输目标图像传感装置，难以满足后续加工及应用。考虑到图像的退化正常情况下是不能倒过来的，实现图像的高质量还原有必要结合图像的先验模型。图像的退化模型可以定义成：y=Ax+n(3.6)其中，y是退化图像，n是噪声［13(这种噪声一般情况下都是高斯白噪声或椒盐噪声，只想到高斯白噪声)，A是线性退化算子(一般可以写成卷积形式)，x是待复原的原始图像。

图像的还原是由退化图像y和算子A来让一开始图像x的高程度还原。图像的还原模型往往具备信度项和正则化项：minf(x)=入项)+||Ax-y||j(3.7)其中，4(x)是正则项，人〉0为正则化参数。全变分模型抑制图像噪声［14,］所以被广泛用于图像的复原。给定mxn的二维灰度图像x，它的离散全变分模型能够定义成：TV(x)=||(Dx,Dx)\按照所使用的矩阵的范数，能够更加强的区别各项同性和各向异性全变分TVTV(x)=||(Dx,Dx)||

isohv订=芯n.(Dx)2+(Dx)2hi,jvi,ji=1j=1TV(x)=||(Dx,Dx)||=l|Dhx；1+IDv^l此中，Dh和D前一个指的是水平方向上，后一个指的是竖直方向上的梯度算子，矩阵、范数则是把悉数元素的绝对值加起来。全变分图像复原模型为：argminf(x)=MTV(x)+—||Ax一y||2(3.8)x尸关于图像恢复的问题，各向同性TV通常可以得到更好的恢复效果。因此，我们认为图像的各向同性的总变异的恢复模型的算法。3.2.2图像复原问题的增广拉格朗日函数算法用辅助变量u代换TV里面的x，(3.8)式等效变成解一下等式约束优化问题:1(3.9)(3.10)argmin人TV(u)—||Ax-y||2x,us.t.u=x将各向同性TV代入(3.8)式，可以得到：(3.9)(3.10)argminf(x)=X||(Dx,Dx)+—||Ax一y||2x"把辅助变量u和v加入，(3.10)式就能变成下面的等式约束优化题目：

(3.11)argminX||(w,v)|+—||Ax-y||2(3.11)u,v,xs.t.u=Dx,v=Dx通过以上各式的转化，原始的全变分图像复原问题，便转化成了等价的等式约束优化问题，进一步地便可以利用增广拉格朗日算法对以上等式约束问题进行高效的求解。(3.9)式对应的增广拉格朗日函数为：15L(x,u,k,5)=XTV(u)+项|Ax一y||2+kt(u一x)+项|Ax一y||2(3.12)其中，k为拉格朗日乘子，a>0为惩罚参数。增广拉格朗日方法具有无条件收敛等优点，使得它在TV图像复原问题中具有独到的优势。目标函数(3.12)通过简单的变换，可以得到改良的增广拉格朗日目标函数形式：-.1,,,,5,,,,一—L(x,u,p,5)=XTV(u)+211Ax一y||2+_||u一x+p||2(3.13)(3.14)(3.15)为了使求解的时候可以简便些，我们利用非精确的增广拉格朗日方法，使用交替更新x(3.14)(3.15)x=(AhA+5)-1(AHy+5(u+p))

k+1kkkku=argminX/5TV(u)+u一(x一p)||2k+1ukiso2k+1kFp=p+u一xk+1kk+1k+15=p5k+1k其中，ah表示矩阵A的共轭转置，1<P<2。假若A是卷积算子，可以利用快速傅里叶变换，也可以利用离散余弦变换来计算Ax和AHy。方程(3.15)事实上是一个各向同性TV图像去噪声问题。理论分析表明，当5^<5max时，可以验证收敛性以及解的最优性。如果取P=1，可以得到交替方向乘子法。许多的以增广拉格朗日为基础的TV图像还原算法都使用交替方向乘子法求解［15。］除此之外，增广拉格朗日也可以广泛应用于压缩感知、基于字典的图像复原问题、矩阵填充问题、鲁棒主成分分析问题等。结论增广拉格朗日乘子法作为一种解决含有约束条件的然后求最好的解的方法，用于工程、国防、经济、金融和社会科学等很多方面。因此，探讨增广拉格朗日乘子法有很大意义。通过说明增广拉格朗日乘子法的产生和发展，从而实现增广拉格朗日乘子法更好的应用。其中增广拉格朗日乘子法作为对罚函数外点法和拉格朗日乘子法的结合，求解精度较高，是一种非常切实可行的设计优化方法。本文通过实际应用的例子说明了增广拉格朗日惩罚在应用过程中，首先对实际问题建立数学模型，再使用本方法可以加快找到最优结果的速度，也使最优结果更精确。总结目前的增广拉格朗日乘子法的应用，在实际应用时，建立模型后计算较为复杂，因此和计算机结合，编写相应算法会更好。参考文献施光燕，钱伟懿，庞丽萍.最优化方法[M].北京:高等教育出版社,2004.王莉，单锋，王诗云.具有约束条件的变分不等式的可行的增广拉格朗日方法[J].生物科学学报,2011,26(2)351-362FriedmanA.Variationalprincipleandfree-boundaryproblems[M].NewYork:Johnwiley,1982,1-56Facchinei,PangJongshi.Finite-Dimensionalvariationalinequalitiesandcomplementarityproblems[M].NewYork:Springer-Verlag,2003,1-406.李光泉，郑丕谔，仲伟俊.城市供水管网系统的优化调度.系统工程学报.1987.(1):59-66仲伟俊，陈森发，徐南荣.供水系统调度的增广拉格朗日函数优化方法南京工学院学报1989(2):13-19仲伟俊，陈森发，徐南荣城市供水系统调度的递阶优化方法。南京工学院学报1987(4):65-72Bertskasdp.MultiplierMethods:ASurvey.Automatica,1976;1