Abstract:

We investigate the infeasibility detection in the alternating direction method of multipliers (ADMM) when minimizing a convex quadratic objective subject to linear equalities and simple bounds. The ADMM formulation consists of alternating between an equality constrained quadratic program (QP) and a projection onto the bounds. We show that: (i) the sequence of iterates generated by ADMM diverges, (ii) the divergence is restricted to the component of the multipliers along the range space of the constraints and (iii) the primal iterates converge to a minimizer of the Euclidean distance between the subspace defined by equality constraints and the convex set defined by bounds. In addition, we derive the optimal value for the step size parameter in the ADMM algorithm that maximizes the rate of convergence of the primal iterates and dual iterates along the null space. In fact, the optimal step size parameter for the infeasible instances is identical to that for the feasible instances. The theoretical results allow us to specify a practical termination condition for infeasibility and the performance of such criterion is demonstrated in a model predictive control application.