Superlinearly convergent infeasible-interior-point algorithm for degenerate LCP

作     者：Potra, FA Sheng, R 

作者机构：Univ Iowa Dept Math Iowa City IA 52242 USA 

出 版 物：《JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS》 (优选法理论与应用杂志)

年 卷 期：1998年第97卷第2期

页      面：249-269页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Science Foundation  NSF  (DMS 9305760) 

主　　题：linear complementarity problems sufficient matrices P*-matrices path-following algorithm infeasible-interior-point algorithm polynomiality superlinear convergence 

摘      要：A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically only two) backsolves. It has been recently proved that any sufficient matrix is a P*(kappa)-matrix for some kappa greater than or equal to 0. The computational complexity of the algorithm depends on kappa as well as on a feasibility measure of the starting point. If the starting point is feasible or close to being feasible, then the iteration complexity is O((1 + kappa)root nL). Otherwise, for arbitrary positive and large enough starting points, the iteration complexity is O((1 + kappa)(2)nL). We note that, while computational complexity depends on kappa, the algorithm itself does not.