A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP

作     者：Achache, Mohamed Khebchache, Radia 

作者机构：Univ Ferhat Abbas Setif1 Lab Math Fondament & Numer Setif Algeria Univ Ferhat Abbas Setif1 Fac Sci Dept Math Setif Algeria 

出 版 物：《AFRIKA MATEMATIKA》 (Afr. Mat.)

年 卷 期：2015年第26卷第1-2期

页      面：139-151页

主　　题：Linear complementarity problems Interior point methods Short-step primal-dual algorithms Complexity of algorithms 

摘      要：In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step and the strategy of the central path to obtain an epsilon-approximate solution of LCP. This algorithm yields the best currently well-known theoretical complexity iteration bound, namely, O(root n log n/epsilon) which is as good as the bound for the linear optimization analogue. The implementation of the algorithm and the algorithm in Wang et al. (Fuzzy Inform Eng 54:479-487, 2009) is done followed by a comparison between these two obtained numerical results.