A full‐Newton step infeasible interior‐point algorithm for monotone LCP based on a locally‐kernel function

We propose a new full‐Newton step infeasible interior‐point algorithm for monotone linear complementarity problems based on a simple locally‐kernel function. The algorithm uses the simple locally‐kernel function to determine the search directions and define the neighborhood of central path. Two types of full‐Newton steps are used, feasibility step and centering step. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The procedure is repeated until an ϵ‐approximate solution is found. We analyze the algorithm and obtain the complexity bound, which coincides with the best‐known result for monotone linear complementarity problems.