matrix completion

A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs

  • Kartik Krishnan Sivaramakrishnan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more

    Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more