  The alternating direction method of multipliers (ADMM) has been applied
successfully in a broad spectrum of areas. Moreover, it was shown in the
literature that ADMM is closely related to the Douglas-Rachford
operator-splitting method, and can be viewed as a special case of the proximal
point algorithm (PPA). As is well known, the relaxed version of PPA not only
maintains the convergence properties of PPA in theory, but also numerically
outperforms the original PPA. Therefore, it is interesting to ask whether ADMM
can be accelerated by using the over-relaxation technique. In this paper, we
answer this question affirmatively by developing an over-relaxed ADMM
integrated with a criterion to decide whether a relaxation step is implemented
in the iteration. The global convergence and $O(1/t)$ convergence rate of the
over-relaxed ADMM are established. We also implement our proposed algorithm to
solve Lasso and sparse inverse covariance selection problems, and compare its
performance with the relaxed customized ADMM in \cite{CGHY} and the classical
ADMM.
  The results show that our algorithm substantially outperforms the other two
methods.
