ISSN:
1572-9338
Keywords:
Linear complementarity problems
;
predictor-corrector
;
infeasible-interior-point algorithm
;
polynomiality
;
superlinear convergence
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract The Mizuno-Todd-Ye predictor-corrector algorithm for linear programming is extended for solving monotone linear complementarity problems from infeasible starting points. The proposed algorithm requires two matrix factorizations and at most three backsolves per iteration. Its computational complexity depends on the quality of the starting point. If the starting points are large enough, then the algorithm hasO(nL) iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has $$O(\sqrt {nL} )$$ iteration complexity. At each iteration, both “feasibility” and “optimality” are reduced exactly at the same rate. The algorithm is quadratically convergent for problems having a strictly complementary solution, and therefore its asymptotic efficiency index is $$\sqrt 2$$ . A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02206812
Permalink
