TY - JOUR
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 - Funding Information:
We are grateful to Walaa Moursi for helpful comments and pointing out additional references. This work was supported by the People Programme (Marie Curie Actions) of the European Union Seventh Framework Programme (FP7/2007–2013) under REA Grant Agreement No. 607957 (TEMPO).
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2019/11/1
Y1 - 2019/11/1
N2 - The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they 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 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.
AB - The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they 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 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.
KW - Alternating direction method of multipliers
KW - Conic programming
KW - Convex optimization
KW - Infeasibility detection
UR - http://www.scopus.com/inward/record.url?scp=85071251396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071251396&partnerID=8YFLogxK
U2 - 10.1007/s10957-019-01575-y
DO - 10.1007/s10957-019-01575-y
M3 - Article
AN - SCOPUS:85071251396
VL - 183
SP - 490
EP - 519
JO - Journal of Optimization Theory and Applications
JF - Journal of Optimization Theory and Applications
SN - 0022-3239
IS - 2
ER -