Interior-point algorithms for \(P_{*}(\kappa )\)-LCP based on a new class of kernel functions
In this paper, we propose interior-point algorithms for \(P_* (\kappa )\)-linear complementarity problem based on a new class of kernel functions. New search directions and proximity measures are defined based on these functions. We show that if a strictly feasible starting point is available, then the new algorithm has \(\mathcal{O }\bigl ((1+2\kappa )\sqrt{n}\log n \log \frac{n\mu ^0}{\epsilon }\bigr )\) and \(\mathcal{O }\bigl ((1+2\kappa )\sqrt{n} \log \frac{n\mu ^0}{\epsilon }\bigr )\) iteration complexity for large- and small-update methods, respectively. These are the best known complexity results for such methods.
kernel function complexity interior-point method polynomial algorithm linear complementarity problem