logo资料库

增广拉格朗日乘子法.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.23M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    第5卷第l期 2002年6月 沙洲职业工学院学报 Journal of Shazhou Polytechnical Institute of Technology V01．5．No．1 Jun．，2002 关于单调变分不等式的一种邻近 增广拉格朗El方法 王治华 (沙洲职业工学院，张家港215600) 摘要：对单调变分不等式的一种新的拉格朗日方法(AL)进行讨论。这种方法只需要解一系列强 单调变分不等式子问题。允许参数从一个叠代点到另一个叠代点变化。在比较弱的条件下算法的 收敛性得到了证明。 关键词：单调变分不等式；邻近点方法；增广拉格朗日方法 中图分类号：0224 文献标识码：A 文章编号：1009—8429(2002)01—0001—06 1 引言 设Q是Rn的一个非空闭的凸集，F是一个从R“到自身的一个单调连续映射，变分不等 式问题是寻找一个向量u+E Q，使得 (U一“+)rF(“。)≥0 V “E n (1．1) 用VI(Q，F)来表示。 在算子研究，经济平衡，非线性分析中，变分不等式方法是一种经常使用的方法。对于变 分不等式，现在有许多叠代方法n¨2】[3】㈨1 3。。 在这篇文章里，我们关心的是具有下面这种特殊结构的变分不等式：求z。E n (z—z+)Tf(z。)≥0 n={z I触=b，z E X} V M∈0 (1．2) (1．3) 其中X是Rn的非空闭凸子集，A∈R“”，b∈R”，f：X—X是一个给定的单调算子， 问题(1．2)一(1．3)等价于下面一个问题： 求z’∈X，Y’∈R” (z—z。)丁(f(z+)一A0’)≥0 Ax+=b (1．4) (1．5) 这个问题的解集用Q。表示。对于问题(1．4)一(1．5)，可以用增广拉格朗日方法来 解吲㈨Ⅲ。增广拉格朗日方法的思路如下，从给定的一对x，Y)开始，它的校正(文，歹)是通过下 面的计算得到 (z’一i)r{，(童)一A丁[Y—fl(AX—b)]}≥0 (1．6) 收稿日期：2002—04—10 作者简介：王治华(1969一)，男，沙洲职业工学院基础科学系讲师，南京大学硕士生。 万方数据 · 1 ·
    歹=Y—p(Aj—b) (1．7) 由于求解的次数明显地依赖于惩罚因子0，Wang和Liao在文献[9]提出了一个修整参数 p的办法，在他们的算法中允许参数|3随叠代点而变化，在文献[11]里，Kontogiorgis和Meyer 给出了另一个算法，允许惩罚因子是一个正定矩阵。B．S．H发展了这方法。川。最近B．S．He 对单调变分不等式提出了一种新的不精确交替方向法，只要不精确的解子问题就可以了馏】。 受上述这些算法的启示，我们讨论一种临近的增广拉格朗日方法： 给定点(x，y)，我们通过下面的方法得到新的点(曼，歹)： X’一i)丁{厂(王)一A丁[y—fl(Ai一6)]+)，(童一z)}≥0 b：Y一卢(A奎一6) 其中口，y是给定的正常数。， (1．8) 如果．厂是单调的，那么(1．8)变成了强单调。在下面的算法中，允许卢，y被～系列正定 矩阵{H。}，{R。}代替。 2预备知识 用II x|l=~／zTz来表示欧几里德范数，设n是R”的一个非空闭凸子集。欧几里德范 数下的投影用Pn(．)表示，即： Pn(副)=argmin{{f可一“fl f M∈o i} 设F是一个Q上的一个映射，如果 (乱一口)T(F(“)一F(勘))≥0 V“，“∈n (2．1) 那么称F在Q上单调。 由于我们用一个正数口乘变分不等式VI(Q，F)是不变的，有下面众所周知的引理： 弓l理1： 设Q是R“的一个非空闭凸子集，那么U。是VI(Q，F)的一个解的充要条件 U。=P“U’一肛(U。)] 因此，解一个变分不等式等价于找残量函数 e(“，卢)=甜一Pn(“～犀F(U)) 的一个零点。一个基本的投影性质是 (u—Pn(口))r(Pn(u)一甜)≥0 V可∈R” V“∈n 可以推出 l|Pn(口)一“lI 2≤l|口一“lI 2～l|勘一Pn(铆)0 2 II Pn(甜)一Pn(口)I|2≤≤Il“一口l|2 V“，可∈R“ V M∈n V u∈R” 设u=(X，y)T∈W=X×R“，问题(1．4)一(1．5)等价于求x’∈X，y。∈R“，满足 {(∥一z’)T(f(z’)一ATy’)≥0 ((y—y’)T(Ax’一6)≥0 所以解问题(1．4)一(1．5)相当于找出 V z7∈X V y∈R” g(“)=-Px t x-If(z’-Ary]}Ax b 的零点。在下面的讨论中作一个标准的假设： ／、 ． 万方数据 (2．2) (2，3) (2．4) (2．5) (2．6) (2．7) (2．8)
    假设A：x是非空闭凸集，Q+是非空。 3临近点拉格朗日方法 为了保证算法的收敛性，给出下列条件， 条件c：设{讯}孑是一个非负序列，且∑孑Tlko，帮^≤地+·≤(1+r／k)Hk R>0，R≤R川≤(1+仇)R^ 1： 2： 由数学分析可知，∑仉<。。等价于Ⅱ(1+啦)(≥)H是指H，一H是正定(半正定)。 注：如果R6=0，H。=口，那么这个算法就是(1．6)一(1．7)。由R。>0(指R是正定 的)，只要算子f(z)单调的，就保证了算子^的强单调，这样就保证了子问题(3．2)的可解 性，并且解是唯一的。 为了方便起见，记 “=G)柚=f‘可) 引理2： 在假设A下，算法1产生的序列满足 (M‘一“+)_D^(“6一M6十1)≥||“‘一M6+1|J D^ 证明：根据(3．2) (z+一z‘+1)一厂(z‘+1)≥0 在由(1．4) (z’一．717‘+1)了’(一f(z+)+A7≥’)≥o (3．6)+(3．7)，再利用f的单调性和(3．3) 万方数据 (3．5) (3．6) (3．7) 3 ·
    (夕一Y。)1了i1(矿一yk“)+ (z6一z+)TRt(z‘ 一z‘+1)≥ ||Ax‘”一b||备。 + ^ z—z ^+l 2 lI |l R5 引理得证。 定理1： 在假设A下，如果条件C满足，算法1产生的序列具有： lI“H1一“。II乞川≤(1+仇)II越6一“+l|毛。一II“6一“¨1 l|乞。 (3．8) 证明，由条件C可知 II“¨1一乱’l|乞川≤(1+仉)lI“¨1一M’||乞。 ≤(1+仉)Il(U‘一“+)+(“‘+1一“‘)ll乞； ≤(1+玑)|J“6一“’IJ乞。+Jl甜‘+1一“。JI乞。 一2(“6一“’)rD^(U‘一M6+1) ≤(1+仇I|f“。一“’ff乞。一if“。一2‘¨1 f|乞。 根据引理2，得到 4收敛性分析 引理3： 在假设A下，如果条件C满足，算法1产生的序列具有： lira Z—+∞ II M‘～M针1 Il 2D．=0 证明：由定理1可得 l|“‘+1一M。l|乞。+。≤(1+叩。)I|“‘一“。II乞。≤… (4．1) k ≤Ⅱ(1+17；)lI让。一“。Il乞。≤C，lI“。一M+Il乞。 (4．2) 所以…“‘一“。II乞。}有界，存在常数L>O。使得I|乱‘一“+Il乞。≤L 根据定理1(3．8)，两边相加 “ M一 2 D ‘ “ 一 比 ／一 “ 一 甜 2 D 2 D 。量 此因 lira Il“‘一“¨1 I|2DI=0 + ∑仉II“‘一“+lI乞。 ^=O + L∑仇=||“。一M’I‰+LC, (4．3) 定理2： 在假设A下，如果条件C满足，算法1产生的序列具有： lira e(“¨1)=0 其中e(u)是(2．8)所定义 证明： 忆∽+1)俨=扩1。刚奢∥+1卜的¨1’112 (4．4) 根据(3．2)，得到 万方数据 ll ∥z¨1。搿≥吼¨L盯bH。“y+1¨I 触针1—6 I
    利用(2．6) ≤I l 一 砭圻 ¨z∥ 一 缸“y ，0 =||“‘一M¨1 Il 2D^2 (4．5) 由范数的等价性可知，存在常数p>0，使得 |l U4一U¨1 JI乞。：≤矿f|U‘一“¨1 l|乞。 所以 P(甜针1)≤卢2 0“‘一U¨1 I|乞。 再根据引理3，有lira e(uk+1)=0 ^—+∞ 定理3： 在假设A下，如果条件C满足，{u。}是算法1产生的序列，则{u。}收敛于问题 (1．4)一(1．5)的一个解。 证明：根据(4．2)，{uk}有界，所以{uk}至少有一聚点，设U‘是其一聚点，且一子列{uk，l收 敛于u’，所以 V愚>k。 V e>0，]ko>0，使得V k。≥k。，(“～∈{扎‘-})，均有 ||“‘t—U。||<￡／cp |I M‘一“+II≤Ⅱ(1+琅)I|“‘。一“’||≤Cp l|M％一“’||<￡ i 2 ko 反以lim“‘=“‘，又因为e(u)是连续的，故可得 ^—-∞ e(“。)=lira e(“‘)=0 k一∞ 根据引理1，u+是问题(1．4)一(1．5)的解。 在实际中，{H。}和{R。}如何选取值得进一步研究。 参考文献： [1]Noor，m．A．Some recent advances in variational inequalities，part I：Basic concepts[J]．New Zealand Journal of Mathematics，1997，26：53—80． [2]Dafermos，S．An iterative scheme for variational inqualities[J]．Mathematical Programming，1983，26：40—47． [3]Harker，P．T，Pang，J．S．Finite—dimensional variational inequality and nonoelinear complementarity problems，a survey of theory，algorithms and applications[J]．Mathematical Programming，1990，25：247—262． [4]B．S．He．A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programmingJ[J]．AppHed Mathematics and Optimization，1992，25：247—262． [5]Gabay，D．“Application of the method of multipliers to variational inequalities，”in Augmented Lagrange Methods：Applieatons to the Solution of boundary—valued Problems．M．Fortin and R．Glowinsky，eds．，North Holland，Amsterdam，The Netherlands，1983，299—331． [6]D．Gabay and B．Mercier，“A dual algorithm for the solution of nonlinear variational problems via finite element approximations．”Computer and Mathematics with Applications 1976，2：17—40． [7]B．S．He，L．z．Liao and H．Yang，“A decomposition method for a class of monotone variational inequality problems．”JOTA，1999，103(3)：603—622． [8]B．S．He，L．Z．Liao，D．R．Han and H．yang，A new inexact alternating directions method for monotone variational inequahties，Mathematical Programming，2002，6：1． 万方数据 · 5 ·
    [9Is．L．Wang and L．一Z．Liao，“Decomposition method with a variable parameter for a class of monotone variational inequality problems．”JOTA 2000，106：349—368． [10]D．P．Bermekas and J．N．Tsitsiklis，ParaUed and Distributed Computation：Numerical methods，Prentice—Hall Englewood Cliffs，NJ，1989． [11]Kontogiorgis，S．and Meyer，R．R，A variable—penaky alternating directions method for convex optimization， MathmaticaI Programming 1998，83：29—53． [12]Tseng，P．，Alternating projection—proximal methods for convex programming and variational inequilties， SIAM J．Optimization 7，951—965． [13]B．S．He and Yang Hai，Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities operations Research Letters，1998，23：151—161． A Proximal Augmented Lagrange Method for Monotone Varational Inequailities WANG Zhi—hua (Shazhou Polytechnical Institute of Technology) Abstract：This paper addresses a new augmented Lagrange method(AL)for mono— tone variational inequality(VI)，which needs only to solve one stongly monotone sub —VI problem．The paramaters are allowed to vary from iteration to iteration．Its con． vergence of the method is proved under mild assumptions． Key words：Monotone variational inequalities；Proximal point method；Augmented Lagrange method ·6 · 万方数据
    关于单调变分不等式的一种邻近增广拉格朗日方法 作者： 王治华， WANG Zhi-hua 作者单位： 刊名： 沙洲职业工学院,张家港,215600 沙洲职业工学院学报 英文刊名： JOURNAL OF SHAZHOU POLYTECHNICAL INSTITUTE OF TECHNOLOGY 2002,5(1) 年，卷(期)： 参考文献(13条) 1.Noor, m. A Some recent advances in variational inequalities, part Ⅰ: Basic concepts 1997 2.Dafermos, S An iterative scheme for variational inqualities 1983 3.Harker, P. T;Pang, J. S Finite - dimensional variational inequality and non0elinear complementarity problems, a survey of theory , algorithms and applications 1990 4.B. S. He A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programmingJ 1992 5.Gabay, D Application of the method of multipliers to variational inequalities 1983 6.D. Gabay;B. Mercier A dual algorithm for the solution of nonlinear variational problems via finite element approximations 1976 7.B. S. He;L.z. Liao;H. Yang A decomposition method for a class of monotone variational inequality problems[外文期刊] 1999(03) 8.B. S. He;L. Z. Liao;D. R. Han;H. Yang A new inexact alternating directions method for monotone variational inequalities[外文期刊] 2002 9.S. L. Wang;L. - Z. Liao Decomposition method with a variable parameter for a class of monotone variational inequality problems[外文期刊] 2000 10.D. P. Bertsekas;J. N. Tsitsiklis Paralled and Distributed Computation: Numerical methods 1989 11.Kontogiorgis, S;Meyer, R. R A variable - penalty alternating directions method for convex optimization[外文期刊] 1998(1) 12.Tseng, P Alternating projection- proximal methods for convex programming and variational inequilties[外文期刊] 13.B S He;Yang Hai Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities operations[外文期刊] 1998(3/5) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_szzygxyxb200201001.aspx
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料