A new search direction of IPM for horizontal linear complementarity problems

This study presents a new search direction for the horizontal linear complementarity problem. A vector-valued function is applied to the system of xy=μe
, which defines the central path. Usually, the way to get the equivalent form of the central path is using the square root function. However, in our study, we substitute a new search function formed by a different identity map, which obtains the equivalent shape of the central path using the square root function. We get the new search directions from Newton’s Method. Given this framework, we prove polynomial complexity for the Newton directions. We show that the algorithm’s complexity is O(n−−√lognϵ)
, which is the same as the best-given algorithms for the horizontal linear complementarity problem.