Optimization Online


An efficient matrix splitting method for the second-order cone complementarity problem

Zhang Leihong (longzlh***at***gmail.com)
Yang Weihong (whyang***at***fudan.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/2012
Entry Accepted: 05/16/2012
Entry Last Modified: 04/10/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society