Optimization Online


An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP

K.F. Jiang (kaifengjiang***at***nus.edu.sg)
D.F. Sun (matsundf***at***nus.edu.sg)
K.C. Toh (mattohkc***at***nus.edu.sg)

Abstract: The accelerated proximal gradient (APG) method, first proposed by Nesterov, and later refined by Beck and Teboulle, and studied in a unifying manner by Tseng has proven to be highly efficient in solving some classes of large scale structured convex optimization (possibly nonsmooth) problems, including nuclear norm minimization problems in matrix completion and $l_1$ minimization problems in compressed sensing. The method has superior worst-case iteration complexity over the classical projected gradient method, and usually has good practical performance on problems with appropriate structures. In this paper, we extend the APG method to the inexact setting where the subproblem in each iteration is only solved approximately, and show that it enjoys the same worst-case iteration complexity as the exact counterpart if the subproblems are progressively solved to sufficient accuracy. We apply our inexact APG method to solve large scale convex quadratic semidefinite programming (QSDP) problems of the form: $\min\{ \frac{1}{2}\inprod{x}{\mathcal{Q}(x)} + \inprod{c}{x}\mid \mathcal{A}(x) = b, x\succeq 0\}$, where $\mathcal{Q},\mathcal{A}$ are given linear maps and $b,c$ are given data. The subproblem in each iteration is solved by a semismooth Newton-CG (SSNCG) method with warm-start using the iterate from the previous iteration. Our APG-SSNCG method is demonstrated to be efficient for QSDP problems whose positive semidefinite linear maps $\mathcal{Q}$ are highly ill-conditioned or rank deficient.

Keywords: Inexact accelerated proximal gradient method, Semismooth Newton CG method, Convex quadratic SDP, Nearest correlation matrix estimation

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: SIAM J. Optimization, to appear.

Download: [PDF]

Entry Submitted: 09/09/2011
Entry Accepted: 09/09/2011
Entry Last Modified: 06/16/2012

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