Optimization Online


Infeasibility detection in the alternating direction method of multipliers for convex optimization

Goran Banjac (goran.banjac***at***eng.ox.ac.uk)
Paul Goulart (paul.goulart***at***eng.ox.ac.uk)
Bartolomeo Stellato (bartolomeo.stellato***at***eng.ox.ac.uk)
Stephen Boyd (boyd***at***stanford.edu)

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

Keywords: convex optimization, alternating direction method of multipliers, infeasibility detection, conic programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 06/02/2017
Entry Accepted: 06/02/2017
Entry Last Modified: 06/05/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society