A Krylov Subspace Method for Large-Scale Second-Order Cone Linear Complementarity Problem
Lei-Hong Zhang, Wei Hong Yang, Chungen Shen, Ren‐Cang Li · SIAM Journal on Scientific Computing · 2015
In this paper, we first show that the second-order cone linear complementarity problem (SOCLCP) can be solved by finding a positive zero $s_*\in \mathbb{R}$ of a particular rational function $h(s)$, and we then propose a Krylov subspace method to reduce $h(s)$ to $h_{\ell}(s)$ as in the model reduction. The zero $s_*$ of $h(s)$ can be accurately approximated by that of $h_{\ell}(s)=0$, which itself can be cast as a small eigenvalue problem. The new method is made possible by a complete characterization of the curve of $h(s)$, and it has several advantages over the bisection-Newton (\sf BN) iteration recently proposed by [L.-H. Zhang and W. H. Yang, Math. Comp., 83 (2013), pp. 1701--1720] and shown to be very efficient for small- to medium-size problems. The method is tested and compared against the \sf BN iteration and two other state-of-the-art packages: \sf SDPT3 and \sf SeDuMi. Our numerical results show that the method is very efficient for both small to medium dense problems and large-scale ones.