A QUADRATICALLY CONVERGENT O((KAPPA+1)ROOT-N L)-ITERATION ALGORITHM FOR THE P-ASTERISK(KAPPA)-MATRIX LINEAR COMPLEMENTARITY-PROBLEM

被引：49
作者：
MIAO, JM
机构：
[1] RUTCOR - Rutgers Center for Operations Research, Rutgers University, New Brunswick, 08903-5062, NJ
来源：
MATHEMATICAL PROGRAMMING | 1995年 / 69卷 / 03期
关键词：
LINEAR COMPLEMENTARITY PROBLEM; INTERIOR-POINT ALGORITHM; QUADRATIC CONVERGENCE; POLYNOMIAL-TIME ALGORITHM;
D O I：
10.1007/BF01585565
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
An interior-point predictor-corrector algorithm for the P*(kappa)-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno-Todd-Ye's predictor-corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity O((kappa + 1)root nL). It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.
引用
收藏
页码：355 / 368
页数：14
相关论文
共 18 条
[1]  
Cottle R. W., 1992, LINEAR COMPLEMENTARI
[2]   A POLYNOMIAL-TIME PREDICTOR-CORRECTOR ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY PROBLEMS [J].
Ding, Jiu ;
Li, Tien-Yien .
SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (01) :83-92
[3]   ON APPROXIMATE SOLUTIONS OF SYSTEMS OF LINEAR INEQUALITIES [J].
HOFFMAN, AJ .
JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1952, 49 (04) :263-265
[4]  
JI J, 1991, 18 U IOW DEP MATH TE
[5]   AN INTERIOR POINT POTENTIAL REDUCTION ALGORITHM FOR THE LINEAR COMPLEMENTARITY-PROBLEM [J].
KOJIMA, M ;
MEGIDDO, N ;
YE, YY .
MATHEMATICAL PROGRAMMING, 1992, 54 (03) :267-279
[6]   AN O(SQUARE-ROOT-N L) ITERATION POTENTIAL REDUCTION ALGORITHM FOR LINEAR COMPLEMENTARITY-PROBLEMS [J].
KOJIMA, M ;
MIZUNO, S ;
YOSHISE, A .
MATHEMATICAL PROGRAMMING, 1991, 50 (03) :331-342
[7]   A POLYNOMIAL-TIME ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS [J].
KOJIMA, M ;
MIZUNO, S ;
YOSHISE, A .
MATHEMATICAL PROGRAMMING, 1989, 44 (01) :1-26
[8]  
KOJIMA M, 1991, LECTURE NOTES COMPUT, V538
[9]   A NEW POLYNOMIAL-TIME METHOD FOR A LINEAR COMPLEMENTARITY-PROBLEM [J].
MIZUNO, S .
MATHEMATICAL PROGRAMMING, 1992, 56 (01) :31-43
[10]  
MIZUNO S, 1992, MATH OPER RES, V18, P964
12