求解单调线性互补问题的邻域跟踪内点算法  

Neighborhood-following interior point algorithm for monotone linear complementarity problem

作　　者：刘长河[1,2] 丁艳风[3] 

机构地区：[1]河南科技大学数学与统计学院,河南洛阳471003 [2]西安电子科技大学理学院,陕西西安710071 [3]郑州大学升达经贸管理学院,河南郑州451191

出　　处：《陕西理工学院学报（自然科学版）》2010年第2期72-77,共6页Journal of Shananxi University of Technology:Natural Science Edition

基　　金：国家自然科学基金资助项目(60674108)

摘　　要：把艾文宝的邻域跟踪算法推广到单调线性互补问题(LCP),用2-范数代替1-范数来定义宽邻域。由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析比线性规划复杂。证明了算法的迭代复杂性为O(n～(1/2)L)。通过证明对偶间隙关于搜索步长的单调性,使得算法易于执行。数值实验显示了该算法的有效性。This paper extends Ai′ s neighborhood-following algorithms for linear programming to monotone linear complementarity problem（LCP）.Since monotone LCP is the generalization of linear programming,the orthogonality of vectors is lost.So the analysis is more difficult than the one in the linear programming case.The 1-norm is substituted by 2-norm in the definition of wide neighborhoods.Thus the analysis is different from Ai.The iteration complexity is given.After the monotone property of the dual-gap provided,the proposed algorithm can be specified into easy implementable variants with given parameters.At last,some numerical results are reported.

关 键 词：单调线性互补问题 内点方法 宽邻域 多项式复杂性 

分 类 号：O221[理学—运筹学与控制论]