增广拉格朗日乘子法及其在约束优化问题的应用.doc
《增广拉格朗日乘子法及其在约束优化问题的应用.doc》由会员分享,可在线阅读,更多相关《增广拉格朗日乘子法及其在约束优化问题的应用.doc(26页珍藏版)》请在咨信网上搜索。
1、毕业论文题 目 增广拉格朗日乘数法及在 其在约束优化问题的应用 学 院 数学科学学院 专 业 信息与计算科学 班 级 计算1001班 学 生 高亚茹 学 号 20100921032 指导教师 邢顺来 二一四年 五 月二十五日摘 要 增广拉格朗日乘子法作为求解约束优化问题的一种重要方法,近年来研究增广拉格朗日乘子法的应用显得更加重要。本文首要介绍了增广拉格朗日乘子法的产生,通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合,引出了现在对增广拉格朗日法的发展状况,概述了增广拉格朗日乘子法基本理论。然后具体说明了增广拉格朗日法在科学领域上的实际应用,如在供水系统和图像复原的应用,也证明了
2、增广拉格朗日乘子法的实际应用性。关键词:增广拉格朗日乘子法;罚函数法;供水系统;图像复原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 prim
3、ary 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 lag
4、rangian 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 Multip
5、lier Methods;Penalty FunctionMethods Water Supply Systems ;Image Restorations目 录摘要. .IABSTRACT.II1前言.11.1增广拉格朗日函数法的产生与应用.11.2研究增广拉格朗日函数法应用的意义.12增广拉格朗日乘子法.32.1约束非线性规划.32.2罚函数外点法.42.3拉格朗日乘子法 .62.4增广拉格朗日乘子法 .72.4增广拉格朗日乘子法的计算 . 103 增广拉格朗日乘子法的应用. 123.1供水系统调度的增广拉格朗日函数优化方法. . 123.2图像复原的增广拉格朗日函数优化方法.14结论.17
6、参考文献.18致谢.191 前言1.1 增广拉格朗日函数法的产生与应用在求解有约束条件的优化题目时,有一个重要方法,便是用适合的方法把约束优化问题,转变成无约束优化问题来进行求解。在求最佳的解的题目中,以美国知名学者约瑟夫起名的拉格朗日乘数法是一种探索三元以上函数的极值的方法,其中有若干个条件制约着这类函数的变量。它的主要解决方式就是,把一个具备个变量与个约束条件的求最佳解的问题,转换为一个具备个变量的方程组的极值问题,这里面的变量有一个特点,没有任何制约,就称为无约束变量。这种方法引入了一种没有过的的标量未知数,也就是拉格朗日函数参数1。罚函数方法是将具备约束条件然后求最好的解的问题变成为不
7、具备制约条件的一种重要的方式,它们首先求解一个,也有可能是一系列的罚问题来得到最末的限制最好的解的问题的解。这样我们可以把罚问题中的目标函数称为一个罚函数。从这里看,增广拉格朗日函数法,我们还有另一种叫法便是使用增广拉格朗日函数来当成罚函数的不间断的可微准确罚函数法,跟序列罚函数法比一下,不可微准确罚函数法具备明显的长处。增广拉格朗日乘子法,是在拉格朗日乘子法的基础上,联合了罚函数外点法,把它们综合在一块的方法,它的本质上最根本的思想就是在之前的罚函数中,考虑引入拉格朗日乘子,这样做就有了增广拉格朗日函数。在寻找最优解的过程中,通过一直连续不断的改变拉格朗日乘子和惩罚因子来求解各异的拉格朗日函
8、数,换句话说也就是使用无约束最小优化方法得到此拉格朗日函数的极小值点,再加上有这样的拉格朗日函数极值点就会不断的向一开始的目标函数的约束最好的点靠拢,根据收敛准则能够得到差不多近似的最优解1。 增广拉格朗日乘子法,从本质上讲就是对拉格朗日乘子方法的延伸,要不就称为是一种序列没有制约的最小化技术。它的最初的想法是对执行可行性的限制标准给予了一个惩罚,在迭代自适应切换惩罚因子可以是拉格朗日乘子,解决了一系列的最小化问题后,以求目的可以逼近原问题的最优解,这样就逃避了单一使用拉格朗日乘子法或单一使用罚函数外点法有可能会出现的不好的地方。 在实际遇到的问题中,增广拉格朗日乘子法被当成求解约束优化问题的
9、一种重要方法,近年来的应用遍及工程、国防、经济、金融和社会科学等很多紧要的科学领域1。比方说,基于拉格朗日乘子法的水平井射孔优化设计问题,就是首先一开始采用了增广拉格朗日乘子法,然后结合油藏渗流模型,在考虑水平井井底流压或者定产量情况下,以获得最大产量还有最小井底流压为研究需求,对数不清的导流来对水平井射孔密度遍布情况来优化。增广拉格朗日乘子法的应用涉及很多的方面,因此,对增广拉格朗日乘子法的应用的研究具有很大的意义。1.2 研究增广拉格朗日函数法应用的意义 关于增广拉格朗日乘子法的研究是一个重要的研究课题,其在很多领域具有广阔的应用前景。 首先,近些年来,随着计算机的快速发展,增广拉格朗日乘
10、子法对于求解变分不等式问题在构造数值算法时能起到很重要的作用。另外,增广拉格朗日乘子法可以用于许多实际问题中的优化设计,通过编写程序构造乘子函数,求解精度较高,是一种非常切实可行的设计优化方法。使用增广拉格朗日乘子法去解决别的实际问题中的变化的分量不等式问题,是值得我们继续研究的课题。2. 增广拉格朗日乘子法2.1 约束非线性规划 解决平常的不是线性的规划问题,比无约束问题和线性规划问题都要麻烦不简单的多。用一个简单的例子来说明这点,考虑问题2 这个问题的可行域是一个三角形,以及它的内部区域,的等值线则是以原点为圆心的同心圆。问题的最优解为,最优值为。 线性规划的最优解总是能够在可行域的顶点中
11、找到,而顶点的数量是有限的,这就是单纯形法的基本出发点。而上面的例子说明:对于非线性规划问题,即使约束都是线性的,最优解也不一定在顶点。这就给求解它们带来了困难。另一方面,由于约束的存在,如果不存在约束,从任一个初始点出发,沿的负梯度方向进行一维搜索,便求得目标函数的无约束极小点。但是,有了约束,在进行一维搜索时,为了使求得的点是一个可行点,就必须对步长加以限制,这样,我们最远只能跑到边界上的一个点,当所取不在直线上时,点就不会是最优解。因此,继续迭代下去寻求一个没见过的可行点是有必要的,使目标函数有更小的值。可是,沿在处的负梯度方向已经找不到可行点,所以梯度迭代已不能继续进行,尽管离最优解还
12、可能很远。这正是约束非线性规划与无约束非线性规划的本质区别,也是求解约束问题的根本问题所在。为了克服这样的困难,也就是换另一句话说,当现有已经存在的点在区域的边缘上时,为了使迭代能不断的继续进行下去,不仅有需求搜索方向拥有使目标函数下降的可能性,还有要求在这个方向上有可行点。例如,有一个小线段整个包含在可行域内,像这样的方向称为可行方向。所以,在求解约束非线性规划迭代法的设计中,主要应在每个迭代点处构造出一个下降可行方向。 解决约束非线性规划的另外一个途径是:在某个近似解处,以已有较好解法的较为简单的问题近似代替原问题用其最优解作为原来问题的新的近似解。例如将目标函数及约束条件中的非线性函数分
13、别以他们的一阶泰勒多项式或二阶泰勒多项式近似替代,或以一无约束非线性规划近似代替等。2.2 罚函数外点法 根据现在已存在的制约特征情况,约束有两类情况,一种情况是等式,另一种情况是不等式,构建一种有可能的惩罚项,继而把它加到目标函数中去,让约束问题的求解,变换成为无约束问题的求解,这类惩罚的方式,在没有约束题目求解的过程当中,和其相关的那些小概率违反约束的迭代点,给它很大的目的数值,强制性的使这些没有约束问题的极小点,一直向可行的区域凑近,也可以不停坚持不断的在可行域内移动,终止到收敛于原来的约束问题的极小点2。 罚函数方法中有一类情况是在可行性区域外进行的惩罚函数法,也能够叫为外点法,它对不
14、遵守约束的迭代点在目标函数中加入符合的惩罚,但是针对可行点就不给予惩罚。这种方法的迭代点往往是在可行域的外部移动。 考虑一般约束最优化问题 (2.1)定义辅助函数 其中可取如下形式其中均为常数,通常取。这样,转化为无约束问题 其中是很大的正数2。一般来讲我们将称为惩罚项,则被叫为惩罚因子,被叫成惩罚函数。例 2.1.1 求解非线性规划 定义惩罚函数用解析法求解,有令得到易见,当时。恰巧就是所求非线性规划的最优解2。 用像这样的方法得到的没有约束问题的最优解,在平时普通的情况下是不会满足约束条件的,它是在可行域外部,当的增大的时候,然后不断接近,所以称这种方法为外点法。 在实际计算的过程中,考虑
15、怎样选择惩罚因子是非常有必要的。平时遇到这种情形时,我们的方式是取一个不断接近无穷大和严格递增的正数列,一个一个的求解如此得到一个极小点的序列,在合适的条件下,最佳的顺序收敛域约束的解决方案。像如此行使一系列无约束题目,来取得限制问题最优解的方式,我们把它称叫为序列没有约束极小化方法,简称为方法。外点法的具体步骤为2:1. 一开始给定初始点,初始化罚因子,把系数放大,可以接受的误差,;2. 以为初始点,解无约束问题 ,设其极小点为;3. 若,则停,得近似解;否则,令回2。2.3 拉格朗日乘子法 若都是可微的,对于问题(2.1),能够成立拉格朗日函数Kuhn-Tucher条件3: 对于非线性规划
16、(2.1),若都是可微的,且互为线性无关,则为(2.1)最优解的必要条件为:都有相对应的拉格朗日乘子和使其中称为的有效约束指标集。 把满足K-T条件的可行点成为K-T点,最优点必定是K-T点。例2.2.1 解非线性规划,并且求它的K-T点 解 非线性规划的K-T条件在这里为 (2.2) (2.3) (2.4) (2.5)再加上约束条件 (2.6) (2.7)(1) 若(2.6)式等号不成立,则由(2.3)式有,再代入(2.2)式得,这和(2.4)矛盾。因此(2.6)式等号必成立。(2) 若(2.7)式等号不成立,则由(2.4)式有,代入(2.2)式得 (2.8)由和(2.8)中第一式,得。再代
17、入(2.6)式(等号成立)中和联系(2.8)中第二式,得。(3) 若(2.7)式等号成立,则有(2.6)、(2.7)两个等式解得两个点及。注意到(2.5)式,由(2.2)式中第一行等式,知不能取,而若取,则就应取,这使(2.2)中第二行等式不能成立。所以,对于所求的非线性规划,存在唯一的K-T点。2.4 增广拉格朗日乘子法 增广拉格朗日乘子法,是在拉格朗日乘子法的基础上,联系了罚函数外点法的一种方式,它的基本思想就是把拉格朗日乘子放入惩罚函数中去,来建立增广拉格朗日函数,在过程中的最优解的搜索,通过不断的惩罚因子和拉格朗日通过调整乘法器,为了能够得到拉格朗日的作用是不同的,通过求解无约束最小优
18、化来的最低点拉格朗日函数,和拉格朗日函数的极值点附近的原始目标函数的限制最优点的基础上,得到一个接近最优解的收敛标准4。考虑问题(2.1),可构造增广拉格朗日函数1. 考虑只存在等式约束的非线性优化问题 (2.9)则优化问题的拉格朗日函数为 (2.10)其中,是一正的罚系数。 增广拉格朗日函数法的基本思想就是通过求解给予及值下的没有约束最佳问题(2.10)和调整及的值的轮换进行,逐步接近优化问题(2.9)的解。所以将有约束优化问题的求解可以变为无约束优化问题的求解。这样,这个方法一方面具有了拉格朗日函数法还有罚函数法所具有的优点,另一方面较好的克服了它们所存在的不好的地方,叫成一种更有用的解决
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 增广 拉格朗日乘子法 及其 约束 优化 问题 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。