Interior-point algorithms for <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$P_{*}(\kappa )$$</EquationSource> </InlineEquation>-LCP based on a new class of kernel functions

In this paper, we propose interior-point algorithms for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$P_* (\kappa )$$</EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$\mathcal{O }\bigl ((1+2\kappa )\sqrt{n}\log n \log \frac{n\mu ^0}{\epsilon }\bigr )$$</EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\mathcal{O }\bigl ((1+2\kappa )\sqrt{n} \log \frac{n\mu ^0}{\epsilon }\bigr )$$</EquationSource> </InlineEquation> iteration complexity for large- and small-update methods, respectively. These are the best known complexity results for such methods. Copyright Springer Science+Business Media New York 2014