Beibei Yuan, Mingwang Zhang, Zhengwei Huang, A wide neighborhood primal-dual interior-point algorithm with arc-search for linear complementarity problems, Vol. 2018 (2018), Article ID 31, pp. 1-14

Full Text: PDF
DOI: 10.23952/jnfa.2018.31

Received January 16, 2018; Accepted August 11, 2018; Published September 17, 2018

Abstract. In this paper, ellipsoidal estimations are used to track the central path of a linear complementarity problem (LCP). A wide neighborhood primal-dual interior-point algorithm is devised to search an $\varepsilon$ -approximate solution of the LCP along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n\log\frac{(x^0)^{T}s^0}{\varepsilon})$ , which is as good as the linear programming analogue. The numerical results show that the proposed algorithm is efficient and reliable.

How to Cite this Article:
Beibei Yuan, Mingwang Zhang, Zhengwei Huang, A wide neighborhood primal-dual interior-point algorithm with arc-search for linear complementarity problems, Journal of Nonlinear Functional Analysis, Vol. 2018 (2018), Article ID 31, pp. 1-14.