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

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

Proceedings of Control 2018, Sheffield, June 2018.

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 diverge. Nevertheless, we show that the ADMM iterates yield conclusive information regarding problem infeasibility for optimization problems with linear or quadratic objective functions and conic constraints, which includes quadratic, second-order cone and semidefinite 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.