线性互补问题的邻域跟踪算法  

Neighborhood-following Algorithms for Monotone LCP

作　　者：刘长河[1,2] 

机构地区：[1]河南科技大学数学与统计学院,河南洛阳471003 [2]西安电子科技大学理学院,西安710071

出　　处：《四川理工学院学报（自然科学版）》2010年第2期140-143,共4页Journal of Sichuan University of Science & Engineering(Natural Science Edition)

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

摘　　要：文章把艾文宝的邻域跟踪算法推广到单调线性互补问题(LCP),由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析变得复杂。证明了算法的迭代复杂性为O(nL),并且通过证明对偶间隙的单调性,使得算法易于执行。This paper extends Ai＇s neighborhood-following algorithms for linear programming to monotone linear comple- mentarity problems （LCP）. Since monotone LCP is the generalization of linear programming, the analysis is more difficult than the one in the linear programming case. The O（√nL） iteration complexity is given. After proving the monotone property of the dual-gap, the proposed algorithm can be specified into easy implementable variants with given parameters.

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

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