Identification of the optimal active set in a noninterior continuation method for LCP (Q1422880)

The authors investigate convergence properties of a modification of the non-interior point method continuation method suggested by \textit{J. Burke} and \textit{S. Xu} [J. Optimization Theory. Appl. 112, 53--76 (2002; Zbl 1049.90097)] for the standard linear complementarity problem. It is shown that the method determines the optimal active set of this problem in a finite number of iterations if the basic matrix is \(P\) and the problem is not degenerate. Namely, the method requires \(O( \rho \log (\beta_{0} \mu_{0} / \tau))\) iterations, where \(\beta_{0}\) is the width of the initial neighborhood, \(\mu_{0}\) is the initial smoothing parameter, and the constants \(\rho\) and \(\tau\) depend on the properties of the problem.