Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex Optimization

G. Banjac, P. J. Goulart, B. Stellato and S. Boyd

June 2017.
BibTeX  Preprint 

@article{BGSB:2017,
  author = {G. Banjac and P. J. Goulart and B. Stellato and S. Boyd},
  title = {Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex Optimization},
  year = {2017}
}

The alternating direction method of multipliers (ADMM) is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the iterates generated by ADMM converge to a solution provided that it exists. If a solution does not exist, then the ADMM iterates do not converge. Nevertheless, we show that the ADMM iterates yield conclusive information regarding problem infeasibility for a wide class of convex optimization problems including both quadratic and conic programs. In particular, we show that in the limit the ADMM iterates either satisfy a set of first-order optimality conditions or produce a certificate of either primal or dual infeasibility. Based on these results, we propose termination criteria for detecting primal and dual infeasibility in ADMM.