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

毕毕 业业 论论 文文 题题 目目 增广拉格朗日乘数法及在 其在约束优化问题的应用 学学 院院 数学科学学院 专专 业业 信息与计算科学 班班 级级 计算 1001 班 学学 生生 高亚茹 学学 号号 20100921032 指导教师指导教师 邢顺来 二 一四年 五 月二十五日 济南大学毕业论文 I 摘 要 增广拉格朗日乘子法作为求解约束优化问题的一种重要方法 近年来研究增广 拉格朗日乘子法的应用显得更加重要 本文首要介绍了增广拉格朗日乘子法的产生 通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合 引出了现 在对增广拉格朗日法的发展状况 概述了增广拉格朗日乘子法基本理论 然后具体 说明了增广拉格朗日法在科学领域上的实际应用 如在供水系统和图像复原的应用 也证明了增广拉格朗日乘子法的实际应用性 关键词 增广拉格朗日乘子法 罚函数法 供水系统 图像复原 济南大学毕业论文 II 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 济南大学毕业论文 III 目 录 摘要 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 济南大学毕业论文 1 1 前言 1 1 增广拉格朗日函数法的产生与应用 在求解有约束条件的优化题目时 有一个重要方法 便是用适合的方法把约束 优化问题 转变成无约束优化问题来进行求解 在求最佳的解的题目中 以美国知 名学者约瑟夫起名的拉格朗日乘数法是一种探索三元以上函数的极值的方法 其中 有若干个条件制约着这类函数的变量 它的主要解决方式就是 把一个具备个变n 量与个约束条件的求最佳解的问题 转换为一个具备个变量的方程组的极值kkn 问题 这里面的变量有一个特点 没有任何制约 就称为无约束变量 这种方法引 入了一种没有过的的标量未知数 也就是拉格朗日函数参数 1 罚函数方法是将具备约束条件然后求最好的解的问题变成为不具备制约条件的 一种重要的方式 它们首先求解一个 也有可能是一系列的罚问题来得到最末的限 制最好的解的问题的解 这样我们可以把罚问题中的目标函数称为一个罚函数 从 这里看 增广拉格朗日函数法 我们还有另一种叫法便是使用增广拉格朗日函数来 当成罚函数的不间断的可微准确罚函数法 跟序列罚函数法比一下 不可微准确罚 函数法具备明显的长处 增广拉格朗日乘子法 是在拉格朗日乘子法的基础上 联合了罚函数外点法 把它们综合在一块的方法 它的本质上最根本的思想就是在之前的罚函数中 考虑 引入拉格朗日乘子 这样做就有了增广拉格朗日函数 在寻找最优解的过程中 通 过一直连续不断的改变拉格朗日乘子和惩罚因子来求解各异的拉格朗日函数 换句 话说也就是使用无约束最小优化方法得到此拉格朗日函数的极小值点 再加上有这 样的拉格朗日函数极值点就会不断的向一开始的目标函数的约束最好的点靠拢 根 据收敛准则能够得到差不多近似的最优解 1 增广拉格朗日乘子法 从本质上讲就是对拉格朗日乘子方法的延伸 要不就称 为是一种序列没有制约的最小化技术 它的最初的想法是对执行可行性的限制标准 给予了一个惩罚 在迭代自适应切换惩罚因子可以是拉格朗日乘子 解决了一系列 的最小化问题后 以求目的可以逼近原问题的最优解 这样就逃避了单一使用拉格 朗日乘子法或单一使用罚函数外点法有可能会出现的不好的地方 在实际遇到的问题中 增广拉格朗日乘子法被当成求解约束优化问题的一种重 要方法 近年来的应用遍及工程 国防 经济 金融和社会科学等很多紧要的科学 领域 1 比方说 基于拉格朗日乘子法的水平井射孔优化设计问题 就是首先一开 始采用了增广拉格朗日乘子法 然后结合油藏渗流模型 在考虑水平井井底流压或 者定产量情况下 以获得最大产量还有最小井底流压为研究需求 对数不清的导流 来对水平井射孔密度遍布情况来优化 增广拉格朗日乘子法的应用涉及很多的方面 济南大学毕业论文 2 因此 对增广拉格朗日乘子法的应用的研究具有很大的意义 1 2 研究增广拉格朗日函数法应用的意义 关于增广拉格朗日乘子法的研究是一个重要的研究课题 其在很多领域具有广 阔的应用前景 首先 近些年来 随着计算机的快速发展 增广拉格朗日乘子法对于求解变分 不等式问题在构造数值算法时能起到很重要的作用 另外 增广拉格朗日乘子法可 以用于许多实际问题中的优化设计 通过编写程序构造乘子函数 求解精度较高 是一种非常切实可行的设计优化方法 使用增广拉格朗日乘子法去解决别的实际问 题中的变化的分量不等式问题 是值得我们继续研究的课题 济南大学毕业论文 3 2 增广拉格朗日乘子法 2 1 约束非线性规划 解决平常的不是线性的规划问题 比无约束问题和线性规划问题都要麻烦不简 单的多 用一个简单的例子来说明这点 考虑问题 2 01 01 01 min 2 1 21 2 2 2 1 x x xxts xxxf 这个问题的可行域是一个三角形 以及它的内部区域 的等值线则是以原 xf 点为圆心的同心圆 问题的最优解为 最优值为 T x 2 1 2 1 2 1 xf 线性规划的最优解总是能够在可行域的顶点中找到 而顶点的数量是有限的 这就是单纯形法的基本出发点 而上面的例子说明 对于非线性规划问题 即使约 束都是线性的 最优解也不一定在顶点 这就给求解它们带来了困难 另一方面 由于约束的存在 如果不存在约束 从任一个初始点出发 沿的负梯度方 0 x xf 向进行一维搜索 便求得目标函数的无约束极小点 但是 有了约束 在进行 T 0 0 一维搜索时 为了使求得的点是一个可行点 就必须对步长加以限制 这样 我们 最远只能跑到边界上的一个点 当所取不在直线上时 点就不会是 0 x0 21 xx 1 x 最优解 因此 继续迭代下去寻求一个没见过的可行点是有必要的 使目标函数 x 有更小的值 可是 沿在处的负梯度方向已经找不到可行点 所以梯度迭 xf 1 x 代已不能继续进行 尽管离最优解还可能很远 这正是约束非线性规划与无约束非 线性规划的本质区别 也是求解约束问题的根本问题所在 为了克服这样的困难 也就是换另一句话说 当现有已经存在的点在区域的边缘上时 为了使迭代能不断 的继续进行下去 不仅有需求搜索方向拥有使目标函数下降的可能性 还有要求在 这个方向上有可行点 例如 有一个小线段整个包含在可行域内 像这样的方向称 为可行方向 所以 在求解约束非线性规划迭代法的设计中 主要应在每个迭代点 处构造出一个下降可行方向 k x k d 解决约束非线性规划的另外一个途径是 在某个近似解处 以已有较好解法的 较为简单的问题近似代替原问题用其最优解作为原来问题的新的近似解 例如将目 济南大学毕业论文 4 标函数及约束条件中的非线性函数分别以他们的一阶泰勒多项式或二阶泰勒多项式 近似替代 或以一无约束非线性规划近似代替等 2 2 罚函数外点法 根据现在已存在的制约特征情况 约束有两类情况 一种情况是等式 另一种 情况是不等式 构建一种有可能的惩罚项 继而把它加到目标函数中去 让约束问 题的求解 变换成为无约束问题的求解 这类惩罚的方式 在没有约束题目求解的 过程当中 和其相关的那些小概率违反约束的迭代点 给它很大的目的数值 强制 性的使这些没有约束问题的极小点 一直向可行的区域凑近 也可以不停坚持不断 的在可行域内移动 终止到收敛于原来的约束问题的极小点 2 罚函数方法中有一类情况是在可行性区域外进行的惩罚函数法 也能够叫为外 点法 它对不遵守约束的迭代点在目标函数中加入符合的惩罚 但是针对可行点就 不给予惩罚 这种方法的迭代点往往是在可行域的外部移动 考虑一般约束最优化问题 2 1 1 0 1 0 min ljxh mixgts xf j i 定义辅助函数 xPxfxF 其中可取如下形式 xP m i l j ji xhxgxP 11 0max 其中均为常数 通常取 1 2 这样 转化为无约束问题 minxPxfxF def 其中是很大的正数 2 一般来讲我们将称为惩罚项 则被叫为惩罚因子 被叫成惩罚函数 xP xF 例 2 1 1 求解非线性规划 1 1 min 2 2 2 2 1 xxgts xxxf def 定义惩罚函数 济南大学毕业论文 5 1 1 1 1 1 1 0max 1 2 2 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 1 xxxx xxx xxxxF 当 当 用解析法求解 有 min xF 1 1 22 12 1 2 222 2 2 2 1 1 xxx xx x F x x F 当 当 令 0 0 21 x F x F 得到 1 1 2 1 x x x 易见 当时 1 1 xx 恰巧就是所求非线性规划的最优解 2 x 用像这样的方法得到的没有约束问题的最优解 在平时普通的情况下是不会满 足约束条件的 它是在可行域外部 当的增大的时候 然后不断接近 所以称 x 这种方法为外点法 在实际计算的过程中 考虑怎样选择惩罚因子是非常有必要的 平时遇到这 种情形时 我们的方式是取一个不断接近无穷大和严格递增的正数列 一个一 k 个的求解 minxPxf k 如此得到一个极小点的序列 在合适的条件下 最佳的顺序收敛域约束的解决 k x 方案 像如此行使一系列无约束题目 来取得限制问题最优解的方式 我们把它称 叫为序列没有约束极小化方法 简称为方法 SUMT 外点法的具体步骤为 2 1 一开始给定初始点 初始化罚因子 把系数放大 可以接受的误差 0 x 1 1 c 0 1 k 2 以为初始点 解无约束问题 1 k x 济南大学毕业论文 6 min k f xP x 设其极小点为 k x 3 若 则停 得近似解 否则 令回 2 k k xP k x 1 1 kkc kk 2 3 拉格朗日乘子法 若都是可微的 对于问题 2 1 能够成立拉格朗日函数 ji hgf 11 l j jj m i ii xhxgxfxL Kuhn Tucher 条件 3 对于非线性规划 2 1 若都是可微的 且 ji hgf 互为线性无关 则为 2 1 最优解的必要条件为 ljxhxIixg ji 1 x 都有相对应的拉格朗日乘子和使 0 1 1 l j jj m i i i x xhxgxfxL 2 1 0 2 1 0 mi mixg i ii 其中称为的有效约束指标集 0 xgixI i x 把满足 K T 条件的可行点成为 K T 点 最优点必定是 K T 点 例 2 2 1 解非线性规划 并且求它的 K T 点 0 1 09 min 212 2 2 2 11 2 2 1 xxxg xxxgts xxxf 解 非线性规划的 K T 条件在这里为 2 2 0 1 1 2 2 1 2 2 2 1 1 1 x xx 2 3 0 9 2 2 2 11 xx 2 4 0 1 212 xx 2 5 0 0 21 济南大学毕业论文 7 再加上约束条件 2 6 09 2 2 2 1 xx 2 7 01 21 xx 1 若 2 6 式等号不成立 则由 2 3 式有 再代入 2 2 式得 这和0 1 1 2 2 4 矛盾 因此 2 6 式等号必成立 2 若 2 7 式等号不成立 则由 2 4 式有 代入 2 2 式得0 2 2 8 021 0 1 2111 xx 由和 2 8 中第一式 得 再代入 2 6 式 等号成立 中和联系 2 8 中第0 1 0 1 x 二式 得 3 6 1 21 x 3 若 2 7 式等号成立 则有 2 6 2 7 两个等式解得两个点 及 T x 2 171 2 171 T 2 171 2 171 注意到 2 5 式 由 2 2 式中第一行等式 知不能取 而若取 则 1 x 2 171 2 17 1 就应取 这使 2 2 中第二行等式不能成立 2 x 2 171 所以 对于所求的非线性规划 存在唯一的 K T 点 2 4 增广拉格朗日乘子法 增广拉格朗日乘子法 是在拉格朗日乘子法的基础上 联系了罚函数外点法的 一种方式 它的基本思想就是把拉格朗日乘子放入惩罚函数中去 来建立增广拉格 朗日函数 在过程中的最优解的搜索 通过不断的惩罚因子和拉格朗日通过调整乘 法器 为了能够得到拉格朗日的作用是不同的 通过求解无约束最小优化来的最低 点拉格朗日函数 和拉格朗日函数的极值点附近的原始目标函数的限制最优点的基 础上 得到一个接近最优解的收敛标准 4 考虑问题 2 1 可构造增广拉格朗日函数 2 0max 2 1 1 2 11 22 l j j m i l j jjiii xhxhxgxfxF 1 考虑只存在等式约束的非线性优化问题 济南大学毕业论文 8 2 9 mixh xf i 10 min 则优化问题的拉格朗日函数为 2 10 m i m i iii xH c xhxfcxF 11 2 2 其中 是一正的罚系数 c 增广拉格朗日函数法的基本思想就是通过求解给予及 值下的没有约束最佳 c 问题 2 10 和调整及 的值的轮换进行 逐步接近优化问题 2 9 的解 所以将有约 c 束优化问题的求解可以变为无约束优化问题的求解 这样 这个方法一方面具有了 拉格朗日函数法还有罚函数法所具有的优点 另一方面较好的克服了它们所存在的 不好的地方 叫成一种更有用的解决非线性约束优化题目的方法 例 2 3 1 用乘子法求解问题 0 1 22min 21 21 2 2 2 1 xxxhts xxxx 解 2 2121 2 2 2 1 1 22 xxxxxxx 取 用解析法解 得极小点为2 1 1 2 1 minx 4 3 2 1 1 2 1 1 1 x x x 修正有 然后再解 得到 像 2 1 4 1 21 1 1 2 xh 2 min 2 1 x 2 x 这样继续 一般情况下 到了第次迭代时 的极小点为k 2 k x 2 2 4 1 6 1 2 1 k k k k k x x x 3 1 6 1 1 kk 很容易看到 在那个时候 即分别计算出的最优 k 5 2 k T k x 5 3 5 2 非线性规划 最优乘子和最优解 2 考虑不等式约束情形 先考虑只有不等式约束的问题 济南大学毕业论文 9 2 1 0 min mixgts xf i 利用等式约束的结果 引入变量 把上式化为等式约束问题 i y 2 1 0 min 2 miyxgts xf ii 这样 可定义增广拉格朗日函数 m i m i iiii yxgiyxgxfyx 11 222 2 从而把问题转化为求解 min yx 为此 将的形式改写为 m i i iii xgyxfyx 1 2 2 2 2 1 2 由的形式 可见为使取极小 的取值必定是 2 i y 0max 1 2 2 iii xgy 于是 可以上式代入消去 因此定义增广拉格朗日函数 i y m i iii xgxfx 1 2 2 0max 2 1 总结以上 不等式约束问题也就可以变为没有约束问题 min x 例 2 3 2 问题 1 6 1 2 1 min 21 2 2 2 1 xxts xx 最优解是 然后利用惩罚函数法和乘子法两种方法解决出它的迭代点 75 0 25 0 x 列 解 1 惩罚函数法 对于 1 26 1 2 1 min 2 21 2 2 2 1 xx c xxxF k ck x 济南大学毕业论文 10 可求得最优解为 41 3 41 T k k k k k c c c c x 2 乘子法 对于 1 1 26 1 2 1 min 21 2 21 2 2 2 1 xxxx c xxxL k k ck x 可求得最优解为 41 3 41 T k k k k k k k c c c c x 2 5 增广拉格朗日乘子法的计算 首先半光滑函数的定义 4 设是部分 Lipschitz 连续映射 我们把它叫为在是半光滑的 mn G G n x 当 i 在处是方向可微的 Gx ii 对任意的和且 有 n x xxGH 0 x xxHxGxxG 进一步地 称在处是强半光滑的 如果在处是半光滑的 且对任意的G n x Gx 和且 有 n x xxGH 0 x 2 xxHxGxxG 若是的一个非空闭的凸子集 对任何一个 都有且只有的使得C n n x Cx min Cyyxxx 称是在集合上的投影 记作 因此 投影算子对于每一个 x xC x C C n C 是有定义的 且是非扩张的 n x 算法 选取原始问题的初始点 则第步迭代点通过 mk ux 1 1 k 11 kk ux 下式计算 济南大学毕业论文 11 2 1 minarg 11 1 2 1 kkk kkkk xguu yuyxFxyx 收敛性定理 设问题 2 1 解集是非空的 是单调的映射 nn f 是凸且可微的映射 为欧式空间的非空的闭凸子集及 则按 mn g n 0 照增广拉格朗日方法解得的序列的聚点就是变分不等式问题 2 1 的解 k x 3 增广拉格朗日乘子法的应用 3 1 供水系统调度的增广拉格朗日函数优化方法 城市供水系统的优化调整的优化问题是一个大规模 非线性 基于对库恩 塔 克的最优性必要条件 所提出的解决该问题的方法 5 要求其数学模型具有凸结构 也即就是要求将数学模型中的目标函数构造成凸函数 6 以增广拉格朗日函数法为 基础 对于城市供水系统的具体特点 用二级递阶结构 找出解决该优化调度问题 的一种新的算法 3 1 1 供水系统优化调度问题的数学模型 城市供水系统是由给水泵站与供水管道按特定的配置式样结合而成的 供水泵 站将水源中的水经过供水管道输送到用户 5 具有个节点的供水管网的运行情况n 可以用一下个节点方程描述 1 n 3 1 1 1 0 sgn 2 1 nippppSu jiji Ii ijii i 式中 与节点相邻的节点标号集合 i I 供水泵站所在的第 个节点的供水流量 i ui 第 个节点的需水量 负荷 i i 第 个节点的压力 i pi 符号函数 定义为 sgn 0 1 0 1 sgn a a a 当 当 济南大学毕业论文 12 摩阻系数 常数 ij S 常数 对于城市供水系统的优化调度问题 一般以总供水成本作为目标函数 它包含 两个部分 一部分是进入供水泵站内的水成本 另一部分是供水泵站内的电能消耗 费用 7 其数学表达式为 3 2 Xi iiiiii phpuruvpuf 式中 供水泵站所在节点标号的集合 X 进入第 个供水泵站水成本的价格 i vi 单位转换系数 常数 i r 第 个供水泵站的地面标高 i phi 供水系统的调度方案除了必须满足 3 1 中的 n 1 个方程外 还必须满足下列不 等式约束 首先必须保证系统的服务质量 也即 3 3 nipp ii 1 min 为根据系统服务程度要求确定的第 个节点的压力下限值 其次 各供水泵站的 min i pi 供水量必须满足下式 3 4 Xiuuu iii maxmin 这里 及为第 个给水泵站供水流量的上限 还有下限 max i u min i ui 3 1 3 4 就建成了地方给水系统调度情况的数学模型 这样 该优化调度问题 就是在系统的负荷都已知的条件下 确定满足方程 3 1 及不等式 3 3 ni i 1 3 4 的各供水泵站的供水流量及节点压力 使式 3 2 的值为最 Xiui nipi 1 小 为了便于说明所提出的优化算法 令 i Ii jijiijiii ppppSuupg 2 1 sgn 则这个优化调度问题的数学模型能够表示为 济南大学毕业论文 13 3 5 0 0 0 0 min max min min uu uu pp upg upf 3 1 2 供水系统优化调度问题的增广拉格朗日函数算法 城市给水系统优化调度问题 3 5 是一个复杂的非线性优化问题 这里 以增广 拉格朗日函数法为基础 利用城市供水系统的具体特点 提出了解决该问题的一种 新的算法 8 对于一般的城市供水系统 在问题 3 5 最优解的轨迹上 必存在且仅存在一个 节点使得而对另外的节点都有k 0 min kk pp nikipp ii 1 min 称第个节点为控制点 关于供水系统的该特点 不失一般性 然后假定节点为kn 控制点 即 该优化问题基于增广拉格朗日乘子法的函数为 min pp 2 1 1 1 1 2 n i i n i ii upg c upgupfcupF 由增广拉格朗日函数基本原理 通过调整交替的值 再求解无约束优化问 c 题 最后则可求出供水系统优化调度问题的解 3 2 图像复原的增广拉格朗日函数优化方法 3 2 1 图像复原模型的成立 图像的还原 为的就是根据退化的图像 重新构建质量较好的一开始的图像 其中 还原的程度以及速度情况 一直以来都是图像办理范畴中考虑的要紧目标 9 按照它的图像边缘保持特殊的性质 在图像复原里面中 全变分最小化模型具有明 显的优先选择权 10 可能存在的局限性 在帧丢失现象 12 中非合作和传输目标图像 传感装置 难以满足后续加工及应用 在图像的传输和采集的过程中 我们有必要思考许多有可能图像质量退化的因 素 例如外界因素 环境的动态性和复杂性 图像本身方面 可能存在的局限性 在帧丢失现象 12 中非合作和传输目标图像传感装置 难以满足后续加工及应用 考虑到图像的退化正常情况下是不能倒过来的 实现图像的高质量还原有必要 结合图像的先验模型 图像的退化模型可以定义成 济南大学毕业论文 14 3 6 nAxy 其中 是退化图像 是噪声 13 这种噪声一般情况下都是高斯白噪声或椒盐噪yn 声 只想到高斯白噪声 是线性退化算子 一般可以写成卷积形式 是待复Ax 原的原始图像 图像的还原是由退化图像和算子来让一开始图像的高程度还原 图像的还原yAx 模型往往具备信度项和正则化项 3 7 2 min F x yAxxxf 其中 是正则项 为正则化参数 全变分模型抑制图像噪声 14 所以被 x 0 广泛用于图像的复原 给定的二维灰度图像 它的离散全变分模型能够定义成 nm x xDxDxTV vh 按照所使用的矩阵的范数 能够更加强的区别各项同性和各向异性全变分TV m i n j jivjih iT vhiso xDxD xDxDxTV 11 2 2 11 l v l h aT vhaniso xDxD xDxDxTV 此中 和前一个指的是水平方向上 后一个指的是竖直方向上的梯度算子 h D v D 矩阵 范数则是把悉数元素的绝对值加起来 1 l 全变分图像复原模型为 3 8 21 argmin 2 F x f xTV xAxy 关于图像恢复的问题 各向同性通常可以得到更好的恢复效果 因此 我们TV 认为图像的各向同性的总变异的恢复模型的算法 3 2 2 图像复原问题的增广拉格朗日函数算法 用辅助变量代换里面的 3 8 式等效变成解一下等式约束优化问题 uTVx 3 9 xuts yAxuTV F ux 2 1 minarg 2 将各向同性代入 3 8 式 可以得到 TV 济南大学毕业论文 15 3 10 21 argmin 2 hv F iT x f xD x D xAxy 把辅助变量和 加入 3 10 式就能变成下面的等式约束优化题目 uv 3 11 xDvxDuts yAxvu vh F xvu 2 1 minarg 2 2 通过以上各式的转化 原始的全变分图像复原问题 便转化成了等价的等式约束优 化问题 进一步地便可以利用增广拉格朗日算法对以上等式约束问题进行高效的求 解 3 9 式对应的增广拉格朗日函数为 3 12 22 2 2 1 F T F yAxxuyAxuTVuxL 其中 为拉格朗日乘子 为惩罚参数 0 增广拉格朗日方法具有无条件收敛等优点 使得它在图像复原问题中具有独TV 到的优势 目标函数 3 12 通过简单的变换 可以得到改良的增广拉格朗日目标函数形式 3 13 22 22 1 FF pxuyAxuTVpuxL 为了使求解的时候可以简便些 我们利用非精确的增广拉格朗日方法 使用交 替更新和的策略对问题进行求解 方法如下 xu 3 14 1 1kkk H k H k puyAAAx 3 15 2 11 2 1 minarg F kkisokuk pxuuTVu 111 kkkk xupp kk p 1 其中 表示矩阵的共轭转置 假若是卷积算子 可以利用快速傅 H AA21 A 里叶变换 也可以利用离散余弦变换来计算和 方程 3 15 事实上是一个各AxyAH 向同性图像去噪声问题 理论分析表明 当时 可以验证收敛性以及解TV max 的最优性 如果取 可以得到交替方向乘子法 许多的以增广拉格朗日为基础的1 图像还原算法都使用交替方向乘子法求解 15 TV 除此之外 增广拉格朗日也可以广泛应用于压缩感知 基于字典的图像复原问 题 矩阵填充问题 鲁棒主成分分析问题等 济南大学毕业论文 16 结 论 增广拉格朗日乘子法作为一种解决含有约束条件的然后求最好的解的方法 用 于工程 国防 经济 金融和社会科学等很多方面 因此 探讨增广拉格朗日乘子 法有很大意义 通过说明增广拉格朗日乘子法的产生和发展 从而实现增广拉格朗 日乘子法更好的应用 其中增广拉格朗日乘子法作为对罚函数外点法和拉格朗日乘 子法的结合 求解精度较高 是一种非常切实可行的设计优化方法 本文通过实际 应用的例子说明了增广拉格朗日惩罚在应用过程中 首先对实际问题建立数学模型 再使用本方法可以加快找到最优结果的速度 也使最优结果更精确 总结目前的增广拉格朗日乘子法的应用 在实际应用时 建立模型后计算较为 复杂 因此和计算机结合 编写相应算法会更好 济南大学毕业论文 17 参 考 文 献 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 I