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

Goran Banjac (), Paul Goulart (), Bartolomeo Stellato () and Stephen Boyd ()
Additional contact information
Goran Banjac: ETH Zurich
Paul Goulart: University of Oxford
Bartolomeo Stellato: Massachusetts Institute of Technology
Stephen Boyd: Stanford University

Journal of Optimization Theory and Applications, 2019, vol. 183, issue 2, No 6, 490-519

Abstract: Abstract 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.

Keywords: Convex optimization; Infeasibility detection; Alternating direction method of multipliers; Conic programming; 90C06; 90C20; 90C22; 90C25; 68Q25 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-019-01575-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:183:y:2019:i:2:d:10.1007_s10957-019-01575-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-019-01575-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().