资源描述：
《基于投影交替方向法求解结构型单调变分不等式》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第３８卷第１期西南大学学报(自然科学版)２０１６年１月Vol?３８No?１JournalofSouthwestUniversity(NaturalScienceEdition)Jan?２０１６DOI:１０?１３７１８/j?cnki?xdzk?２０１６?０１?０１４基于投影交替方向法求解结构型单调变分不等式①许微,彭建文重庆师范大学数学学院,重庆４０１３３１摘要:通过构造新的下降方向对孙敏等人给出的投影型交替方向法进行改进和推广,提出了改进投影型交替方向法．与前者相比较,该方法具有收敛速度快,迭代次数少的特点．
2、在相同的假设条件下,证明了新方法的全局收敛性,并通过数值试验初步验证了该方法的有效性．关键词:单调变分不等式;可分离结构;投影收缩;交替方向法;全局收敛性中图分类号:O２２１?２文献标志码:A文章编号:１６７３９８６８(２０１６)０１００９００８对于一个凸优化问题:minf(x)s?t?x∈X(１)其中:X是Rn中的一个非空闭凸子集,f(?)是从Rn到R的可微凸函数．记F(x)＝∇f(x)若x∗是问题(１)的解,则该凸优化问题可以转化为一个变分不等式的形式:(x－x∗)T∗)≥０∀x∈X(２)F(x本文中,我
3、们考虑的是一种带线性约束的结构型凸优化问题:min{f(x)＋g(y)Ax＋By＝b,x∈X,y∈Y}(３)其中:f:Rn１n２m×n１;B∈Rm×n２;b∈Rm;X,Y分别为Rn１和→R,g:R→R为可微凸函数;A∈Rn２R中的一个非空闭凸子集．在问题(３)中,对线性约束Ax＋By＝b引入Lagrange乘子λ∈Rm,即可得到一个定义在W＝X×Y×m上的Lagrange函数:RT(Ax＋By－b)(４)L(x,y,λ)＝f(x)＋g(y)－λ则对于问题(３)的求解,我们可以转化为找Lagrange函数的鞍点
4、(x∗,y∗,λ∗),满足:∗,y∗,λ)≤L(x∗,y∗,λ∗)≤L(x,y∗,λ∗)L(x∗,y∗,λ)≤L(x∗,y∗,λ∗)≤L(x∗,y,λ∗)L(x为了方便,记F(x)＝∇f(x),G(y)＝∇g(y)利用一阶最优性条件,上述鞍点问题等价于:找(x∗,y∗,λ∗)∈W,使得对∀(x,y,λ)∈W,有①收稿日期:２０１５０３０７基金项目:国家自然科学基金项目(１１１７１３６３);重庆市基础科学与前沿技术研究重点项目(cstc２０１５jcyjBX００２９)．作者简介:许微(１９８９),男,江苏宿迁人,
5、硕士,主要从事最优化算法和最优化控制研究．通信作者:彭建文,教授．２西南大学学报(自然科学版)http://xbbjb?swu?edu?cn第３８卷(x－x∗)T(F(x∗)－AT∗)≥０ìïλï(y－y∗)T(G(y∗)－BT∗)≥０íλïï(λ－λ∗)T(Ax∗∗î＋By－b)≥０令æxöç÷w＝çy÷ç÷èλøTæF(x)－Aλöç÷TQ(w)＝çG(y)－Bλ÷ç÷èAx＋By－bø则问题(３)等价于如下结构型变分不等式问题的形式:找一点w∗∈W,使得(w－w∗)T∗)≥０∀w∈W(５)Q(w[１]对
6、于结构型变分不等式(５)的求解,Gabay最早提出了一种非常有效的求解方法—交替方向法(ADM),该方法将一个大型原问题分解为一系列低维子问题,在每步迭代过程中只需要求解一些子变分不等式．近[２]年来,许多学者在如何有效提高交替方向法的计算能力方面提出了很多改进的策略．如Ye通过对下降方[３][４]向的步长进行优化,提出了一种预测—校正交替方向法;由于变分不等式求解的困难性,Han,He等[５－６]给出了非精确求解的正交投影交替方向法;Sun在此基础上提出新的投影型交替方向法,在每步迭代过程中只需进行一次正交
7、投影．本文改进了文献[６]中的方法,通过有效利用每步迭代过程所产生的预测点,提高了正交投影交替方向法的计算能力．相对于文献[６]中的方法,改进后的投影型交替方法具有迭代次数少,收敛速度快的特点．１预备知识本文主要在Euclidean范数下,给出一些基本定义和相关性质,记T‖x‖＝xxn中的一个非空闭凸子集．用P(v)表示点v从Rn到Ω上的投影,记为:定义１设Ω是RΩn,∀u∈Ω}PΩ(v)＝argmin{‖v－u‖v∈Rn,下式成立:引理１对任意的一个非空闭凸子集Ω⊆R(v－P(v))T(u－P(v))≤０∀
8、v∈Rn,∀u∈Ω(６)ΩΩ(v－w)T[P(v)－P(w)]≥‖P(v)－P(w)‖２ΩΩΩΩ通过引理１,利用CauchyＧSchwarz不等式,我们可以得到投影的非扩张性:n(７)‖PΩ(v)－PΩ(w)‖≤‖v－w‖∀v,w∈Rn,记引理２对任意的β＞０,x∈Re(x,β)＝x－PΩ(x－βF(x))为F(x)在Ω上投影的余差函数,则x∗是变分不等式(２)的解,当且仅当e(x∗,)＝０．β引理
