A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions

X. Li, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

65 Citations (Scopus)

Abstract

© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. This paper is devoted to the design of an efficient and convergent semi-proximal alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun et al. (2014, arXiv:1404.5378). Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP.
Original languageEnglish
Pages (from-to)333-373
Number of pages41
JournalMathematical Programming
Volume155
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • Convergence
  • Convex quadratic conic programming
  • Multiple-block ADMM
  • QSDP
  • Semi-proximal ADMM

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this