Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension

Abstract

This work is a follow-up and a complement to arXiv:1912.08899 [math.OC] for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term-sparsity and chordal extension. By exploiting term-sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to obtain quasi block-diagonal matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS arXiv:1912.08899 [math.OC] has a theoretical convergence guarantee, the chordal-TSSOS has superior performance but lacks this theoretical guarantee.

arXiv comment29 pages, 14 tables, 5 figures. arXiv admin note: text overlap with arXiv:1912.08899

References in corpus (1)

• JuMP: A Modeling Language for Mathematical Optimization

Cited by in corpus (21)

• Sparse Noncommutative Polynomial Optimization
• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• TSSOS: A Moment-SOS hierarchy that exploits term sparsity
• Bounding the Distance to Unsafe Sets with Convex Optimization
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization
• Exploiting Term Sparsity in Moment-SOS hierarchy for Dynamical Systems
• Subgroup Fairness in Two-Sided Markets
• Finding unstable periodic orbits: a hybrid approach with polynomial optimization
• Fairness in Forecasting of Observations of Linear Dynamical Systems
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Learning of Linear Dynamical Systems as a Non-Commutative Polynomial Optimization Problem
• Exploiting term sparsity in Noncommutative Polynomial Optimization
• SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions
• Minimizing rational functions: a hierarchy of approximations via pushforward measures
• Global minimization of polynomial integral functionals
• A Sublevel Moment-SOS Hierarchy for Polynomial Optimization
• Globally optimal control of quantum dynamics
• Convexification of box-constrained polynomial optimization problems via monomial patterns
• Tractable semidefinite bounds of positive maximal singular values