Argonne National Laboratory

A Multiscale Approach to A Class of Semidefinite Programs

TitleA Multiscale Approach to A Class of Semidefinite Programs
Publication TypeReport
Year of Publication2015
AuthorsLin, F, Di, Z, Leyffer, S
Other NumbersANL/MCS-P5402-0915

We consider a class of semidefinite programs that arises from combinatorial optimization problems on graphs. We propose a multilevel approach that produces a sequence of progressively coarser problems by coarsening the underlying graphs. We use the solution of each coarse problem to provide an initial approximation to the solution at a finer level. At the coarsest level we employ Newton’s method for high-accuracy solutions, and at finer levels we take advantage of the inexpensive coordinate descent updates. We coarsen the graph based on an algebraic distance that can be computed efficiently. Furthermore, our coarsening scheme preserves the properties of the graph Laplacian matrix between fine and coarse levels. Numerical experiments indicate the competitiveness of the hybrid multilevel approach compared with state-of-the-art SDP solvers for both synthetic graphs and real-world power networks.