TY - GEN
T1 - Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex Optimization
AU - Banjac, Goran
AU - Goulart, Paul
AU - Stellato, Bartolomeo
AU - Boyd, Stephen
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/31
Y1 - 2018/10/31
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85056903374&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056903374&partnerID=8YFLogxK
U2 - 10.1109/CONTROL.2018.8516858
DO - 10.1109/CONTROL.2018.8516858
M3 - Conference contribution
AN - SCOPUS:85056903374
T3 - 2018 UKACC 12th International Conference on Control, CONTROL 2018
SP - 340
BT - 2018 UKACC 12th International Conference on Control, CONTROL 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - UKACC 12th International Conference on Control, CONTROL 2018
Y2 - 5 September 2018 through 7 September 2018
ER -