Sparse Copositive Polynomial Optimization
Suhan Zhong, Jinling Zhou, Jiawang Nie, Xindong Tang · 2026
Read Sparse Copositive Polynomial Optimization by Suhan Zhong, Jinling Zhou, Jiawang Nie, Xindong Tang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00180.txt.
Introduction
Zhong, Zhou, Nie, and Tang study copositive optimization where the goal is a sparse polynomial and constraints are linear over the nonnegative orthant. They propose sparse Moment-SOS relaxations, prove when these relaxations are tight, and show tightness under a cop-SOS convexity assumption. Against dense versions, the sparse ones run faster. Tests confirm the speed gains.
Catalog record
| CREATOR | Suhan Zhong, Jinling Zhou, Jiawang Nie, Xindong Tang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60323 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00180
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse Copositive Polynomial Optimization Suhan Zhong, Jinling Zhou, Jiawang Nie, Xindong Tang Abstract . This paper studies the copositive optimization problem whose objective is a sparse polynomial, with linear constraints over the nonnegative orthant. We propose sparse Moment-SOS relaxations to solve it. Necessary and sufficient conditions are shown for these relaxations to be tight. In particular, we prove they are tight under the cop-SOS convexity assumption. Compared to the traditional dense ones, the sparse Moment-SOS relaxations are more computationally efficient. Numerical experiments are given to show the efficiency. 2020 Mathematics Subject Classification 90C23, 90C22, 90C30 1. Introduction Let x\coloneqq(x_{1},\ldots,x_{n}) be a vector variable in the n -dimensional real Euclidean space \mathbb{R}^{n} . We consider the sparse polynomial optimization problem (1.1) \left\{\begin{array}[]{cl}\min\limits_{x\in\mathbb{R}^{n}}&f(x)\coloneqq f_{1}(x_{{\rm\Delta}_{1}})+\cdots+f_{m}(x_{{\rm\Delta}_{m}})\\ \mathrm{s.t.}&Ax=b,\,Cx\geq d,\,x\geq 0,\end{array}\right. for given matrices A\in\mathbb{R}^{m_{1}\times n} , C\in\mathbb{R}^{m_{2}\times n} and vectors b\in\mathbb{R}^{m_{1}} , d\in\mathbb{R}^{m_{2}} . In the above, {\rm\Delta}_{1},\ldots,{\rm\Delta}_{m} are subsets of [n]\coloneqq\{1,\ldots,n\} such that {\rm\Delta}_{1}\cup\cdots\cup{\rm\Delta}_{m}\,=\,[n]. Each f_{i}(x_{{\rm\Delta}_{i}}) is a polynomial in the subvector x_{{\rm\Delta}_{i}}\coloneqq(x_{j_{1}},\cdots,x_{j_{n_{i}}}),\qquad\text{where}\quad{\rm\Delta}_{i}=\{j_{1},\ldots,j_{n_{i}}\}. A polynomial like f as in ( 1.1 ) is said to have the sparsity pattern ({\rm\Delta}_{1},\ldots,{\rm\Delta}_{m}) . In the above, the matrices A and C can be either dense or sparse. The minimum value of ( 1.1 ) is denoted as f_{min} , and its feasible region is (1.2) K=\{x\in\mathbb{R}^{n}:Ax=b,\,Cx\geq d,\,x\geq 0\}. We call ( 1.1 ) a sparse copositive polynomial optimization problem. This is not the same as copositive programming , which typically means linear conic optimization problems over the copositive matrix cone [ 1 , 7 , 10 , 12 ] . Problem ( 1.1 ) can be viewed as a general dense polynomial optimization problem. It can be solved by the standard Moment-SOS hierarchy of semidefinite programming (SDP) relaxations [ 21 , 25 , 26 , 32 ] . We call these relaxations to be the dense ones. This hierarchy has asymptotic convergence under the Archimedeanness [ 21 ] and has finite convergence under some additional optimality conditions [ 31 ] . It is typically expensive to solve the dense Moment-SOS relaxations for large-scale problems. Recently, sparse Moment-SOS relaxations have been extensively used to solve large-scale polynomial optimization problems. In them, the objective function usually has the sparsity pattern like f as in ( 1.1 ), and each constraining polynomial is only about a subvector x_{{\rm\Delta}_{i}} . By exploiting the sparsity, the sparse relaxation formulates semidefinite programs whose positive semidefinite matrix variables have smaller dimensions, compared with the dense one. Sparse relaxations are efficient for solving large scale problems. They have asymptotic convergence under certain conditions. We refer to the earlier work [ 19 , 22 , 29 , 33 , 45 , 43 ] . The finite convergence property of sparse Moment-SOS relaxations is investigated in [ 36 , 37 ] . Moreover, there exist other types of sparsity patterns in polynomial optimization; see [ 18 , 20 , 28 , 44 ] . We remark that problem ( 1.1 ) is different from other sparse polynomial optimization problems, since its linear constraints can be dense. The prior sparse relaxation methods are not appropriate for solving the sparse copositive polynomial optimization problem ( 1.1 ). In this paper, we propose new sparse Moment-SOS relaxations to solve ( 1.1 ). Copositive polynomials have been extensively and actively studied in optimization [ 5 , 12 , 34 , 35 ] . A homogeneous polynomial p(x) of degree d is said to be copositive if p(x)\geq 0 for all x\geq 0 . For the degree two case, a symmetric matrix A is copositive if and only if the associated quadratic form is copositive. The set of all d th degree copositive forms in n variables is a convex cone, which we denote by \mathcal{COP}_{n,d} . Copositive polynomials and their applications are studied in [ 13 , 14 , 24 , 34 ] . Checking memberships of the copositive cone \mathcal{COP}_{n,d} is NP-hard [ 9 ] . We refer to [ 17 , 34 , 35 , 39 ] for the related work. In the existing literature (e.g., [ 1 , 7 , 10 , 12 ] ), the term copositive programming or copositive optimization usually refers to the linear conic optimization problem over the copositive matrix cone \mathcal{COP}_{n,2} . We refer to [ 6 , 11 , 38 , 42 ] for applications of copositive optimization. Contributions. Problem ( 1.1 ) is a class of linearly constrained sparse polynomial optimization problems. It can be equivalently formulated as (1.3) \left\{\begin{array}[]{cl}\max&\gamma\\ \mathrm{s.t.}&f(x)-\gamma\in\mathscr{P}_{d}(K),\end{array}\right. where d is the degree of f and \mathscr{P}_{d}(K) denotes the cone of degree- d polynomials that are nonnegative on K , i.e., (1.4) \mathscr{P}_{d}(K)\coloneqq\{q\in\mathbb{R}[x]_{d}:q(x)\geq 0\,\,\forall x\in K\}. In this paper, we propose new sparse Moment-SOS relaxations to solve ( 1.3 ), by exploiting the sparsity pattern of f , and investigate conditions for these relaxations to be tight. The sparse relaxations are more appropriate for solving large-scale problems. Our main contributions are: • We propose new sparse Moment-SOS relaxations to solve ( 1.1 ), or its equivalent reformulation ( 1.3 ). The sparse moment and SOS relaxations are given in ( 3.3 ) and ( 3.4 ), respectively. • We characterize conditions for the sparse Moment-SOS relaxations ( 3.3 )-( 3.4 ) to be tight. This is shown in Theorems 3.1 , 3.2 , and 3.4 . • We show that the sparse Moment-SOS relaxations ( 3.3 )-( 3.4 ) are tight under the cop-SOS convexity assumption. This is shown in Theorem 4.4 . The rest of this paper is organized as follows. In Section 2 , we introduce some notation and give preliminaries for polynomial optimization. In Section 3 , we propose the sparse Moment-SOS relaxations ( 3.3 )-( 3.4 ) and characterize conditions for their tightness. In Section 4 , we prove these sparse relaxations are tight under the cop-SOS convexity assumption. Numerical experiments are presented in Section 5 and some conclusions are drawn in Section 6 . 2. Preliminaries Notation The symbol \mathbb{R} denotes the real field, \mathbb{R}_{+} denotes the set of nonnegative real numbers, and \mathbb{N} denotes the set of nonnegative integers. For a positive real number t , \lceil t\rceil denotes the smallest integer that is greater than or equal to t . For a positive integer n , denote [n]\coloneqq\{1,\ldots,n\} . The notation \mathbb{R}^{n} (resp. \mathbb{R}_{+}^{n} , \mathbb{N}^{n} ) stands for the set of n -dimensional vectors of entries in \mathbb{R} (resp. \mathbb{R}_{+} , \mathbb{N} ). We denote the subspace \mathbb{R}^{{\rm\Delta}_{i}}\coloneqq\{x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}:x_{j}=0\,\,\text{for all}\,\,j\not\in{\rm\Delta}_{i}\}, and denote \mathbb{R}_{+}^{{\rm\Delta}_{i}} and \mathbb{N}^{{\rm\Delta}_{i}} similarly. The notation \mathbb{R}[x] and \mathbb{R}[x_{{\rm\Delta}_{i}}] stand for the polynomial rings in x and x_{{\rm\Delta}_{i}} , respectively. The set of polynomials in \mathbb{R}[x] with degrees up to d is denoted as \mathbb{R}[x]_{d} , and \mathbb{R}[x_{{\rm\Delta}_{i}}]_{d} is defined similarly. The column vector of monomials in x and of degrees up to d , ordered in the graded lexicographic ordering, is denoted by [x]_{d}\coloneqq\big[\begin{array}[]{ccccccccccccc}1&x_{1}&\cdots&x_{n}&x_{1}^{2}&x_{1}x_{2}&\cdots&x_{n}^{2}&\cdots&x_{1}^{d}&x_{1}^{d-1}x_{2}&\cdots&x_{n}^{d}\end{array}]^{T}. The monomial vector [x_{{\rm\Delta}_{i}}]_{d} is defined similarly. 2.1. Standard Moment-SOS relaxations General polynomial optimization problems can be solved globally by the dense Moment-SOS relaxations [ 21 ] . A polynomial \sigma\in\mathbb{R}[x] is said to be a sum-of-squares (SOS) if there exist polynomials p_{1},\ldots,p_{l}\in\mathbb{R}[x] such that \sigma=p_{1}^{2}+\cdots+p_{l}^{2} . We denote by {\rm\Sigma}[x] the cone of SOS polynomials in x . For a degree d