Mathematical Programming Computation, Volume 6, Number 2, June 2014

Font Size:  Small  Medium  Large

A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

Renato D. C. Monteiro, Camilo Ortiz, Benar F. Svaiter

Abstract


In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredi- ents from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks. We then specialize the method to the context of conic semidefinite programming (SDP) problems consisting of two easy blocks of constraints. Without putting them in standard form, we show that four important classes of graph-related conic SDP problems auto- matically possess the above two-easy-block structure, namely: SDPs for O-functions and O+-functions of graph stable set problems, and SDP relaxations of binary inte- ger quadratic and frequency assignment problems. Finally, we present computational results on the aforementioned classes of SDPs showing that our method outperforms the three most competitive codes for large-scale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a Newton-CG augmented Lagrangian method, called SDPNAL, by Zhao et al., and a variant of the BP method, called the SPDAD method, by Wen et al.


Full Text: pdf

mpc footer
© MPS 2008-2016