An Infeasible-Interior-Point Method for Linear Complementarity Problems (Q4377574)

For the linear complementarity problem (LCP) of the form: determine a vector pair \((x,z)\) satisfying \(Mx-c=z\), \(x^{T}z= 0\), \((x,z) \leq {\mathbf 0}\), where \(x,z,c \in {\mathbb{R}}^{n}\) and \(M \in {\mathbb{R}}^{n}\times {\mathbb{R}}^{n}\), the authors propose an infeasible-interior-point algorithm based on a method being a modification of a method for general nonlinear programming problems, developed by \textit{A. S. El-Bakry, R. A. Tapia, T. Tsuchiya} and \textit{Zhang} [J. Optimization Theory Appl. 89, No. 3, 507-541 (1996; Zbl 0851.90115)]. The source problem can be reformulated (applying the logarithmic-barrier method) as the minimization problem \[ x^{T}z-\mu \sum \log (x_{i}) - \mu \sum \log (z_{i})=\min ! \] subject to \(Mx-c=z\), \((x,z) \leq {\mathbf 0}\). The first-order conditions for the Lagrange form of this problem may be reduced to the system \(Mx-z-c={\mathbf 0}\), \(XZe=\mu e\), where \(X=\)diag \((x_{i})\), \(Z=\)diag \((z_{i})\) and \(e\) is the vector \((1,1,\ldots,1)\), assuming nonsingularity of the matrix \(XM^{T}+Z\). The algorithm moves from the current estimate \(v^{k}=(x^{k},z^{k})\) of the source problem solution to a new its estimate \(v^{k+1}\) by \[ x^{k+1}=x^{k}+\alpha_{k} \Delta x^{k},\qquad z^{k+1}=z^{k}+\alpha_{k} \Delta z^{k}, \] for \(k=0,1,2,\ldots\), where \((x^{0},z^{0})\) is a strictly positive starting point and \[ \Delta x^{k} = (X^{k}M+Z^{k})^{-1}(X^{k}c-X^{k}Mx^{k} + \mu_{k}e), \] \[ \Delta z^{k}= M\Delta x^{k} +Mx^{k} - z^{k} - c, \] seeking to minimize the merit function \[ \phi (v) = (\| XZe\| ^{2} + \| Mx - z - c\| ^{2})^{\frac{1}{2}}, \] and terminates when \(\phi (x,z) \leq \varepsilon\) for some predetermined \(\varepsilon\). The selection of \(\mu_{k}\) and \(\alpha_{k}\) is also described in such a way that \(v^{k+1}>0\) is guaranteed during all iteration steps. The authors give the proof of the global convergence of the algorithm under minor assumptions and present some numerical results demonstrating its very good computational performance on large-scale LCP's.