A full-Newton step feasible interior-point algorithm for <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$P_*(\kappa )$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mi>P</mi> <mo>∗</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">κ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math> ...

In this paper, a full-Newton step feasible interior-point algorithm is proposed for solving <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$P_*(\kappa )$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mi>P</mi> <mo>∗</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">κ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation>-linear complementarity problems. We prove that the full-Newton step to the central path is local quadratically convergent and the proposed algorithm has polynomial iteration complexity, namely, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$O\left( (1+4\kappa )\sqrt{n}\log {\frac{n}{\varepsilon }}\right) $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mfenced close=")" open="(" separators=""> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mn>4</mn> <mi mathvariant="italic">κ</mi> <mo stretchy="false">)</mo> </mrow> <msqrt> <mi>n</mi> </msqrt> <mo>log</mo> <mfrac> <mi>n</mi> <mi mathvariant="italic">ε</mi> </mfrac> </mfenced> </mrow> </math> </EquationSource> </InlineEquation>, which matches the currently best known iteration bound for <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$P_*(\kappa )$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mi>P</mi> <mo>∗</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">κ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation>-linear complementarity problems. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm. Copyright Springer Science+Business Media New York 2014