线性互补问题罚函数方法的收敛性分析

《线性互补问题罚函数方法的收敛性分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２１卷第５期运筹与管理Ｖｏｌ．２１，Ｎｏ．５２０１２年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１２线性互补问题罚函数方法的收敛性分析李园，　杨丹丹，　韩海山（内蒙古民族大学数学学院，内蒙古通辽０２８０４３）摘要：线性互补问题ＬＣＰ（A，b）无论是解的存在性、唯一性，还是算法的收敛性，都与矩阵A的结构有着密切关系．本文采用文［４］所构造的罚函数方法，在一定假设条件下证明了当ＬＣＰ（A，b）的矩阵A是P-矩阵时线性互补问题相应的罚方程的解收敛到原线性互补问题的解，且收敛速率也可以达到指数次，推广了文献［４］

2、中的结果。关键词：运筹学；线性互补问题；罚函数方法；P-矩阵；收敛速率；推广中图分类号：Ｏ２２１．２　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１２）０５-０１２９-０６ConvergenceAnalysisofPowerPenaltyMethodforLinearComplementarityproblemsＬＩＹｕａｎ，ＹＡＮＧＤａｎ-ｄａｎ，ＨＡＮＨａｉ-ｓｈａｎ（CollegeofMathematics，InnerMongoliaUniversityforNationalities，Tongliao０２８０４３，China）Abstract

3、：Ｂｏｔｈｔｈｅｅｘｉｓｔｅｎｃｅ，ｕｎｉｑｕｅｎｅｓｓｏｆｔｈｅｓｏｌｕｔｉｏｎａｎｄｔｈｅｃｏｎｖｅｒｇｅｎｃｅｏｆａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅａｒｃｏｍｐｌｅｍｅｎ-ｔａｒｉｔｙｐｒｏｂｌｅｍＬＣＰ（A，b）ｄｅｐｅｎｄｏｎｔｈｅｓｔｒｕｃｔｕｒｅｏｆｍａｔｒｉｘA．Ｕｎｄｅｒｓｏｍｅａｓｓｕｍｐｔｉｏｎｓ，ｔｈｉｓｐａｐｅｒｕｓｉｎｇｔｈｅｐｅｎａｌｉｚｅｄｅｑｕａｔｉｏｎｃｏｎｓｔｒｕｃｔｅｄｉｎ［４］ｐｒｏｖｅｓｔｈｅｓｏｌｕｔｉｏｎｔｏｔｈｅｐｅｎａｌｔｙｅｑｕａｔｉｏｎｃｏｎｖｅｒｇｅｓｔｏｔｈａｔｏｆｔｈｅＬＣＰｗｉｔｈAｉｓａP-ｍ

4、ａｔｒｉｘｗｈｅｎｔｈｅｐｅｎａｌｔｙｐａｒａｍｅｔｅｒａｐｐｒｏａｃｈｅｓｔｏｉｎｆｉｎｉｔｙ，ａｎｄｔｈｅｃｏｎｖｅｒｇｅｎｃｅｒａｔｅｉｓａｌｓｏｅｘｐｏｎｅｎｔｉａｌ．Ｇｅｎｅｒａｌｉｚｅｔｈｅｃｏｎｃｌｕｓｉｏｎｉｎ［４］．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ；ｌｉｎｅａｒｃｏｍｐｌｅｍｅｎｔａｒｉｔｙｐｒｏｂｌｅｍ；ｐｅｎａｌｔｙｍｅｔｈｏｄ；P-ｍａｔｒｉｘ；ｃｏｎｖｅｒｇｅｎｃｅｒａｔｅ；ｇｅｎｅｒａｌｉｚａｔｉｏｎ０　引言线性互补问题是运筹学与计算数学的一个交叉研究领域，已经广泛应用于力学、交通、经济、金融、控制等领域中出

5、现的许多数学模型，例如障碍和自由边界问题、供应链问题、交通分配问题、经济均衡问题、非均衡博弈论等，这使得线性互补问题成为数学规划中的一个十分热门的研究课题．许多学者对线性互补问题的［１，２］求解进行了深入的研究，提出了许多算法，例如：投影法、光滑牛顿法、非光滑牛顿法、松弛法、内点法、非光滑方程法等．进一步掌握和研究互补问题的各类算法，不仅具有理论意义，而且具有实际意义。本文考虑如下线性互补问题（简记作ＬＣＰ（A，b））：n求x＝（x１，x２，⋯，xn）∈R，使得Ax－b≤０（１）x≤０T（Ax－b）x＝０收稿日期：２０１１-０６-０１基金项目：内蒙古自然科学

6、基金资助项目（２０１１ＭＳ０１１４）作者简介：李园（１９８５-），男，内蒙古通辽市人，助教，研究方向：变分不等式与互补问题。１３０运筹与管理　　　　　　　　　　　２０１２年第２１卷n×nn其中A∈R，b∈R。n令K＝｛y∈R｜y≤０｝，则求解问题（１）等价于求解如下变分不等式问题：求x∈K，使得对任意的y∈K，满足TT（y－x）Ax≥（y－x）b（２）文［４］构造了如下关于问题（１）的罚函数方法：n求xλ∈R，满足１Axkλ＋λ［xλ］＋＝b（３）naaaa其中λ＞１，k＞１是参数，［u］＋＝ｍａｘ｛u，０｝．并且对任意的y＝（y１，y２，⋯，yn）∈R，有

7、y＝（y１，y２，⋯，yn）．文［３］讨论了Ｈｉｌｂｅｒｔ空间中椭圆型变分不等式形如（３）式的罚函数法，在适当的假设条件下证明了罚函n数方法的收敛性以及作为Ｈｉｌｂｅｒｔ空间的特例，R（n有限）空间中变分不等式（２）在矩阵A对称正定的情况下形如（３）式的罚函数法（当k＝１时）的收敛性问题．文［４］在矩阵A正定，A的主对角线元素大于零，其余元素均小于等于零的假设条件下，证明了随着惩罚因子λ→∞时罚方程（３）的解收敛到问题（１）的解，且收敛速－率是指数次的．本文将文［４］中矩阵A的正定条件放宽，证明了当A是P矩阵时的相应结论。１　主要结果本文对矩阵A作如下假设：

8、n×n－Ａ１：A∈R是严格行对角占优的P矩阵；a１１