A path-following interior-point algorithm for monotone LCP based on a modified Newton search direction

Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences, University Ferhat Abbas Sétif 1, Sétif 19000, Algeria

^* Corresponding author: welid.gimes@univ-setif.dz

Received: 23 February 2022
Accepted: 10 April 2023

Abstract

In this paper, we propose a short-step feasible full-Newton step path-following interior-point algorithm (IPA) for monotone linear complementarity problems (LCPs). The proposed IPA uses the technique of algebraic equivalent transformation (AET) induced by an univariate function to transform the centering equations which defines the central-path. By applying Newton’s method to the modified system of the central-path of LCP, a new Newton search direction is obtained. Under new appropriate defaults of the threshold τ which defines the size of the neighborhood of the central-path and of θ which determines the decrease in the barrier parameter, we prove that the IPA is well-defined and converges locally quadratically to a solution of the monotone LCPs. Moreover, we derive its iteration bound, namely, O(√nlog n\ϵ) which coincides with the best-known iteration bound for such algorithms. Finally, some numerical results are presented to show its efficiency.