DSA-BD v0.31032011 · March 31, 2011
Dynamic Scaled Adaptive Block Decomposition algorithm for Semidefinite Programming.
DSA-BD is a MATLAB package developed by C. Ortiz, R. D. C. Monteiro and B. F. Svaiter for solving general semidefinite programs (SDPs) using a block-decomposition first-order method, which is a special case of the hybrid proximal extragradient (HPE) method, a framework of inexact proximal point methods introduced by B. F. Svaiter and M. Solodov. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products in the primal and dual spaces; dynamic update of the scaled inner product in the primal space for properly balancing the primal and dual relative residuals, and; proper choices of the initial primal and dual iterates, as well as the initial parameter for the primal scaled inner product. The subroutines for most of the algebraic operations (SVD, matrix-vector multiplication) use a LAPACK implementation coded in C, using the SDP data structure implemented in SDPT3 (software package by K. C. Toh, M.J. Todd, and R. H. Tütüncu) and SDPNAL (software package by X. Y. Zhao, D. Sun, and K. C. Toh).
Details of the algorithm: Implementation of a block decomposition algorithm for solving large-scale conic optimization problems by R. D. C. Monteiro, C. Ortiz and B. F. Svaiter.
- Download DSA-BD v0.31032011
- Quick user guide (PDF, under development)
- HTML documentation
Installation. DSA-BD requires a few mex-files that you may need to compile in MATLAB. Run MATLAB in the directory DSA_BD, then type:
>> Install_DSA_BD;To check the installation:
>> DSA_BD_demo;