- An efficient matrix splitting method for the second-order cone complementarity problem Zhang Leihong (longzlhgmail.com) Yang Weihong (whyangfudan.edu.cn) Abstract: Given a symmetric and positive (semi)definite $n$-by-$n$ matrix $M$ and a vector, in this paper, we consider the matrix splitting method for solving the second-order cone linear complementarity problem (SOCLCP). The matrix splitting method is among the most widely used approaches for large scale and sparse classical linear complementarity problems (LCP), and its linear convergence is proved by [Luo and Tseng, \textit{SIAM J. Control Optim.}, 30, 408-425 (1992)]. Our first contribution is to prove that, when the general matrix splitting algorithm is applied to SOCLCP with $M$ symmetric and positive definite, it also converges at least linearly. Numerically, our second contribution is to propose a special and efficient matrix splitting algorithm, the block successive over-relaxation (BSOR) method, for solving SOCLCP. The algorithm makes good use of the underlying geometry of SOCLCP and each iteration only involves solving triangular linear systems and requires $O(n^2)$ flops; moreover, the algorithm does not destroy the sparse structure of $M$ and is able to exploit the sparsity effectively. Our code \textsf{BSOR\_BN\_L} based on this method is tested against other four state-of-the-art methods on problems with dense, ill-conditioned symmetric and positive definite matrices, as well as on problems with large scale sparse, symmetric and positive (semi)definite matrices. The numerical results are quite encouraging and \textsf{BSOR\_BN\_L} exhibits a very good performance in terms of its speed, the accuracy and its efficiency in exploiting the sparsity of $M$. Keywords: Second-order cone, Linear complementarity problem, Matrix splitting method, Regular splitting, Successive overrelaxation (SOR), Linear convergence, Bisection iteration, Newton's iteration Category 1: Complementarity and Variational Inequalities Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming ) Category 3: Optimization Software and Modeling Systems (Other ) Citation: SIAM Journal on Optimization, to appear. Download: [PDF]Entry Submitted: 05/16/2012Entry Accepted: 05/16/2012Entry Last Modified: 04/10/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.