Please use this identifier to cite or link to this item:
Title: An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
Authors: Jiang, K.
Sun, D. 
Toh, K.-C. 
Keywords: Convex quadratic SDP
Inexact accelerated proximal gradient
Semismooth Newton-CG
Structured convex optimization
Issue Date: 2012
Citation: Jiang, K., Sun, D., Toh, K.-C. (2012). An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP. SIAM Journal on Optimization 22 (3) : 1042-1064. ScholarBank@NUS Repository.
Abstract: The accelerated proximal gradient (APG) method, first proposed by Nesterov for minimizing smooth convex functions, later extended by Beck and Teboulle to composite convex objective functions, 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 solved only 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{1/2〈x, Q(x)〉 + 〈c, x〉 | A (x) = b, x ≻ 0}, where Q,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 Q are highly ill-conditioned or rank deficient. © 2012 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Optimization
ISSN: 10526234
DOI: 10.1137/110847081
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.