guest ::
login


Search  Submit  Help  Servei de Biblioteques  Sobre el DDD  Català English Español 
Home > Articles > Published articles > Predictorcorrector algorithm for solving P_* (k)matrix LCP from arbitrary positive starting points 
Date:  1997 
Abstract:  A new predictorcorrector algorithm is proposed for solving P_*(k)matrix linear complementarity problems. If the problem is solvable, then the algorithm converges from an arbitrary positive starting point (x^0, s^0). The computational complexity of the algorithm depends on the quality of the starting point. If the starting point is feasible or close to being feasible, it has O((1 + k) V~n/(rho)_0L)iteration complexity, where (rho)_0 is the ratio of the smallest and average coordinate of X^0s^0. With appropriate initialization, a modified version of the algorithm terminates in O((1 + k)^2 (n/(rho)_0)L) steps either by finding a solution or by determining that the problem has no solution in a predetermined, arbitrarily large, region. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also propose an extension of a recent algorithm of Mizuno to P_* (k)matrix linear complementarity problems such that it can start from arbitrary positive points and has superlinear convergence without a strictly complementary condition. . 
Language:  Anglès. 
Document:  Article ; recerca ; article ; publishedVersion 
Subject:  Linear complementarity problems ; P_*matrices ; Interiorpoint algorithm ; Superlinear convergence 
Published in:  Mathematical Programming, vol. 76 n. 1 (1997) p. 223244, ISSN 00255610 
22 p, 782.7 KB UAB restricted access 
The record appears in these collections:
Articles > Published articles