The global linear convergence of a noninterior path-following algorithm for linear complementarity problems

被引:95
作者
Burke, JV [1 ]
Xu, S [1 ]
机构
[1] Univ Washington, Dept Math, Seattle, WA 98195 USA
关键词
linear complementarity problem; noninterior algorithm; path following algorithm; interior point algorithm; global linear convergence;
D O I
10.1287/moor.23.3.719
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
A noninterior path-following algorithm is proposed for the linear complementarity problem. The method employs smoothing techniques introduced by Kanzow. If the LCP is P-0 + R-0 and satisfies a nondegeneracy condition due to Fukushima, Luo, and Pang, then the algorithm is globally linearly convergent. As with interior point path-following methods, the convergence theory relies on the notion of a neighborhood for the central path. However, the choice of neighborhood differs significantly from that which appears in the interior point literature. Numerical experiments are presented that illustrate the significance of the neighborhood concept for this class of methods.
引用
收藏
页码:719 / 734
页数:16
相关论文
共 21 条
[1]  
[Anonymous], 1988, LINEAR NONLINEAR PRO
[2]  
CHEN B, 1997, GLOBAL LOCAL SUPER L
[3]  
CHEN B, 1997, GLOBAL LINEAR LOCAL
[4]  
CHEN B, 1997, 991644736 WASH STAT
[5]   A NON-INTERIOR-POINT CONTINUATION METHOD FOR LINEAR COMPLEMENTARITY-PROBLEMS [J].
CHEN, BT ;
HARKER, PT .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1993, 14 (04) :1168-1190
[6]   COMPUTATIONAL COMPLEXITY OF LCPS ASSOCIATED WITH POSITIVE DEFINITE SYMMETRIC MATRICES [J].
FATHI, Y .
MATHEMATICAL PROGRAMMING, 1979, 17 (03) :335-344
[7]  
FUKUSHIMA M, 1996, IN PRESS COMPUTATION
[8]  
Geiger C., 1996, Computational Optimization and Applications, V5, P155, DOI 10.1007/BF00249054
[9]  
Harker PT., 1990, Comput Solut Nonlinear Syst Equ, V26, P265
[10]  
HOTTA K, 1996, DISCUSSION PAPER SER, V708