Complexity of chordal conversion for sparse semidefinite programs with small treewidth

• 成果类型: Article
• 署名作者: Zhang, Richard Y.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02137-5
• 发表日期: 2025
• 页码: 201-237
• 关键词: interior-point methods; improved approximation algorithms; exploiting sparsity; optimization; sdp; implementation; completions; relaxations; cut

摘要

If a sparse semidefinite program (SDP), specified over n x n matrices and subject to m linear constraints, has an aggregate sparsity graph G with small treewidth, then chordal conversion will sometimes allow an interior-point method to solve the SDP in just O(m + n) time per-iteration, which is a significant speedup over the Omega(n(3)) time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by an O(1) treewidth in G that is independent of m and n, as a diagonal SDP would have treewidth zero but can still necessitate up to Omega(n(3)) time per-iteration. Instead, we construct an extended aggregate sparsity graph (G) over bar superset of G by forcing each constraint matrix Ai to be its own clique in G. We prove that a small treewidth in (G) over bar does indeed guarantee that chordal conversion will solve the SDP in O(m+n) time per-iteration, to epsilon-accuracy in at most O(root m+n log (1/epsilon)) iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-k-CUT relaxation, the Lovasz theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience.