On Superlinear and Convergence of a Path-Following Algorithm for Monotone Linear Complementarity Problems in a Wide Neighborhood. (4th May 2017)

• Record Type: Journal Article
• Authors: Ma, Xiaojue; Liu, Hongwei; Zhang, Jianke; Cong, Weijie
• Is Part Of: Numerical functional analysis and optimization. Volume 38:Number 5(2017)
• Page Start: 627
• Page End: 640
• Publication Date: 2017-05-04
• Subjects: Monotone linear complementarity -- path-following -- primal-dual interior-point methods -- Superlinear -- wide neighborhoods; 90C33 -- 49M15 -- 65K15; Functional analysis -- Periodicals; Numerical analysis -- Periodicals; Mathematical optimization -- Periodicals; Numerical Analysis, Computer-Assisted; 515.705
• DOI: 10.1080/01630563.2017.1297824
• Languages: English
• ISSNs: 0163-0563

Abstract

ABSTRACT: We propose a modified path-following algorithm in a wide neighborhood for monotone linear complementarity problems. The algorithm takes two steps in one iteration, called a fast step and a safe step, respectively. In the algorithm, if a fast step fails, a safe step will be taken. However, when iterations are sufficiently large, fast steps are taken all through. We prove that the algorithm has not only the complexity bound but also local superlinear convergence. Furthermore, assuming a strictly complementary solution exists, the sequence, generated by the algorithm, is convergent. Finally, the numerical results show the algorithm effective.