线性互补问题的Mehrotra型预估矫正算法  

Mehrotra predictor-corrector algorithm for linear complementarity problem

作　　者：常铮[1] 李敬华[1] 

机构地区：[1]西安电子科技大学数学系,陕西西安710071

出　　处：《纺织高校基础科学学报》2013年第4期498-501,共4页Basic Sciences Journal of Textile Universities

基　　金：国家自然科学基金资助项目(61072144);中央高校基本科研业务费专项资助项目(K50513100007)

摘　　要：以艾文宝的邻域跟踪算法为基础,增加了一个二阶矫正项,提出了单调线性互补问题的一个Mehrotra型预估矫正算法.由于单调线性互补问题的迭代方向不具有正交性,因此算法的理论分析变得复杂.通过分析,得到了目前线性互补问题最好的复杂度.In this paper,a second-order correction term is added based on Ai＇s neighborhood following al- gorithm, and an Mehrotra predictor-corrector algorithm for linear complementarity problem is presen- ted. Since LCP＇s iterative direction does not have orthogonality,the theoretical analysis of the algorithm is more difficult than the one in the linear programming. By deriving the complexity for the algorithm, the best-known result for linear complementarity problem is obtained.

关 键 词：单调线性互补问题 Mehrotra型预估矫正算法 宽邻域算法 多项式复杂性 

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