Optimization Online


ADMM for Convex Quadratic Programs: Linear Convergence and Infeasibility Detection

Arvind U. Raghunathan (raghunathan***at***merl.com)
Stefano Di Cairano (dicairano***at***merl.com)

Abstract: In this paper, we analyze the convergence of Alternating Direction Method of Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and bound constraints. The ADMM formulation alternates between an equality constrained QP and a projection on the bounds. Under the assumptions of: (i) positive definiteness of the Hessian of the objective projected on the null space of equality constraints (reduced Hessian), and (ii) linear independence constraint qualification holding at the optimal solution we derive an upper bound on the rate of convergence to the solution at each iteration. In particular, we provide an explicit characterization of the rate of convergence in terms of: (a) the eigenvalues of the reduced Hessian, (b) the cosine of the Friedrichs angle between the subspace spanned by equality constraints and the subspace spanned by the gradients of the components that are active at the solution and (c) the distance of the inactive components of solution from the bounds. Using this analysis we show that if the QP is feasible, the iterates converge at a Q-linear rate and prescribe an optimal setting for the ADMM step-size parameter. For infeasible QPs, we show that the primal variables in ADMM converge to minimizers of the Euclidean distance between the hyperplane defined by the equality constraints and the convex set defined by the bounds. The multipliers for the bound constraints are shown to diverge along the range space of the equality constraints. Using this characterization, we also propose a termination criterion for ADMM. Numerical examples are provided to illustrate the theory through experiments.

Keywords: Quadratic Programs, Alternating Direction Methods of Multipliers, Q-Linear Convergence, Infeasibility Detection

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: arXiv:1411.7288v2

Download: [PDF]

Entry Submitted: 01/08/2015
Entry Accepted: 01/08/2015
Entry Last Modified: 01/09/2015

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