  In this paper, we analyze the convergence of Alternating Direction Method of
Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and
bound constraints. The ADMM formulation alternates between an equality
constrained QP and a projection on the bounds. Under the assumptions of (i)
positive definiteness of the Hessian of the objective projected on the null
space of equality constraints (reduced Hessian), and (ii) linear independence
constraint qualification holding at the optimal solution, we derive an upper
bound on the rate of convergence to the solution at each iteration. In
particular, we provide an explicit characterization of the rate of convergence
in terms of: (a) the eigenvalues of the reduced Hessian, (b) the cosine of the
Friedrichs angle between the subspace spanned by equality constraints and the
subspace spanned by the gradients of the components that are active at the
solution and (c) the distance of the inactive components of solution from the
bounds. Using this analysis we show that if the QP is feasible, the iterates
converge at a Q-linear rate and prescribe an optimal setting for the ADMM
step-size parameter. For infeasible QPs, we show that the primal variables in
ADMM converge to minimizers of the Euclidean distance between the hyperplane
defined by the equality constraints and the convex set defined by the bounds.
The multipliers for the bound constraints are shown to diverge along the range
space of the equality constraints. Using this characterization, we also propose
a termination criterion for ADMM. Numerical examples are provided to illustrate
the theory through experiments.
