An Efficient Matrix Splitting Method for the Second-Order Cone Complementarity Problem
An Efficient Matrix Splitting Method for the Second-Order Cone Complementarity Problem
复制标题
DOI：
10.1137/13090938x
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Lei-Hong Zhang;W. Yang
中科院分区：
文献类型：
--
作者：
Lei-Hong Zhang;W. Yang
给定一个对称的正（半）定的n × n矩阵M和一个向量，本文考虑用矩阵分裂法求解二阶锥线性互补问题（SOCLCP）.矩阵分裂方法是求解大规模稀疏经典线性互补问题的最广泛使用的方法之一，其线性收敛性由[Luo和Tseng，SIAM J. Control Optim.，30（1992），pp. 408- 425]。我们的第一个贡献是证明，当一般的矩阵分裂算法应用于SOCLCP $M$对称和正定，它也至少线性收敛。数值上，我们的第二个贡献是提出了一个特殊的和有效的矩阵分裂算法，块逐次超松弛方法，解决SOCLCP。该算法充分利用了SOCLCP的基本几何结构，每次迭代只涉及求解三角线性方程组，需要O（n^2）$次触发器;此外，该算法不破坏迭代过程。
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, and its linear convergence is proved by [Luo and Tseng, SIAM J. Control Optim., 30 (1992), pp. 408--425]. 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 method, for solving the SOCLCP. The algorithm makes good use of the underlying geometry of the SOCLCP and each iteration only involves solving triangular linear systems and requires $O(n^2)$ flops; moreover, the algorithm does not destroy ...