标题

Size: px

Start display at page:

Download "标题"

哄冬尚
5 years ago
Views:

1 第 38 卷第 5 期西南大学学报 ( 自然科学版 ) 2016 年 5 月 Vol.38 No.5 JournalofSouthwestUniversity (NaturalScienceEdition) Maẏ 2016 DOI: /j.cnki.xdzk 求解一类广义均衡问题的交替方向法徐洁, 张俊容, 刘佳西南大学数学与统计学院, 重庆摘要 : 通过修正拉格朗日乘子构造了一种新的交替方向法求解一类广义均衡问题, 分析了该算法的收敛性及其所产生序列的特性. 关键词 : 广义均衡问题 ; 交替方向法 ; 收敛性中图分类号 :O224 文献标志码 :A 文章编号 : (2016) 考虑如下一类广义均衡问题 : 确定向量 x * X, 使其满足 f(x *,x)+ <Kx *,x-x * > 0 s.t.ax B,x X (1) 其中函数 f:x X R 是关于第二变元的凸函数 ( 不必光滑 ),X R n,a R m n,b 为 R m 上的非空闭凸集,K 为单调映射,Ω 为该问题的非空解集. 若 K =0, 上述问题变为经典均衡问题 ; 若 f=0, 上述问题变为经典变分不等式. 广义均衡问题包含了这两类问题, 直接研究该问题是很有必要的. 均衡问题为优化问题和变分不等式问题的研究提供了统一的研究框架, 有关均衡问题的一些算法和问 [1-2] 题的延拓都有相关的研究. 而交替方向法 (ADMM) 是求解线性约束凸优化问题与变分不等式问题的一 [3-5] 种有效算法. 本文利用文献 [6] 中的 ADMM 算法求解一类广义均衡问题. 1 预备知识在 B 中, 存在向量 b 0, 使 Ax =b, 将问题 (1) 转化为以下形式 (1),(2) 式的解是等价的. f(x *,x)+ <Kx *,x-x * > 0 s.t.ax-b=0 引入线性约束拉格朗日乘子 λ R m, 问题 (2) 的增广拉格朗日函数为 b B,x X (2) L(x *,x,b,λ)=f(x *,x)+ (x-x * ) T Kx * -λ T (Ax-b)+ γ 2 Ax-b 2 令 ω =(x,b.λ), 它定义在 W =X B R m [7] 上. 根据鞍点定理, 对已知 ω k =(x k,b k,λ k ),L(x *,x, b,λ) 的一个鞍点的求解过程为 : L(x k,x,b k,λ k )-L(x k,x k,b k,λ k )= f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k - 1 收稿日期 : 基金项目 : 国家自然科学基金项目 ( ). 作者简介 : 徐洁 (1990 ), 女, 河南新乡人, 硕士研究生, 主要从事最优化理论与算法研究. 通信作者 : 张俊容, 教授.

2 2 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 38 卷令由凸函数 g(x) 的次梯度可得只需 x k 满足 λ kt (Ax-b k )+λ kt (Ax k -b k )+ γ 2 Ax-bk 2 - γ 2 Ax k -b k 2 g(x)= Ax-b k 2 γ 2 Ax-bk 2 - γ 2 Ax k -b k 2 (x-x k ) T γa T (Ax k -b k ) f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k + (x-x k ) T (-A T ){λ k -γ(ax k -b k )} 0 求出 x k, 令 x k+1 =x k. L(x k+1,x k,b,λ k )-L(x k+1,x k,b k,λ k )= -λ kt (Ax k -b)+λ kt (Ax k -b k )+ γ 2 Ax k -b 2 - γ 2 Ax k -b k 2 只需 b k 满足 λ kt (b-b k )+ (b-b k ) T γ(ax k -b k ) (b-b k ) T [λ k +γ(ax k -b k )] 0 求出 b k, 令 b k+1 =b k. 修正拉格朗日乘子令 λ k =λ k -γ(ax k -b k ) λ k+1 =λ k -γ(ax k -b k )= 有以下形式整理上述迭代过程有 λ k - [γ(b k -b k )+γ(ax k -b k )]= λ k - [γ(b k -b k )+ (λ k -λ k )] b k+1 æ è λ k+1 ö æ = bk ö æ - I 0 ö æ bk -b k ö èλ k èγi I èλ k -λ k f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k + x-x k æ æ ö -A T λ k ö b-b k λ k +γ(b k -b k ) èλ-λ k Ax k -b k + (b k -b k )+ 1 0 (4) γ ( λ k -λ k ) è [8] 将 (4) 式转化为以下形式其中 f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k + (ω -ω k ) T F(ω k ) ( η -η k ) T R( η k -η k ) (5) æ -A T λö η k =(b k,λ k ) F(ω)= λ èax-b æγi 0 ö R = I 1 æ è γ I M = I 0 ö èγi I

3 第 5 期徐洁, 等 : 求解一类广义均衡问题的交替方向法 3 易知 Q 为正定矩阵,G 是半正定矩阵. 2 算法及收敛性分析 æγi 0 ö Q =RM -1 = 0 1 è γ I æ0 0 ö G =R +R T -R T M = 0 1 è γ I 本节构造一类求解广义均衡问题的 ADMM 算法, 并分析该算法的收敛性. 算法 1 设初始值 ω 0 =(x 0,b 0,λ 0 ),γ (0,2),ε >0 1) 对当前点 ω k =(x k,b k,λ k ), 求解 ω k =(x k,b k,λ k ): ì x k =argmin{f(x k,x)+ (x-x k ) T Kx k -λ kt (Ax-b k )+ γ 2 Ax-bk 2 x X} í b k =argmin{- (λ k ) T (Ax k -b)+ γ 2 Ax k -b 2 b B} îλ k =λ k -γ(ax k -b k ) 2) 求 ω k+1 =(x k+1,b k+1,λ k+1 ): ì x k+1 =x k íæb k+1 ö æ = bk ö æ - I 0 ö æb k -b k ö îèλ k+1 èλ k èγi I èλ k -λ k 3) 若 ω k+1 -ω k <ε, 停止迭代 ; 否则,k=k+1, 转入 1). 接下来分析由算法 1 产生的序列收敛特性. 从算法 1 的迭代过程可以看出如果 { η k } 是收敛的,{ω k } 也是收敛的, 为了简化证明过程, 只需证明 { η k [9] } 收敛即可. 设 ω * 为以下变分不等式的解 f(x k,x)+ (x-x k ) T Kx k -f(x k,x * )- (x * -x k ) T Kx k + (ω -ω * ) T F(ω * ) 0 定理 1 Q 为正定矩阵,G 是半正定矩阵, 算法 1 产生的序列 { η k } 满足 η k+1 -η * 2 Q η k -η * 2 Q - η k -η k 2 G η * Ω (6) 证由于 η k+1 =η k -M ( η k -η k ),(5) 式中不等式右端可以改写为 f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k + (ω -ω k )F(ω k ) ( η -η k ) T RM -1( η k -η k+1 )= 又而 ( η -η k ) T Q( η k -η k+1 ) ( η -η k ) T Q( η k -η k+1 )= 1 2 ( η -η k+1 2 Q - η -η k 2 Q ) ( η k -η k 2 Q - η k+1 -η k 2 Q ) η k -η k 2 Q - η k+1 -η k 2 Q = η k -η k 2 Q - ( η k -η k )- ( η k -η k+1 ) 2 Q = η k -η k 2 Q - ( η k -η k )-M ( η k -η k ) 2 Q = 2( η k -η k ) T QM ( η k -η k )- ( η k -η k ) T M T QM ( η k -η k )=

4 4 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 38 卷 ( η k -η k ) T (R +R T -M T QM )( η k -η k )= 所以 η k -η k 2 G f(x k,x)+ (x-x k ) T Kx k -f(x k,x k )- (x k -x k ) T Kx k + (ω -ω k )F(ω k ) 1 2 ( η -η k+1 2 Q - η -η k 2 Q ) ηk -η k 2 G 令 ω =ω *, 相应地有 η =η * η k -η * 2 Q - η k+1 -η * 2 Q 又 η k -η k 2 G +2{f(x k,x k )+ (x k -x k ) T Kx k -f(x k,x * )- (x * -x k ) T Kx k + (ω k -ω * )F(ω k )} (ω k -ω * ) T F(ω k )=(ω k -ω * ) T F(ω * )=(λ k ) T (Ax * -b * )- (λ * ) T (Ax k -b k ) 所以 f(x k,x k )+ (x k -x k ) T Kx k -f(x k,x * )- (x * -x k ) T Kx k + (ω k -ω * )F(ω * ) 0 η k+1 -η * 2 Q η k -η * 2 Q - η k -η k 2 G η * Ω G 为半正定矩阵,Q 为正定矩阵, 根据定理 3.1 有 0 η k+1 -η * 2 Q η k -η * 2 Q 数列 { η k -η * } 单调递减且有界, 因而 { η k -η * } 为收敛数列, 并且不等式 (6) 两边同时取极限 lim η k+1 -η * 2 Q =lim η k -η * 2 Q lim η k -η k 2 G =0 定理 2 G 是半正定矩阵, 算法 1 产生的序列 { η k } 收敛于一点 η' Ω. 证首先证明 R 为非奇异矩阵, 由 (5) 式有 ( η k -η') T R( η k -η k ) 0 ( η k -η') T R( η k -η k ) 而 f(x k,x k )+ (x k -x k ) T Kx k -f(x k,x')- (x'-x k ) T Kx k + (ω k -ω')f(ω k ) 0 ( η k -η') T R( η k -η k )= ( η k ) T R( η k -η k )- ( η') T R( η k -η k )= ( η k ) T R( η k -η k )- ( η k ) T R( η k -η k )+ ( η k ) T R( η k -η k )- ( η') T R( η k -η k )= ( η k -η k ) T R( η k -η k )+ ( η k -η') T R( η k -η k ) ( η k -η k ) T R( η k -η k )= ( ær η k -η k ) +R T ö T è 2 ( η k -η k ) 0 又 { η k } 有界, lim η k -η k 2 G =0 { η k } 也是有界的, 记 η' 为 { η k } 的一个聚点,{ η k i } 是 { η k } 的一个收敛于 η' 的子列,{ η k i } 也收敛于 { η'}. 由 (5) 式知 f(x k,x)+ (x-x k ) T Kx k -f(x k,x k i )- (x k i -x k ) T Kx k + (ω -ω k i )F(ω k i ) ( η -η k i ) T R( η k i -η k i ) 0

5 第 5 期徐洁, 等 : 求解一类广义均衡问题的交替方向法 5 f(x *,x)+ (x -x * ) T Kx * 与 F(ω) 都为连续函数, 所以 f(x k,x)+ (x-x k ) T Kx k -f(x k,x')- (x'-x k ) T Kx k + (ω -ω')f(ω') 0 (7) ω' 为 (7) 式的解, 从而即 { η k } 收敛于一点 η'. 3 结论 lim η k -η' 2 G =0 广义均衡问题包含了经典均衡问题和变分不等式. 本文采用了 ADMM 算法来解决该问题, 并证明了该算法的收敛性. 应用该算法解决广义均衡问题是一种崭新的尝试, 它对于研究均衡问题具有启发性, 今后将会进一步对该算法进行数值模拟实验, 使该算法在解决均衡问题时得到实际应用的支持. 参考文献 : [1] 段培超. 广义均衡和不动点问题的迭代算法 [J]. 河北师范大学学报 ( 自然科学版 ),2012,36(02): [2] 代宏霞. 广义混合均衡问题 [J]. 四川大学学报 ( 自然科学版 ),2013,50(05): [3] 周瑾. 交替方向法求解带线性约束的变分不等式 [J]. 高等学校计算数学学报,1999(2): [4] 黎景. 求解一类非对称单调变分不等式的非精确自适应交替方向法 [J]. 数学理论与应用,2007(3): [5] 张敏, 韩德仁, 何洪津, 等. 解可分离结构变分不等式的一种新的交替方向法 [J]. 中国科学 : 数学,2012,42(2): [6] HEB,LIAO LZ,HAN D,etal.A NewInexactAlternatingDirections MethodforMonotoneVariationalInequalities [J].MathProgram,2002,92(1): [7] 林贵华. 非线性最优化基础 [M]. 北京 : 科学出版社,2011. [8] HEB,YUAN X M.A ClassofADMM-BasedAlgorithmsforMulti-BlockSeparableConvexProgramming [DB/OL]. ( )[ ].htp:// [9] HEB,YUAN X M.OntheDirectExtensionofADMMforMulti-BlockSeparableConvexProgrammingandBeyond: From VariationalInequalityPerspective[DB/OL].( )[ ].htp:// AlternatingDirection MethodofMultipliersforSolving aclassofgeneralequilibriumproblem XU Jie, ZHANGJun-rong, LIU Jia SchoolofMathematicsandStatistics,SouthwestUniversity,Chongqing400715,China Abstract:Thealternatingdirectionmethodisoneoftheclassicmethodsforsolvingoptimizationproblems withaseparablestructure.itsessenceisliesinthatapplyingtheoriginalproblem'solutionequivalentto thesaddlepointoftheaugmentedlagrangianfunctiontoiterativetheparameters,andthenfindingoutthe solutionoftheoriginalproblem.thispapercorrectslagrangianmultiplierstoconstructanewalternating direction methodforsolvingaclassofgeneralequilibriumproblem,andthenanalyzesthepropertiesofthe alternatingdirectionmethodandderivestheconvergenceofthealternatingdirectionmethod. Keywords:generalequilibriumproblem;ADMM (AlternatingDirection MethodofMultipliers);convergence 责任编辑张栒

6 6 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 38 卷

标题

第 35 卷第期西南大学学报 ( 自然科学版 ) 3 年月 Vol.35 No. JouralofSouthwestUiversity (NaturalScieceEditio) Feb. 3 文章编号 :673 9868(3) 69 4 一类积分型 Meyer-KiḡZeler-Bzier 算子的点态逼近赵晓娣, 孙渭滨宁夏大学数学计算机学院, 银川 75 摘要 : 应用一阶 DitziaṉTotik