增广拉格朗日函数的两种可分化方法之比较!

增广拉格朗日 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数的两种可分化方法之比较! ! "#$# 年$$ 月 重庆师范大学学报(自然科学 版) %&’ "#$# 第" 卷 第* 期 +&,-./0 &1 23&.456.4 %&-7/0 8.6’9-:6; (%/;,-/0 69. 9 ) ?&0 " %& * 运筹学与控制论 @AB :$# CD*DE + B % $* "F **DC "#$# #* ##" 增广拉格朗日函数的两种可分化方法之比较! 王! 磊，白富生 (重庆师范大学 数学学院，重庆 G###G ) 摘要:可分方法用于将一个复杂的大规模优化问题分解成各个子问题进 行求解。增广拉格朗日松弛方法的主要缺 点是由其引入的二次项是不能分离的。为了处理这种增广拉格朗日函数的不可分离性，可将辅助问题原理方法或 分块坐标下降方法应用于增广拉格朗日松弛方法。与已有文献中对带有约束条件! " ! # # 的优化问题进行这两种 " 可分方法的比较不同，本文对带有更一般的约束条件―――线性约束$ # %! 的优化问题进行这两种可分化方法的比 较;最后给出的两个算例证实了本文的理论 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 结果―――在处理不可分离的增广拉格朗日函数的时候，在一定条件 下，分块坐标下降法往往比辅助问题原则法更快得到最优值。 关键词:可分化方法;增广拉格朗日松弛;辅助问题原理;分块坐标下降 中图分类号: A""$ " 文献标识码:H! ! ! 文章编号:$* "F **DC("#$# )#*F ### F #I $ 预备知识 为了解决数学规划中的大规模问题，可分化方法的产生是有必要的。可分化方法又称为分解方法，可应 用于多区域电力系统分析、网络设计、价格决策管理等模型中〔$FI 〕，早在上世纪*# 年代就已提出，如@/.;J64F 〔* 〕 K&019 分解和L9.M9-: 分解 。后来有不少相关的研究成果问世，现在拉格朗日松弛(NO )方法是使用最广 泛的方法。而在NO 方法中，有两个主要的方法:经典拉格朗日松弛(P39 0/::6 /0 N/4-/.46/. -90/Q/;6&. )方 法〔 FD 〕和增广拉格朗日松弛(P39 /,479.;9M N/4-/.46/. -90/Q/;6&. )方法〔$#F$" 〕，分别简记为2NO 方法、HNO 方 法。2NO 方法在求解优化问题时，由于对偶间隙的存在常常会得到一个不可行的解，而HNO 方法好于2NO 方法的一个方面就是它可能会得到一个可行解;但是在解非凸问题时，HNO 方法可能会得到一个局部最优 值;除此之外， HNO 方法另一个主要缺点是由增广拉格朗日函数引入的二次项是不可分离的。 〔$C 〕 〔$G 〕 为了克服这个缺点，使用最广的方法是辅助问题原则HRR 方法 和分块坐标下降(L2@ )方法 。在 文献〔 $I 〕中，作者用HRR 方法和L2@ 方法比较求解带有约束! " ! # # 的优化问题的快慢，结果表明分块坐 " 标下降法比辅助问题原则法更快得到最优值。本文将文献〔$I 〕中的约束 推广为更一般的线性约束$ # %! ， 然后去比较在这种条件下的HRR 方法和L2@ 方法。即将约束进行了推广， 使约束条件更一般化，扩大了应 用的范围。 本文分为两个部分。第一部分介绍HNO 方法、HRR 方法和L2@ 方法; 第二部分从理论和算例比较了两 种可分化方法，即HRR 法和L2@ 法。 $ $ 增广拉格朗日松弛方法 为了解决以下原始问题(! #!& ，$ #!’ ) 76. (! ) * ($ ) ($ ) : ; $ # %! ，! #+ ，$ #+ 其中 :!& $ (" S ， S 〕，* :!’ $ (" S ， S 〕，且% 是一个’ , & 矩阵。 ($ )式的拉格朗日函数即- (! ，$ ，) (! ) * ($ ) P (%! " $ )，用它可以得到其对偶问题7/Q . ()， ! ! ! !’ ! # ! 收稿日期:"# $#F #G F $" 资助项目:国家自然科学基金(%& $# $ $$$T ) 作者简介:王磊，男，硕士研究生，研究方向为最优化理论与算法; 通讯作者:白富生，UF7/60 :1:V/6W 5., 9M, . % 重庆师范大学学报(自然科学版)5 6778 :9 9 :::; # ? ; #5 5 5 5 5 5 5 5 5 5 第%@ 卷 其中对偶函数为! () !"# % (" )& ’ ($ )& $ ( " $ )。即对于固定的拉格朗日乘子，要得到以上问题的 ! ! " # ，$ # # # 最优解，可以分解为求两个独立问题的最优解。但是在非凸情况下，由于对偶间隙的存在，可能降低了这个方 法的可应用性;即使在凸的情况下由于对偶问题! () !"# % (" )& ’ ($ )& $ ( " $ )的非光滑性，也可 ! ! " # ，$ # # # 能存在不足的地方。 通过使用增广拉格朗日函数，有许多方法凸化参数问题，在下节将介 绍其中两种方法。为了把对偶问题 分解为两个子问题，一个定义在# 上，另一个定义在# 上，将增广拉格朗日 函数中的耦合约束 " $ 松弛，这 意味着在目标函数 $ * % % (" )& ’ ($ )中增加了拉格朗日项 ( " $ ) 和惩罚项 。形成的这种最大― ! " $ % $ * % 最小化问题称为对偶问题，即!&’ !"# % (" ) & ’ ($ )& ! ( " $ )& " $ 。 !+ " # ，$ # ! # # # % 通常情况下，增广拉格朗日函数被定义为 , (" ，$ ，) % (" )& ’ ($ )& $ ( " $ )& * % (% ) * ! ! " $ % 相应的对偶函数为! () 。 于是，对偶问题可描述为!&’ ! ()。 ! !"# , (" ， $ ，) ! * ! * * !+ " # ， $ # ! # # # * 注意到，增广拉格朗日函数(% )式，由于有二次惩罚项 " $ % 而不能将其分离开。 % - % 可分化方法 本文的焦点是基于不可分的增广拉格朗日函数的最小 化 !"# % (" )& ’ ($ )& !$ ( " $ )& " # ，$ # # # * " $ % ，将其分化为小的子问题这种方法称为辅助问题原则方法 ( ** )。粗糙地说， ** 方法将拉格朗 % * / 日函数中的二次项 " $ % 在当前迭代(". ，$ . ) 处线性化，再增加一个二次的可分离项( )(" " % & % % . $ $ % )，于是有 . $ $ / % % !"# % (" )& ’ ($ )& ! ( " $ )& *( ". $ . )( " $ )& ( )(" " & $ $ ) " # ， $ # . . # # % / / 增加的二次项 ( )( % & $ $ % )0 ( )( $ $ % " " " ，$ ) (" ，$ ) % . . % . . 的主要作用是使部分项线性化的增广拉格朗日函数成为严格凸函数。 于是，由于,* 中添加了这个逼近项，求解,* 的最小化问题 可以分化为求解两个子问题的最值((". & ， $ . & )是新的迭代) $ $ / % " &+,!"#% (" )& !. " & *( ". $ . ) " & ( )" " . & " # . # % $ $ / % $ &+,!"# ’ ($ ) !. $ *( ". $ . )$ & ( )$ $ . & $ # . # % 另一个可供选择的方法是分块坐标下降(-./ )法，也称为非线性高 斯―赛德尔方法。与 ** 方法不同 -./ 方法直接将, 最小化。当在定义域# 内最小化时， 定义域# 内的变量在它们当前最好的值固定，这 的是， * 个值记作$ ;类似地，当在定义域# 内最小化时，定义域# 内的 变量在它们当前最好的值固定，这个值记作 . 〔 0 〕 ". & ，依此下去。在凸的情况下，收敛性能够保证 。于是，,* 的最小化问题可分解为两个子问题((". & ，$ . & ) 是新的迭代) $ * % $ * % ". & &+,!"#% (" )& !. " & ( ) " $ . ， $ . & &+,!"# ’ ($ ) !. $ & ( ) ". & $ " # $ # # % # % - 1 可分化算法 这部分用一个熟知的事实:对偶函数在当前对偶迭代的梯度等于松弛约束在当前原迭代的值，即 ! ( )0 ( " $ )带有辅助问题原则( ** )的增广拉格朗日松弛( 23 )方法可以总结为以下的 23 4 ! * . . . ** 算法( 23 算法也称为乘子法)。 第7 期3 3 3 3 3 3 3 3 3 3 3 3 3 王3 磊，等:增广拉格朗日函数的两种可分化方法之比较 4 !"# $ !%% 算法 第一步，核对终止准则。如果对偶函数的梯度的范数 & ，则停止，(" ，% ， )是最优解; !" $ % ! # # "# # # + # 第二步，计算" "#$%&’ (" )’ " !" ’ * (!" $ % )!" ’ ( )" $ " ; # # # # # ’ ! " # # + # 第三步，计算% "#$%&’ , (% )$ " % $ * (!" $ % )% ’ ( )% $ % ; # # # # # ’ ! % # # 第四步，对偶变量的更新。令" - " ’ * (!" $ % ); # ’ ! # # # ’ ! # ’ ! 第五步，罚参数更新。如果 !"# ’ ! $ % # ’ ! . # ??!"# $ % # ，则令*# ’ ! $ *# ，+# ’ ! %*# ’ ! 。 一个合适的选择 是 !/ !* ， ， 。 # $ % 类似地，带有分块坐标下降(+,- )的./0 方法可以总结为以下的./0 1 +,- 算法。 !"# $ &’ 算法 第一步，核对终止准则。如果对偶函数的梯度的范数 & ，则停止。(" ，% ， )是最优解; !" $ % ! # # "# # # * # 第二步，计算"# ’ ! "#$%&’ (" )’ "# !" ’ ( )!" $ % # ; " # * # 第三步，计算% # ’ ! "#$%&’ , (% )$ "# % ’ ( )!"# ’ ! $ % ; % # 第四步，对偶变量的更新。令" - " ’ * (!" $ % ); # ’ ! # # # ’ ! # ’ ! 第五步，罚参数更新。如果 !"# ’ ! $ % # ’ ! . # ??!"# $ % # ，则令*# ’ ! $ *# 。一个合适的选择 是# !/ !* ， $ 。 理论比较 这一部分从理论的观点比较了.22 法和+,- 法。 命题!3 辅助问题原则.22 法中的迭代等价于 * + * # # # " "#$%&’ (" )’ "# !" ’ ( )!" $ % ’ " $ " $ !" $ !" (4 ) # ’ ! " # # # # * + $ * # # # % "#$%&’ , (% )$ "# % ’ ( )!" $ % ’ ( )% $ % (5 ) # ’ ! % # # # " ，% )是当前的迭代的输入对，而 (" ，% )是下个迭代的输出对。 其中(# # # ’ ! # ’ ! 证明3 考虑 + + $ * * *(!" $ % )!" ’ ( )" $ " - * (!" )!" $ *% !" ’ " $ " ’ " $ " - # # # # # # # + $ * * * * * * * " $ " ’ !" $ *% !" ’ % $ !" $ % ’ " $ *" " ’ " ’ * ! " " - # # # # # # # + $ * * * " $ " ’ !" $ % ’ ($ !" $ % ’ " $ " "# ’ " ’ " ! !"# )- # # # # + $ * * * " $ " ’ !" $ % ’ 〔" $ " $ !" $ !" ’ !" $ % 〕- # # # # # # * + * * !" $ % ’ " $ " $ !" $ !" ’ (!" $ % ) # # # # # + 则在 上的最小化 %&’ (" )’ "# !" ’ *(!"# $ % # )!" ’ ( )" $ " " # # 可以写为 * + * * %&’ (" )’ "# !" ’ !" $ % ’ " $ " $ !" $ !" ’ (!" $ % ) (6 ) " # # # # # # + + $ * * 类似地，考虑 $ *(!"# $ % # )% ’ ( )% $ % - $ *(!"# )% ’ *(% # )% ’ ( )% $ % ’ ( )% $ % - # # # 4 重庆师范大学学报(自然科学版). 988: :; ; 7 %?@ 7 %. . . . . 第!2 卷 ! " # ! # ! " # ! " " ( ) & ( ) " #($ ) $ & ( ) " #(’ )$ & #($ )$ $ " $ $ % $ % % ! % ! % ! ! " # # # ( )$ " $ ! & ( )’ " $ ! " (’ ! " $ ! ) ! % ! % ! % % " " ! ! 则在* 上的最小化#$% + ($ )" !% $ " #(’ % " $ % ) $ & ( )$ " $ ，可以写为 $ * % # ! " ! " # ! # ! # ! ! #$% + ($ )" !% $ & ( )$ " $ & ( )’ " $ " (’ " $ ) (& ) $ * % % % % # ! ! ! 于是，目标函数 ( # # ’ )式和目标函数(& )式中的固定项 ( " )和 ( " ) 可以不要，这也不 ’ $ $ ’ ! % % ! % % 法中的迭代等价于 会改变最优的迭代。因此， # ! # " % ! % ! % ! +,-#$%, ( )& !% ’ & ( )’ " $ & " " ’ " ’ % & * * % % % # ! ! ! # ! " # " % ! % % ! $ +,-#$% + ($ )" !% $ & ( )’ " $ & ( )$ " $ % & * $ * % % # ! ! 这就是要证明的结果。 证毕 〔*’ 〕 推论* . 对于! # ，’ - ， 法就是非线性 高斯―赛德尔或/01 法的雅可比式。 证明. 比较命题* 和以下的/01 法(非线性高斯―赛德尔法) " # ! " # ! +,-#$%, ( )& !% ’ & ( )’ " $ ， $ % & * +,-#$% + ($ )" !% $ & ( )’ % & * " $ (2 ) % & * % $ * * # ! # ! 对于! # ，’ - ，(3 ). (4 )式的最后一项就没有了。 因此，这两种方法的不同之处仅在于:在(4 )式 中， 法用的是旧的迭代 % (雅可比方法)，然而在(2 )式中/01 法用 的是新的迭代 % & * (非线性高斯―赛 德尔法)。 证毕 众所周知的是在数值分析中非线性高斯―赛德尔法很可能优于雅可 比法。主要原因就是非线性高斯― 赛德尔方法在当前的迭代中就直接使用新产生的 % & * ，而雅可比方法在 下个迭代开始才使用新产生的 % & * (在当前的迭代中使用的是 % )。因此，在! # ，’ - 这种情况下，与 方法相比，/01 方法能更快的 收敛到最优值。 ! 在命题* 中，如果考虑目标函数在 * / * 上的最小化，当’ - 时，(3 )式中的项 " ! " ! % # ! " # ! " # ! 和(4 )式中的项( ) ! 可 以合并写成( ) " " ! ，若! # ， 则前 ’ " ’ $ " $ ，$ )" ( ，$ ) ( ! % ! % ! % % 式将不存在;但是对于任意的! 0 # ，它将惩罚 远离( % ，$ % )的迭代对( % & * ，$ % & * )。 当’ % - ，有 ! # ! # ! " # ’ ! " ! " ’ " ’ ! & " ! " ’ ! " ! " ! (5 ) ! % ! % ! % ! % ! % 因此，当 ’ ! 0 * 且对于任意的! 0 # ’ ! ， 或者当 ’ ! 1 * 且对于任意的! 0 # 都有(5 )式中的结果。 ’ ! ’ * ’ ! 0 * 综上所述，一般来说，比起! # ，’ - 这种情况，对于 或 。 方法很可能要更 ! 0 # ! 0 # ’ ! 多的迭代才能达到最优点，因为前两式的惩罚从当前迭代向后一个迭代的长步长。 3 数值算列 例 *. #$% , ( )& + ($ ) ! & ! & $! * ! ( ， ) !! ，$ ! * ! # # * 67 87 . (*. * ) $ ! 第: 期- - - - - - - - - - - - - 王- 磊，等:增广 拉格朗日函数的两种可分化方法之比较 4 ! ! 很容易知道最优解为! " (! ，! )，# " ! 。在"#$ % "&& 算法和"#$ % ’ 算法中，令初始罚参数$! 等 于*。参数% 等于+ ，常数 ，，分别等于 *& *，, ，, 。前面 提到的两种方法解决这个问题的一些数据在下表 ! ! " # * 中。 例,- ./0 ’ (! ) (# )" ,!, !, !, ,#, * , + ! " (! ，! ) !, ，# ! * , # # ! ? * ? ? ? 12 32 (!& 4 * !& 4 !& ,4 ) " # ! ? , ? ? ? ? !+ ? 与例* 类似地，有下面的表, 。 表*- 例* 的两种算法比较