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

增广拉格朗日乘子法及其在约束优化问题的应用 题 目 增广拉格朗日乘数法及在 其在约束优化问题的应用 学 院 数学科学学院 专 业 信息与计算科学 班 级 计算1001班 学 生 高亚茹 学 号 20100921032 指导教师 邢顺来 二〇一四年 五 月二十五日 济南大学毕业 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 摘 要 增广拉格朗日乘子法作为求解约束优化问题的一种重要方法，近年来研究增广拉格朗日乘子法的应用显得更加重要。本文首要介绍了增广拉格朗日乘子法的产生，通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合，引出了现在对增广拉格朗日法的发展状况，概述了增广拉格朗日乘子法基本理论。然后具体说明了增广拉格朗日法在科学领域上的实际应用，如在供水系统和图像复原的应用，也证明了增广拉格朗日乘子法的实际应用性。 关键词:增广拉格朗日乘子法;罚函数法;供水系统;图像复原 I — — 济南大学毕业论文 ABSTRACT Augmented lagrange multiplier methods as an important method for solving constrained optimization problems, recent studies in applications of augmented lagrange multiplier methods is even more important. This paper describes the generation of primary augmented lagrange multiplier method. By interpreting the augmented lagrangian multiplier methods is the combination of penalty function methods and Lagrange multiplier methods, It is given to a recent development of augmented lagrangian methods. Then is shown the basic theories of augmented lagrangian multiplier methods. Finally it is specified the augmented lagrangian method on the practical applications of scientific fields, such as water supply ystems and image restorations, also proved augmented lagrangian multiplier methods of practical application. Key words:Augmented Lagrange Multiplier Methods;Penalty Function Methods Water Supply Systems ;Image Restorations II — — 济南大学毕业论文 目 录 摘要………………………………………………..…….….…………….. .I ABSTRACT……………………………………….……………………..…………….II 1前言…………………….…………………………………………….….……………..1 1.1增广拉格朗日函数法的产生与应用………………………………………..1 1.2研究增广拉格朗日函数法应用的意义………………………………………..1 2增广拉格朗日乘子法......……..….……………………….…..….………….3 2.1约束非线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 …………………………………………………………………..3 2.2罚函数外点法…………………………….………………...………………..4 2.3拉格朗日乘子法………………………………… ……...…………………...6 2.4增广拉格朗日乘子法 ………………………… ……...…………………...7 2.4增广拉格朗日乘子法的计算……………………… ……...…………………... 10 3 增广拉格朗日乘子法的应用……………………………………….… …… ………… 12 3.1供水系统调度的增广拉格朗日函数优化方法……..……………… ……….... 12 3.2图像复原的增广拉格朗日函数优化方法………...…………………………….14 结论......................………….………….……………………..….……...…..….………...17 参考文献......................…………….…………………..….…..……………….………….18 致谢......................………………….……………………..…….…………...…………….19 III — — 济南大学毕业论文 1 前言 1.1 增广拉格朗日函数法的产生与应用 在求解有约束条件的优化题目时，有一个重要方法，便是用适合的方法把约束优化问题，转变成无约束优化问题来进行求解。在求最佳的解的题目中，以美国知名学者约瑟夫起名的拉格朗日乘数法是一种探索三元以上函数的极值的方法，其中有若干个条件制约着这类函数的变量。它的主要解决方式就是，把一个具备个变量与个nk n，k约束条件的求最佳解的问题，转换为一个具备个变量的方程组的极值问题，这里面的变量有一个特点，没有任何制约，就称为无约束变量。这种方法引入了一种没 [1]有过的的标量未知数，也就是拉格朗日函数参数。 罚函数方法是将具备约束条件然后求最好的解的问题变成为不具备制约条件的一种重要的方式，它们首先求解一个，也有可能是一系列的罚问题来得到最末的限制最好的解的问题的解。这样我们可以把罚问题中的目标函数称为一个罚函数。从这里看，增广拉格朗日函数法，我们还有另一种叫法便是使用增广拉格朗日函数来当成罚函数的不间断的可微准确罚函数法，跟序列罚函数法比一下，不可微准确罚函数法具备明显的长处。 增广拉格朗日乘子法，是在拉格朗日乘子法的基础上，联合了罚函数外点法，把它们综合在一块的方法，它的本质上最根本的思想就是在之前的罚函数中，考虑引入拉格朗日乘子，这样做就有了增广拉格朗日函数。在寻找最优解的过程中，通过一直连续不断的改变拉格朗日乘子和惩罚因子来求解各异的拉格朗日函数，换句话说也就是使用无约束最小优化方法得到此拉格朗日函数的极小值点，再加上有这样的拉格朗日函数极值点就会不断的向一开始的目标函数的约束最好的点靠拢，根据收敛准则能 [1]够得到差不多近似的最优解。 增广拉格朗日乘子法，从本质上讲就是对拉格朗日乘子方法的延伸，要不就称为是一种序列没有制约的最小化技术。它的最初的想法是对执行可行性的限制标准给予了一个惩罚，在迭代自适应切换惩罚因子可以是拉格朗日乘子，解决了一系列的最小化问题后，以求目的可以逼近原问题的最优解，这样就逃避了单一使用拉格朗日乘子法或单一使用罚函数外点法有可能会出现的不好的地方。 在实际遇到的问题中，增广拉格朗日乘子法被当成求解约束优化问题的一种重要方法，近年来的应用遍及工程、国防、经济、金融和社会科学等很多紧要的科学领域[1]。比方说，基于拉格朗日乘子法的水平井射孔优化设计问题，就是首先一开始采用了增广拉格朗日乘子法，然后结合油藏渗流模型，在考虑水平井井底流压或者定产量情况下，以获得最大产量还有最小井底流压为研究需求，对数不清的导流来对水平井射孔密度遍布情况来优化。增广拉格朗日乘子法的应用涉及很多的方面，因此，对增 1 - - 济南大学毕业论文 广拉格朗日乘子法的应用的研究具有很大的意义。 1.2 研究增广拉格朗日函数法应用的意义 关于增广拉格朗日乘子法的研究是一个重要的研究课题，其在很多领域具有广阔的应用前景。 首先，近些年来，随着计算机的快速发展，增广拉格朗日乘子法对于求解变分不等式问题在构造数值算法时能起到很重要的作用。另外，增广拉格朗日乘子法可以用于许多实际问题中的优化设计，通过编写程序构造乘子函数，求解精度较高，是一种非常切实可行的设计优化方法。使用增广拉格朗日乘子法去解决别的实际问题中的变化的分量不等式问题，是值得我们继续研究的课题。 2 - - 济南大学毕业论文 2. 增广拉格朗日乘子法 2.1 约束非线性规划 解决平常的不是线性的规划问题，比无约束问题和线性规划问题都要麻烦不简单 [2]的多。用一个简单的例子来说明这点，考虑问题 22minf(x),x，x,12 s.t.x，x,1,0,12 1,x,0,1 1,x,0,2 这个问题的可行域是一个三角形，以及它的内部区域，的等值线则是以原f(x) T111,,**f(x),点为圆心的同心圆。问题的最优解为，最优值为。 x,,,,222,, 线性规划的最优解总是能够在可行域的顶点中找到，而顶点的数量是有限的，这就是单纯形法的基本出发点。而上面的例子说明:对于非线性规划问题，即使约束都是线性的，最优解也不一定在顶点。这就给求解它们带来了困难。另一方面，由于约 (0)x束的存在，如果不存在约束，从任一个初始点出发，沿的负梯度方向进行一f(x) T维搜索，便求得目标函数的无约束极小点。但是，有了约束，在进行一维搜索，，0,0 时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，我们最远只能跑 (0)(1)*xxx到边界上的一个点，当所取不在直线上时，点就不会是最优解。x,x,012 因此，继续迭代下去寻求一个没见过的可行点是有必要的，使目标函数有更小的值。 (1)x可是，沿在处的负梯度方向已经找不到可行点，所以梯度迭代已不能继续进f(x) 行，尽管离最优解还可能很远。这正是约束非线性规划与无约束非线性规划的本质区别，也是求解约束问题的根本问题所在。为了克服这样的困难，也就是换另一句话说，当现有已经存在的点在区域的边缘上时，为了使迭代能不断的继续进行下去，不仅有需求搜索方向拥有使目标函数下降的可能性，还有要求在这个方向上有可行点。例如，有一个小线段整个包含在可行域内，像这样的方向称为可行方向。所以，在求解约束 (k)x非线性规划迭代法的设计中，主要应在每个迭代点处构造出一个下降可行方向(k)d。 解决约束非线性规划的另外一个途径是:在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题用其最优解作为原来问题的新的近似解。例如将目标函 3 - - 济南大学毕业论文 数及约束条件中的非线性函数分别以他们的一阶泰勒多项式或二阶泰勒多项式近似替代，或以一无约束非线性规划近似代替等。 2.2 罚函数外点法 根据现在已存在的制约特征情况，约束有两类情况，一种情况是等式，另一种情况是不等式，构建一种有可能的惩罚项，继而把它加到目标函数中去，让约束问题的求解，变换成为无约束问题的求解，这类惩罚的方式，在没有约束题目求解的过程当中，和其相关的那些小概率违反约束的迭代点，给它很大的目的数值，强制性的使这些没有约束问题的极小点，一直向可行的区域凑近，也可以不停坚持不断的在可行域 [2]内移动，终止到收敛于原来的约束问题的极小点。 罚函数方法中有一类情况是在可行性区域外进行的惩罚函数法，也能够叫为外点法，它对不遵守约束的迭代点在目标函数中加入符合的惩罚，但是针对可行点就不给予惩罚。这种方法的迭代点往往是在可行域的外部移动。 考虑一般约束最优化问题 minf(x) s.t.g(x),0,i,1,？,m, (2.1) i h(x),0,j,1,？,l.j 定义辅助函数 F(x,,),f(x)，,P(x), 其中可取如下形式 P(x) ml,,,,,,P(x),max0,,g(x)，h(x), ,,ij,,11ij ,,,,1其中均为常数，通常取。 ,,,,2 这样，转化为无约束问题 def ，，minFx,,,f(x)，,P(x), [2],其中是很大的正数。 ,，，Fx,,,P(x)一般来讲我们将称为惩罚项，则被叫为惩罚因子，被叫成惩罚函数。 例 2.1.1 求解非线性规划 def22minf(x),(x,1)，x,12 s.t.g(x),x,1.2 定义惩罚函数 4 - - 济南大学毕业论文 222,,(,),(,1)，，max0,,(,1)Fxxxx,,,,122 22 ,(,1)，,,1,xx当x122,,222(x,1)，x，,(x,1),当x,1,1222, 用解析法求解，有 minF(x,,) 2x当x,1,,,F,F2,2 ,2(x,1),,,1xxx,x当x,,2，2(,1),,1,12222, ,F,F令 ,0,,0,,x,x12 得到 1，，x，，1*,,,x,,, ,,,x,,2，，,，1，， 易见，当时 ,,，, 1，，**。 x,x,,,,1，， [2]*x恰巧就是所求非线性规划的最优解。 用像这样的方法得到的没有约束问题的最优解，在平时普通的情况下是不会满足 *x约束条件的，它是在可行域外部，当,的增大的时候，然后不断接近，所以称这种方法为外点法。 在实际计算的过程中，考虑怎样选择惩罚因子,是非常有必要的。平时遇到这种 ,,,情形时，我们的方式是取一个不断接近无穷大和严格递增的正数列，一个一个的k求解 minf(x)，,P(x), k *,,x如此得到一个极小点的序列，在合适的条件下，最佳的顺序收敛域约束的解决方k 案。像如此行使一系列无约束题目，来取得限制问题最优解的方式，我们把它称叫为 SUMT序列没有约束极小化方法，简称为方法。 [2]外点法的具体步骤为: (0)c,1,,0x,1.一开始给定初始点，初始化罚因子，把系数放大，可以接受的误差，1 k,1; (k,1)x2.以为初始点，解无约束问题 5 - - 济南大学毕业论文 ， min()()fxPx，,k (k)设其极小点为; x (k)(k)3.若，则停，得近似解;否则，令回2。 x,,c,,k,k，1,,P(x),,k,1kk 2.3 拉格朗日乘子法 若f,g,h都是可微的，对于问题(2.1)，能够成立拉格朗日函数 ij ml ，，Lx,,,,,f(x),,g(x),,h(x).,,iijj,1,1ij [3]Kuhn-Tucher条件: f,g,h 对于非线性规划(2.1)，若都是可微的,且ij ****x,g(x),i,I(x),,h(x),j,1,？,l互为线性无关，则为(2.1)最优解的必要条件为:ij **,和使 都有相对应的拉格朗日乘子, ml********，，,Lx,,,,,,f(x),,,g(x),,,h(x),0, i,,xijji,1j,1 **,g(x),0,i,1,2,？,m,ii *,,0,i,1,2,？,m,i ***x其中称为的有效约束指标集。 ,,I(x),i|g(x),0i 把满足K-T条件的可行点成为K-T点，最优点必定是K-T点。 例2.2.1 解非线性规划，并且求它的K-T点 2minf(x),x，x,12 22s.t.g(x),,x,x，9,0, 112 g(x),,x,x，1,0.212解 非线性规划的K-T条件在这里为 ,2x2x,1，，，，，，11,,,,,0， (2.2) 12,,,,,,,2x1,1，，，，2，， 22 (2.3) ,(,x,x，9),0,112 ,(,x,x，1),0, (2.4) 212 6 - - 济南大学毕业论文 (2.5) ,,0,,,0,12 再加上约束条件 22 (2.6) ,x,x，9,0,12 (2.7) ,x,x，1,0.12 (1)若(2.6)式等号不成立，则由(2.3)式有，再代入(2.2)式得，这和(2.4),,0,,-112矛盾。因此(2.6)式等号必成立。 (2)若(2.7)式等号不成立，则由(2.4)式有，代入(2.2)式得 ,,02 (2.8) x(1，,),0,1，2,x,0,1112 由和(2.8)中第一式，得。再代入(2.6)式(等号成立)中和联系(2.8)中第二,,0x,011 1,,，x,,3式，得。 126 (3)若(2.7)式等号成立，则有(2.6)、(2.7)两个等式解得两个点 TT,,,,1,171，171，171,17,,,,及。 x,,,,,,,2222,,,, 1，171-17注意到(2.5)式，由(2.2)式中第一行等式，知x不能取，而若取，则x就1222 1，17应取，这使(2.2)中第二行等式不能成立。 2 所以，对于所求的非线性规划,存在唯一的K-T点。 2.4 增广拉格朗日乘子法 增广拉格朗日乘子法，是在拉格朗日乘子法的基础上，联系了罚函数外点法的一种方式，它的基本思想就是把拉格朗日乘子放入惩罚函数中去，来建立增广拉格朗日函数，在过程中的最优解的搜索，通过不断的惩罚因子和拉格朗日通过调整乘法器，为了能够得到拉格朗日的作用是不同的，通过求解无约束最小优化来的最低点拉格朗日函数，和拉格朗日函数的极值点附近的原始目标函数的限制最优点的基础上，得到 [4]一个接近最优解的收敛标准。 考虑问题(2.1)，可构造增广拉格朗日函数 mll1,222,,，，,,Fx,,,,f(x)，max(0,,g(x)),,h(x)，h(x). ,,,,,,,,,,iiijjj22,,,11,1ijj 7 - - 济南大学毕业论文 1. 考虑只存在等式约束的非线性优化问题 minf(x) (2.9) h(x),0i,1,？,mi 则优化问题的拉格朗日函数为 mmc2 (2.10) ，，,,Fx,,,c,f(x)，,h(x)，H(x),,iii2,,11ii其中，是一正的罚系数。 c 增广拉格朗日函数法的基本思想就是通过求解给予及值下的没有约束最佳c,问题(2.10)和调整及的值的轮换进行，逐步接近优化问题(2.9)的解。所以将有约束c, 优化问题的求解可以变为无约束优化问题的求解。这样，这个方法一方面具有了拉格 朗日函数法还有罚函数法所具有的优点，另一方面较好的克服了它们所存在的不好的 地方，叫成一种更有用的解决非线性约束优化题目的方法。 例 2.3.1 用乘子法求解问题 22min2x，x,2xx,1212 s.t.h(x),x，x,1,0.12解 222， ，，,x,,,,,2x，x,2xx,,(x，x,1)121212 (1),,2取，，用解析法解，得极小点为 min,(x,1,2),1, (1)1，，，，x21x(1),,， ,,,,(1)3x4，，2，， 11(2)1(2),(1),h(x(1)),1,2,,x,,,，，min,x,,2修正有。然后再解，得到，像这,242 (k)样继续。一般情况下，到了第次迭代时，的极小点为 ,(x,,,2)k (k)(k)1,，，，，(，2)x(k)16x,,, ,,,,(k)(k)1,，(2)x2，，4，， 11(k，1)(k),,,，. 63 T223,,(k)()kk,，,,,很容易看到，在那个时候，，,即分别计算出的最优x,,,,555,,非线性规划，最优乘子和最优解。 2. 考虑不等式约束情形 先考虑只有不等式约束的问题 8 - - 济南大学毕业论文 minf(x), s.t.g(x),0,i,1,2,？,m.i 利用等式约束的结果，引入变量，把上式化为等式约束问题 yi minf(x), 2s.t.g(x),y,0,i,1,2,？,m.ii 这样，可定义增广拉格朗日函数 mm,222~ (x,y,,),f(x),(g(x),y)，(gi(x),y),,,,,,,iiii2,,11ii从而把问题转化为求解 ~ min,(x,y,,,,), ~为此，将的形式改写为 , 22m,,,,1,,，，2~i,,,,,,，,,, (x,y,,)f(x)y(g(x)),,,,iii,,,,22,,，，,1i,, 2~~由的形式，可见为使取极小，的取值必定是 ,,yi 122,,y,,,max0,,g(x),,. iii, ~y于是，可以上式代入消去，因此定义增广拉格朗日函数 ,i m122~ ,,,,,(x,,,,),f(x)，max(0,,,,g(x)),,,,iii2,,1i 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 以上，不等式约束问题也就可以变为没有约束问题 ~ min,(x,,,,).例 2.3.2 问题 1122minx，x,12 26 s.t.x，x,1.12 *最优解是，然后利用惩罚函数法和乘子法两种方法解决出它的迭代点x,(0.25,0.75) 列。 解 1. 惩罚函数法，对于 c11222kminF(x),x，x，(x，x,1), ck1212x262 9 - - 济南大学毕业论文 可求得最优解为 T*,,cc3kkk,,x,,. ,,，c，c1414,,kk2.乘子法，对于 c11222()kk minL(x),x，x，(x，x,1),,(x，x,1),121212ckx262 可求得最优解为 T(k)(k),,c，c，3(),,kkk,,x,,. ,,，c，c1414,,kk 2.5 增广拉格朗日乘子法的计算 [4]首先半光滑函数的定义: nnmx,,设是部分Lipschitz连续映射。我们把它叫为在是半光滑的，当 G:,,,,G(i)在x处是方向可微的; G n,x,0,x,,和且，有 (ii) 对任意的H,,G(x，,x) G(x，,x),G(x),H(,x),;(,x) nx,,x 进一步地，称在处是强半光滑的，如果在处是半光滑的，且对任意的GG n,x,0,x,,和且，有 H,,G(x，,x) 2G(x，,x),G(x),H(,x),;(,x) nnˆx,C,x,,若是的一个非空闭的凸子集，对任何一个，都有且只有的使得 C ˆ,,x,x,minx,y:y,C, nˆx,(x)称是在集合上的投影，记作。因此，投影算子,:,,C对于每一个xCCC nx,,是有定义的，且是非扩张的。 1kmk，1k，1k，1算法:选取原始问题的初始点，则第步迭代点通过x,,,u,,x,u，下式计算: 10 - - 济南大学毕业论文 21,,k，1kk，1k,x,argminy,x，F(x,y,u)|y,,,,,2 ,, k，1kk，1u,,(u，,g(x))， *nnnm收敛性定理:设问题(2.1)解集是非空的，是单调的映射，,f:,,,g:,,, n,0,,是凸且可微的映射。为欧式空间的非空的闭凸子集及。则按照增广拉格朗, k日方法解得的序列的聚点就是变分不等式问题(2.1)的解。 ,,x 3. 增广拉格朗日乘子法的应用 3.1 供水系统调度的增广拉格朗日函数优化方法 城市供水系统的优化调整的优化问题是一个大规模，非线性。基于对库恩—塔克 [5]的最优性必要条件，所提出的解决该问题的方法要求其数学模型具有凸结构，也即 [6]就是要求将数学模型中的目标函数构造成凸函数。以增广拉格朗日函数法为基础，对于城市供水系统的具体特点，用二级递阶结构，找出解决该优化调度问题的一种新的算法。 3.1.1 供水系统优化调度问题的数学模型 城市供水系统是由给水泵站与供水管道按特定的配置式样结合而成的，供水泵站 [5]将水源中的水经过供水管道输送到用户。具有n个节点的供水管网的运行情况可以 n,1用一下个节点方程描述。 1/2u,,,Ssgn(p,p)p,p,0,i,1,？,n,1 (3.1) ,iiijijij,iIi I式中 与节点相邻的节点标号集合; i u 供水泵站所在的第个节点的供水流量; ii , 第i个节点的需水量(负荷); i p 第i个节点的压力; i 1,当a,0,sgn(a), 符号函数。定义为: sgn,,1,当a,0;, 11 - - 济南大学毕业论文 摩阻系数，常数; Sij 常数。 , 对于城市供水系统的优化调度问题，一般以总供水成本作为目标函数。它包含两 个部分:一部分是进入供水泵站内的水成本;另一部分是供水泵站内的电能消耗费用 [7]。其数学表达式为 (3.2) f(u,p),,,vu，ru(p,ph)iiiiii,i,X 式中 供水泵站所在节点标号的集合; X 进入第个供水泵站水成本的价格; vii r 单位转换系数，常数; i ph 第个供水泵站的地面标高。 ii 供水系统的调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 除了必须满足(3.1)中的n-1个方程外，还必须满足下列不等 式约束。首先必须保证系统的服务质量。也即 min (3.3) p,p,i,1,？,nii min为根据系统服务程度要求确定的第个节点的压力下限值。其次，各供水泵站的pii 供水量必须满足下式 minmax (3.4) u,u,u,i,Xiii maxminuu这里，及为第个给水泵站供水流量的上限，还有下限。 iii (3.1)-(3.4)就建成了地方给水系统调度情况的数学模型。这样，该优化调度问题 ，，,i,1,？n就是在系统的负荷都已知的条件下，确定满足方程(3.1)及不等式(3.3)、(3.4)i ，，，，ui,Xpi,1,？,n的各供水泵站的供水流量及节点压力，使式(3.2)的值为最小。ii 为了便于说明所提出的优化算法，令 1/2g(p,u,,),u,,,Ssgn(p,p)p,p ,iiiijijiji,Ii 则这个优化调度问题的数学模型能够表示为 minf(p,u) ,g(p,u,),0 minp,p,0 (3.5) minu,u,0 maxu,u,0 12 - - 济南大学毕业论文 3.1.2 供水系统优化调度问题的增广拉格朗日函数算法 城市给水系统优化调度问题(3.5)是一个复杂的非线性优化问题。这里，以增广拉格朗日函数法为基础，利用城市供水系统的具体特点，提出了解决该问题的一种新的 [8]算法。 对于一般的城市供水系统，在问题(3.5)最优解的轨迹上，必存在且仅存在一个节 min点使得而对另外的节点都有 p,p,0,kkk min p,p,i,k;i,1,？,nii 称第个节点为控制点。关于供水系统的该特点，不失一般性，然后假定节点为控nk min制点，即。该优化问题基于增广拉格朗日乘子法的函数为 p,p 2n,n,11c ,,F(p,u,,,c),f(p,u)，,g(p,u,,)，g(p,u,,),,iii2i,i,11 由增广拉格朗日函数基本原理，通过调整交替的值，再求解无约束优化问题，c,, 最后则可求出供水系统优化调度问题的解。 3.2 图像复原的增广拉格朗日函数优化方法 3.2.1图像复原模型的成立 图像的还原，为的就是根据退化的图像，重新构建质量较好的一开始的图像，其 [9]中，还原的程度以及速度情况，一直以来都是图像办理范畴中考虑的要紧目标。按照它的图像边缘保持特殊的性质，在图像复原里面中，全变分最小化模型具有明显的 [10][12]优先选择权。可能存在的局限性，在帧丢失现象中非合作和传输目标图像传感装置，难以满足后续加工及应用。 在图像的传输和采集的过程中，我们有必要思考许多有可能图像质量退化的因素，例如外界因素，环境的动态性和复杂性、图像本身方面，可能存在的局限性，在 [12]帧丢失现象中非合作和传输目标图像传感装置，难以满足后续加工及应用。 考虑到图像的退化正常情况下是不能倒过来的，实现图像的高质量还原有必要结合图像的先验模型。 图像的退化模型可以定义成: y,Ax，n (3.6) [13]n其中，是退化图像，是噪声(这种噪声一般情况下都是高斯白噪声或椒盐噪声，y x只想到高斯白噪声)，是线性退化算子(一般可以写成卷积形式)，是待复原的原A 始图像。 13 - - 济南大学毕业论文 图像的还原是由退化图像和算子来让一开始图像的高程度还原。图像的还原模xyA 型往往具备信度项和正则化项: 2 (3.7) minf(x),,,(x)，Ax,yFx [14],,0其中，是正则项，为正则化参数。全变分模型抑制图像噪声，所以被广,(x) 泛用于图像的复原。 给定的二维灰度图像，它的离散全变分模型能够定义成: xm，n TV(x),(Dx,Dx)hv 按照所使用的矩阵的范数，能够更加强的区别各项同性和各向异性全变分 TV TV(x),(Dx,Dx)isohviT mn 22,(Dx)，(Dx),,hijvij,,ij,,11 TVx,DxDx()(,)anisohvaT ,Dx，Dxhvll11 DD此中，和前一个指的是水平方向上，后一个指的是竖直方向上的梯度算子，矩hv l阵范数则是把悉数元素的绝对值加起来。 1 全变分图像复原模型为: 12fxTVxAxy,，,, argmin()() (3.8) Fx2 关于图像恢复的问题，各向同性通常可以得到更好的恢复效果。因此，我们TV 认为图像的各向同性的总变异的恢复模型的算法。 3.2.2 图像复原问题的增广拉格朗日函数算法 ux 用辅助变量代换里面的，(3.8)式等效变成解一下等式约束优化问题: TV 12argminTV(u)，Ax,y,F2 xu (3.9) , s.t.u,x 将各向同性代入(3.8)式，可以得到: TV 12fxDxDxAxy,，,,argmin(), (3.10) ，，hvFiTx2 uv把辅助变量和加入，(3.10)式就能变成下面的等式约束优化题目: 14 - - 济南大学毕业论文 12，，,argminu,v，Ax,yF2 (3.11) 2uvx,, s.t.u,Dx,v,Dxhv 通过以上各式的转化，原始的全变分图像复原问题，便转化成了等价的等式约束优化问题，进一步地便可以利用增广拉格朗日算法对以上等式约束问题进行高效的求解。 (3.9)式对应的增广拉格朗日函数为: 1,22T(,,,)()()Lxu,TVu，Ax,y，u,x，Ax,y (3.12) ,,,,FF22 ,,0其中，为拉格朗日乘子，为惩罚参数。 , 增广拉格朗日方法具有无条件收敛等优点，使得它在图像复原问题中具有独TV 到的优势。 目标函数(3.12)通过简单的变换，可以得到改良的增广拉格朗日目标函数形式: 1,22(,,,)()Lxup,TVu，Ax,y，u,x，p (3.13) ,,FF22 为了使求解的时候可以简便些，我们利用非精确的增广拉格朗日方法，使用交替 xu更新和的策略对问题进行求解。方法如下: H,1H (3.14) x,(AA，,)(Ay，,(u，p))k，1kkkk 12u,argmin,/,TV(u)，u,(x,p) (3.15) k，ukisok，k11F2 p,p，u,x k，1kk，1k，1 ,,p, k，1k HA其中，表示矩阵的共轭转置，。假若是卷积算子，可以利用快速傅1,,,2AA H里叶变换，也可以利用离散余弦变换来计算和。方程(3.15)事实上是一个各向AyAx ,,,同性图像去噪声问题。理论 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 表明，当时，可以验证收敛性以及解的TV,max 最优性。 ,,1 如果取，可以得到交替方向乘子法。许多的以增广拉格朗日为基础的图TV [15]像还原算法都使用交替方向乘子法求解。 除此之外，增广拉格朗日也可以广泛应用于压缩感知、基于字典的图像复原问题、矩阵填充问题、鲁棒主成分分析问题等。 15 - - 济南大学毕业论文 结 论 增广拉格朗日乘子法作为一种解决含有约束条件的然后求最好的解的方法，用于工程、国防、经济、金融和社会科学等很多方面。因此，探讨增广拉格朗日乘子法有很大意义。通过说明增广拉格朗日乘子法的产生和发展，从而实现增广拉格朗日乘子法更好的应用。其中增广拉格朗日乘子法作为对罚函数外点法和拉格朗日乘子法的结合，求解精度较高，是一种非常切实可行的设计优化方法。本文通过实际应用的例子说明了增广拉格朗日惩罚在应用过程中，首先对实际问题建立数学模型，再使用本方法可以加快找到最优结果的速度，也使最优结果更精确。 总结目前的增广拉格朗日乘子法的应用，在实际应用时，建立模型后计算较为复杂，因此和计算机结合，编写相应算法会更好。 16 - - 济南大学毕业论文 参 考 文 献 [1] 施光燕,钱伟懿,庞丽萍. 最优化方法[M]. 北京:高等教育出版社,2004. [2] 王莉, 单锋, 王诗云. 具有约束条件的变分不等式的可行的增广拉格朗日方法[J].生物科学学 报,2011,26(2)351-362 [3] Friedman A. Variational principle and free-boundary problems[M]. New York: John wiley, 1982, 1-56 [4] Facchinei, Pang Jongshi. Finite-Dimensional variational inequalities and complementarity problems[M]. NewYork: Springer-Verlag,2003,1-406. [5] 李光泉, 郑丕谔, 仲伟俊. 城市供水管网系统的优化调度. 系统工程学报. 1987.(1):59-66 [6] 仲伟俊, 陈森发, 徐南荣. 供水系统调度的增广拉格朗日函数优化方法南京工学院学报 1989(2):13-19 [7] 仲伟俊，陈森发，徐南荣.城市供水系统调度的递阶优化方法。南京工学院学报1987(4):65-72 [8] Bertskas d p. Multiplier Methods: A Survey.Automatica,1976;12(2):133-145 [9] 赵晓飞，张宏志，左旺孟，张大鹏.面向全变分图像复原的增广拉格朗日方法综述哈工大学报 2012(3):44-47 [10] Acar r,Vogel c r, Analysis of total variation penalty methods [J]. Inverse Problems, 1994, 10(6):1217-1229. [11] Zhang x, Burger m,Bresson x, et al. Bregmanized nonlocal regularization for deconvolution and sparse reconstruction[R].UCLA CAM Report,2009 [12] Bertsekas D P. Nonlinear programming[M].2nd edition. Athena scientific,1999 [13] Esser E. Application of Lagrangian-based alternating direction methods and connection to split bregman [R].CAM Report ,2009:9-31 [14] Wu c, Zhang j, Tai x c Augmented Lagrangian method for total variation restoraion with non-quadratic fidelty[R].CAM Report,2009:9-82 [15] Chambolle a. An algorithm for total variation minimization and application [J].Mathematical Imaging and Vision , 2004, 20(1):89-97. 17 - - 济南大学毕业论文 致 谢 在论文完成之际,首先要特别感谢我的毕业论文指导老师—邢顺来老师.在我撰写论文的过程当中,邢老师倾注了很多的心血和汗水,帮我搜集了大量的材料,帮我解决写作中的实际困难,不管在论文的选题、构想和资料的采集方面,还是在论文的研究方法以及成文定稿方面,从开始选题到中期修正,再到最终定稿,我都得到了邢老师悉心细致的教诲和无私的帮助.在论文初稿完成时,邢老师细致的修改我的论文,并给出宝贵的修改意见,为论文的顺利完成奠定基础,在此表示衷心的感谢.邢老师渊博的专业知识,周详的治学态度,精益求精的工作作风,对我感化深远,使我建设了远大的学术目标、掌握了基本的研究方法. 我真诚地感谢大学四年来数学科学学院各位老师对我的关怀和教导，感谢大学期间所有任课老师、学办老师和学院领导，感谢你们的精心教导和关怀，四年之中，不仅给予了我丰厚的知识，也使得我学到了更多社会阅历，培养了正确的思维方式，增强了表达能力，开阔了视野，对于今后的生活受益匪浅.是你们传授给我专业课知识及其他知识，使我打下了坚实的数学基础和计算机基础，是你们教会我做人的道理，也是你们教给了我如何发展自己，如何适应社会需求，让我在以后的人生道路上充满信心。 在论文的写作过程中,也得到了许多同学的宝贵建议,他们在我论文写作遇到困难之时伸出援助之手,帮我分析问题,查阅资料。感谢我的室友及其他好友,因为有他们的帮助,我的论文得以顺利完成。 在以后的学习中,我会更加努力来答谢关心、帮助和支持过我的所有领导、老师、同学、和朋友。真诚的祝福所有的老师工作顺利,身心愉快,祝愿济南大学数学科学学院人才辈出,济南大学拥有更加辉煌灿烂的明天.再一次对所有帮助过我的老师和同学表示衷心的感谢～ 18 - -