一个求解P_*(κ)水平线性互补问题精确极大互补解的不可行内点算法(英文)  

An Infeasible IPM for an Exact Maximally Complementary Solution to the P_*(κ) Horizontal LCP

作　　者：王哲民[1] 黄正海[2] 唐文杰[1] 

机构地区：[1]复旦大学统计运筹系,上海200433 [2]中国科学院数学与系统科学研究院应用数学研究所,北京100080

出　　处：《运筹学学报》2001年第2期57-59,共3页Operations Research Transactions

基　　金：This project is supported by the National Nature Science Foundation of China (Grant No. 198710l6).

摘　　要：Stoer,Wechs,和Mizuno最近提出了一个求解P_*(k)水平线性互补问题的不可行内点算法，他们的算法能在有限不内得到问题的一个精确解，但是没有讨论算法的多项式复杂性．本文提出一个能得到P_*(k)水平线性互补问题精确极大互补解的不可行内点算法，通过使用条件数和误差界理论，我们证明了所给算法是多项式有界的．For the P_*(κ) horizontal linear complementarity problem (LCP),Stoer,Wechs,and Mizuno presented recently an infeasible interior point method (IPM) that is capable of obtaining an exact solution in finite iterations,but they gave no discussion of polynomial complexity.In this paper we provide an infeasible IPM for obtaining an exact maximally complementary solution to the P_*(κ) horizontal LCP. Using condition numbers and error bound theory, we show that the algorithm is polynomial bounded.

关 键 词：P＊(k)水平线性互补问题 不可行内点算法 精确极大互补解 条件数 误差界理论 多项式有界 多项式复杂性 

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