To cite this record: http://ddd.uab.cat/record/161
Predictor-corrector algorithm for solving P_* (k)-matrix LCP from arbitrary positive starting points
Potra, Florian A.
Rongqin, Sheng

Date: 1997
Abstract: A new predictor-corrector 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 ; Interior-point algorithm ; Superlinear convergence
Published in: Mathematical Programming, vol. 76 n. 1 (1997) p. 223-244, ISSN 0025-5610



22 p, 782.7 KB
 UAB restricted access

The record appears in these collections:
Articles > Published articles

 Record created 2006-03-13, last modified 2014-06-14



   Favorit i Compartir
QR image