Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization

Abstract

Chordal and factor-width decomposition methods for semidefinite programming and polynomial optimization have recently enabled the analysis and control of large-scale linear systems and medium-scale nonlinear systems. Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. Factor-width decompositions, instead, relax or strengthen SDPs with dense semidefinite matrices into more tractable problems, trading feasibility or optimality for lower computational complexity. This article reviews recent advances in large-scale semidefinite and polynomial optimization enabled by these two types of decomposition, highlighting connections and differences between them. We also demonstrate that chordal and factor-width decompositions allow for significant computational savings on a range of classical problems from control theory, and on more recent problems from machine learning. Finally, we outline possible directions for future research that have the potential to facilitate the efficient optimization-based study of increasingly complex large-scale dynamical systems.

49 pages, 21 figures, 4 tables

References in corpus (10)

• Symmetry groups, semidefinite programs, and sums of squares
• Surface Multigrid via Intrinsic Prolongation
• Bounds on heat transport for convection driven by internal heating
• Recovery of binary sparse signals from compressed linear measurements via polynomial optimization
• TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization
• On the Existence of Block-Diagonal Solutions to Lyapunov and ${\mathcal{H}}_{\infty }$ Riccati Inequalities
• On Approximations of the PSD Cone by a Polynomial Number of Smaller-sized PSD Cones
• A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs
• Sparse PSD approximation of the PSD cone
• Chordal Decomposition for Spectral Coarsening

Cited by in corpus (5)

• Data-driven design of safe control for polynomial systems
• The background method: Theory and computations
• Sparsity in the numerical six-point bootstrap
• Global weight optimization of frame structures with polynomial programming
• Approximate PSD-Completion for Generalized Chordal Graphs