Abstract

 It is well known that, for a linear program (LP) with constraint matrix A  , the Alternating Direction Method of Multiplier converges globally and linearly at a rate . However, such a rate is related to the problem dimension and the algorithm exhibits a slow and fluctuating “tail convergence” in practice. In this paper, we propose a new variable splitting method of LP and prove that our method has a convergence rate of . The proof is based on simultaneously estimating the distance from a pair of primal dual iterates to the optimal primal and dual solution set by certain residuals. In practice, we result in a new first-order LP solver that can exploit both the sparsity and the specific structure of matrix A and a significant speedup for important problems such as basis pursuit, inverse covariance matrix estimation, L1 SVM and nonnegative matrix factorization problem compared with the current fastest LP solvers.