Optimization Online


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

Renato D. C. Monteiro (monteiro***at***isye.gatech.edu)
Camilo Ortiz (camiort***at***gatech. edu)
Benar F. Svaiter (benar***at***impa.br)

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 ingredients 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 automatically possess the above two-easy-block structure, namely: SDPs for θ-functions and θ_+-functions of graph stable set problems, and SDP relaxations of binary integer 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.

Keywords: complexity, proximal, extragradient, block-decomposition, convex optimization, conic optimization, semidefinite programing

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )


Download: [PDF]

Entry Submitted: 07/28/2012
Entry Accepted: 07/28/2012
Entry Last Modified: 10/14/2013

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