Optimization Online


An inexact block-decomposition method for extra large-scale conic semidefinite programming

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 present an inexact block-decomposition (BD) first-order method for solving standard form conic semidefinite programming (SDP) which avoids computations of exact projections onto the manifold defined by the affine constraints and, as a result, is able to handle extra large SDP instances. The method is based on a two-block reformulation of the optimality conditions where the first block corresponds to the complementarity conditions and the second one corresponds to the manifolds consisting of both the primal and dual affine feasibility constraints. While the proximal subproblem corresponding to the first block is solved exactly, the one corresponding to the second block is solved inexactly in order to avoid finding the exact solution of the underlying augmented primal-dual linear system. The error condition required by the BD method naturally suggests the use of a relative error condition in the context of the latter augmented primal-dual linear system. Our implementation uses the conjugate gradient (CG) method applied to a reduced positive definite dual linear system to obtain inexact solutions of the augmented linear system. In addition, we implemented the proposed BD method with the following refinements: an adaptive choice of stepsize for performing an extragradient step; and a new dynamic scaling scheme that uses two scaling factors to balance three inclusions comprising the optimality conditions of the conic SDP. Finally, we present computational results showing the efficiency of our method for solving various extra-large SDP instances, including some with at least two million constraints and/or fifty million non-zero coefficients in the affine constraints.

Keywords: complexity, proximal, extragradient, block-decomposition, conic optimization, semidefinite programing, large-scale, conjugate gradient

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Optimization Software and Modeling Systems


Download: [PDF]

Entry Submitted: 12/11/2013
Entry Accepted: 12/11/2013
Entry Last Modified: 02/01/2014

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