ISSN:
1573-2878
Keywords:
Linear complementarity problems
;
predictor-corrector method
;
interior-point algorithms
;
polynomiality
;
superlinear convergence
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We extend the Mizuno-Todd-Ye predictor-corrector algorithm for solving monotone linear complementarity problems. We prove that the extended algorithm is globally Q-linearly convergent and solves problems with integer data of bitlengthL in at most $$O(\sqrt n L)$$ iterations. We also prove that the duality gap converges to zero Q-superlinearly for problems having strictly complementary solutions. Our results generalize the results obtained by Ye, Tapia, and Zhang for linear programming.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02192304
Permalink