P_*(κ)线性互补问题的预估-校正内点算法  

A Predictor-Corrector Interior-Point Algorithm for P_*(κ)-Linear Complementarity Problems

作　　者：刘新泽[1,2] 刘红卫[1] 刘长河[3] 

机构地区：[1]西安电子科技大学数学系,西安710071 [2]临沧高等师范专科学校数理系,云南临沧677000 [3]河南科技大学数学与统计学院,河南洛阳471003

出　　处：《吉林大学学报（理学版）》2013年第5期789-794,共6页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:61072144);中央高校基本科研业务费专项基金(批准号:K50513100007)

摘　　要：通过修正大邻域跟踪算法的搜索方向,提出一种新的求解P*(κ)线性互补问题(LCP)的不可行预估-校正内点算法,并对算法进行了收敛性分析,证明了该算法具有目前最好的理论复杂度O((1+κ)5/2nL).数值结果验证了算法的有效性.Based on modifying the search direction of neighborhood-following interior-point algorithm for linear programming, a new infeasible predictor-corrector interior-point algorithm for P＊（κ）-linear complementarity problem （LCP） was presented. The facts that P＊（κ）-LCP is nonmonotone and the corresponding search directions is non-orthogonal make the convergence analysis of the presented algorithm more complex. We have obtained the best known iteration complexity bound of the proposed algorithm so far, i.e. , O（（1＋κ）5/2nL）, where κ is the handicap of the problem. Numerical results show that the algorithm is feasible.

关 键 词：线性互补问题 内点算法 预估-校正算法 多项式复杂度 

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