Journal of Applied Mathematics
Volume 2011 (2011), Article ID 340192, 12 pages
http://dx.doi.org/10.1155/2011/340192
Research Article

An Improved Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems with √ 𝑂 ( 𝑛 𝐿 ) -Iteration Complexity

Debin Fang1 and Qian Yu2

1School of Economics and Management, Wuhan University, Wuhan 430072, China
2School of Economics, Wuhan University of Technology, Wuhan 430070, China

Received 18 September 2011; Revised 23 November 2011; Accepted 24 November 2011

Academic Editor: Chong Lin

Copyright © 2011 Debin Fang and Qian Yu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

This paper proposes an improved predictor-corrector interior-point algorithm for the linear complementarity problem (LCP) based on the Mizuno-Todd-Ye algorithm. The modified corrector steps in our algorithm cannot only draw the iteration point back to a narrower neighborhood of the center path but also reduce the duality gap. It implies that the improved algorithm can converge faster than the MTY algorithm. The iteration complexity of the improved algorithm is proved to obtain √ 𝑂 ( 𝑛 𝐿 ) which is similar to the classical Mizuno-Todd-Ye algorithm. Finally, the numerical experiments show that our algorithm improved the performance of the classical MTY algorithm.