Abstract:

In this paper, we present a path-following infeasible interior-point method for P∗(κ) horizontal linear complementarity problems (P∗(κ)-HLCPs). The algorithm is based on a simple kernel function for finding the search directions and defining the neighborhood of the central path. The algorithm follows the central path related to some perturbations of the original problem, using the so-called feasibility and centering steps, along with only full such steps. Therefore, it has the advantage that the calculation of the step sizes at each iteration is avoided. The complexity result shows that the full-Newton step infeasible interior-point algorithm based on the simple kernel function enjoys the best-known iteration complexity for P∗(κ)-HLCPs.

Key words: Horizontal linear complementarity problem, Infeasible interior-point method, Central path, Kernel function