一个求解水平线性互补问题的高阶可行内点算法的多项式复杂性  

POLYNOMIALITY OF A HIGH-ORDER FEASIBLE INTERIOR POINT METHOD FOR SOLVING THE HORIZONTAL LINEAR COMPLEMENTARITY PROBLEMS

作　　者：黄正海[1] 

机构地区：[1]复旦大学统计运筹系,上海200433

出　　处：《系统科学与数学》2000年第4期432-438,共7页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金!(No: 19871016)

摘　　要：最近，Ｚｈａｏ和Ｓｕｎ提出了一个求解ｓｕｆｆｉｃｉｅｎｔ线性互补问题的高阶不可行内点算 法．不需要严格互补解条件，他们的算法获得了高阶局部收敛率，但他们的文章没有报告 多项式复杂性结果．本文我们考虑他们所给算法的一个简化版本，即考虑求解单调水平线 性互补问题的一个高阶可行内点算法．我们证明了算法的迭代复杂性是Ｏ（ｌｏｇ（））．Recently, Zhao and Sun presented a high-order infeasible interior point method (IPM) for solving the sufficient linear complementarity problem (LCP) which possesses highorder convergent rate when the LCP has no strictly complementary solution. But no polynomiality result was reported in their paper. In this paper, we consider a simple version of their algorithm, i.e., a high-order feasible IPM for solving the monotone horizontal linear complementarity problem. We prove that the iteration complexity of the method is of O().

关 键 词：高阶内点算法 单调水平线性互补问题 多项式复杂性 

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