Sparse Polynomial Optimization with Matrix Constraints

2024/11/27 by Jiawang Nie, Nie, Jiawang, Zheng Qu +5
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2411.18820

openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

This paper studies the hierarchy of sparse matrix Moment-SOS relaxations for solving sparse polynomial optimization problems with matrix constraints. First, we prove a sufficient and necessary condition for the sparse hierarchy to be tight. Second, we discuss how to detect the tightness and extract minimizers. Third, for the convex case, we show that the hierarchy of the sparse matrix Moment-SOS relaxations is tight, under some general assumptions. In particular, we show that the sparse matrix Moment-SOS relaxation is tight for every order when the problem is SOS-convex. Numerical experiments are provided to show the efficiency of the sparse relaxations.

Related

• A Characterization for Tightness of the Sparse Moment-SOS Hierarchy
• Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization
• Sparse Polynomial Matrix Optimization
• Lagrange multiplier expressions for matrix polynomial optimization and tight relaxations
• Sparse Polynomial Optimization: Theory and Practice