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

Goran Banjac, Paul Goulart, Bartolomeo Stellato, Stephen Boyd

Research output: Contribution to journalArticle

4 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)490-519
Number of pages30
JournalJournal of Optimization Theory and Applications
Volume183
Issue number2
DOIs
StatePublished - Nov 1 2019

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Keywords

  • Alternating direction method of multipliers
  • Conic programming
  • Convex optimization
  • Infeasibility detection

Fingerprint Dive into the research topics of 'Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex Optimization'. Together they form a unique fingerprint.

  • Cite this