An efficient inexact ABCD method for least squares semidefinite programming

Defeng Sun, K.-C. Toh, L. Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

Abstract

© 2016 Societ y for Industrial and Applied Mathematics. We consider least squares semidefinite programming (LSSDP) where the primal matrix variable must satisfy given linear equality and inequality constraints, and must also lie in the intersection of the cone of symmetric positive semidefinite matrices and a simple polyhedral set. We propose an inexact accelerated block coordinate descent (ABCD) method for solving LSSDP via its dual, which can be reformulated as a convex composite minimization problem whose objective is the sum of a coupled quadratic function involving four blocks of variables and two separable nonsmooth functions involving only the first and second block, respectively. Our inexact ABCD method has the attractive O(1/k2) iteration complexity if the subproblems are solved progressively more accurately. The design of our ABCD method relies on recent advances in the symmetric Gauss-Seidel technique for solving a convex minimization problem whose objective is the sum of a multiblock quadratic function and a nonsmooth function involving only the first block. Extensive numerical experiments on various classes of over 600 large scale LSSDP problems demonstrate that our proposed ABCD method not only can solve the problems to high accuracy, but it is also far more efficient than (a) the well-known block coordinate descent method, (b) an enhanced version of the accelerated randomized block coordinate gradient method, and (c) the accelerated proximal gradient method.
Original languageEnglish
Pages (from-to)1072-1100
Number of pages29
JournalSIAM Journal on Optimization
Volume26
Issue number2
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • Accelerated block coordinate descent
  • Least squares sdp
  • Symmetric Gauss-Seidel

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this