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.

arXiv comment49 pages, 21 figures, 4 tables

References in corpus (50)

• Distributed Optimal Power Flow for Smart Microgrids
• Symmetry groups, semidefinite programs, and sums of squares
• Smoothing Traffic Flow via Control of Autonomous Vehicles
• Semidefinite relaxations for certifying robustness to adversarial examples
• Leading Cruise Control in Mixed Traffic Flow: System Modeling, Controllability, and String Stability
• Scalable Semidefinite Programming
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Exploiting symmetries in SDP-relaxations for polynomial optimization
• Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
• Bounds for deterministic and stochastic dynamical systems using sum-of-squares optimization
• COSMO: A conic operator splitting method for convex conic problems
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Surface Multigrid via Intrinsic Prolongation
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• Sparse Noncommutative Polynomial Optimization
• Sparsity Invariance for Convex Design of Distributed Controllers
• Bounding extreme events in nonlinear dynamics using convex optimization
• Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
• Logarithmic barriers for sparse matrix cones
• Bounding stationary averages of polynomial diffusions via semidefinite programming
• On the Robustness and Scalability of Semidefinite Relaxation for Optimal Power Flow Problems
• Bounds on heat transport for convection driven by internal heating
• A Framework for Input-Output Analysis of Wall-Bounded Shear Flows
• Distributed Design for Decentralized Control using Chordal Decomposition and ADMM
• Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
• Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number
• Bounding extrema over global attractors using polynomial optimisation
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Chordal networks of polynomial ideals
• Fast ADMM for sum-of-squares programs using partial orthogonality
• Sum-of-Squares approach to feedback control of laminar wake flows
• Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• Recovery of binary sparse signals from compressed linear measurements via polynomial optimization
• Decomposition of arrow type positive semidefinite matrices with application to topology optimization
• TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization
• Approximating regions of attraction of a sparse polynomial differential system *
• 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
• Decomposition and Completion of Sum-of-Squares Matrices
• Polyhedral approximations of the semidefinite cone and their application
• Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
• Angle-Based Sensor Network Localization
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers
• A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Sparse PSD approximation of the PSD cone
• Controller Synthesis for Discrete-Time Polynomial Systems via Occupation Measures
• Chordal Decomposition for Spectral Coarsening

Cited by in corpus (6)

• Data-driven design of safe control for polynomial systems
• The background method: Theory and computations
• Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization
• Sparsity in the numerical six-point bootstrap
• Global weight optimization of frame structures with polynomial programming
• Approximate PSD-Completion for Generalized Chordal Graphs