Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework

By Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, Kazuhide Nakata. SIAM Journal on Optimization, 2000

353 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/332116d99018c781975c341b719daa68259e024a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Convex Relaxation of Optimal Power Flow—Part I: Formulations and Equivalence (2014, methodology): “OPF-ch usually requires more computation than OPF-socp but much less than OPF-sdp for large sparse networks (even though OPF-ch can be as complex as OPF-sdp in the worse case [64], [65]).”
Convex relaxations and linear approximation for optimal power flow in multiphase radial networks (2014, background): “There is a standard way of positive semidefinite matrix completion—looking at the chordal extension of a partial matrix [16].”
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization (2003, methodology): “For the algorithms and issues surrounding the classical, second-order interior-point methods for SDP, see [18], and for a selection of papers which deal with sparsity in these types of interior-point methods, see [3, 10].”
Strong SOCP Relaxations for the Optimal Power Flow Problem (2015, methodology): “The underlying methodology utilizes techniques such as chordal graph extension, tree-width decomposition, and matrix completion, as proposed and developed in Fukuda et al. (2001) and Nakata et al. (2003).”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “For completeness, we also mention the work of [14, 31, 58, 70] on second-order methods, that take advantage of data sparsity in order to handle large SDPs in a more eﬃcient way.”
Convex relaxation of optimal power flow: A tutorial (2013, background): “Given a perfect elimination ordering all maximal cliques qk can be enumerated and XF (qk) constructed efficiently [35].”
A Rewriting System for Convex Optimization Problems (2017, background): “The particulars of this reduction (and related ones) can be found in Fukuda, Kojima, Murota, and Nakata (2001), whose authors were among the ﬁrst to exploit chordal sparsity patterns to decompose large semideﬁnite programs, and (Vandenberghe & Andersen, 2015, § 14.2), which thoroughly surveys the…”