  


An efficient matrix splitting method for the secondorder cone complementarity problem
Zhang Leihong (longzlhgmail.com) 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 secondorder 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, 408425 (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 overrelaxation (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 stateoftheart methods on problems with dense, illconditioned 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: Secondorder 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 (SecondOrder Cone Programming ) Category 3: Optimization Software and Modeling Systems (Other ) Citation: SIAM Journal on Optimization, to appear. Download: [PDF] Entry Submitted: 05/16/2012 Modify/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  