On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials - Université de Lorraine Access content directly
Journal Articles SIAM Journal on Optimization Year : 2024

On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials


In this article, we are interested in developing polynomial decomposition techniques based on sums-of-squares (SOS), namely the difference-of-sums-of-squares (D-SOS) and the difference-of-convex-sums-of-squares (DC-SOS). In particular, the DC-SOS decomposition is very useful for difference-of-convex (DC) programming formulation of polynomial optimization problems. First, we introduce the cone of convex-sums-of-squares (CSOS) polynomials and discuss its relationship to the sums-of-squares (SOS) polynomials, the non-negative polynomials and the SOS-convex polynomials. Then, we propose the set of D-SOS and DC-SOS polynomials, and prove that any polynomial can be formulated as D-SOS and DC-SOS. The problem of finding D-SOS and DC-SOS decompositions can be formulated as a semi-definite program and solved for any desired precision in polynomial time using interior point methods. Some algebraic properties of CSOS, D-SOS and DC-SOS are established. Second, we focus on establishing several practical algorithms for exact D-SOS and DC-SOS polynomial decompositions without solving any SDP. The numerical performance of the proposed D-SOS and DC-SOS decomposition algorithms and their parallel versions, tested on a dataset of 1750 randomly generated polynomials, is reported.

Dates and versions

hal-04589956 , version 1 (28-05-2024)



Yi-Shuai Niu, Hoai An Le Thi, Tao Pham Dinh. On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials. SIAM Journal on Optimization, 2024, 34 (2), pp.1852-1878. ⟨10.1137/22M1495524⟩. ⟨hal-04589956⟩
24 View
0 Download



Gmail Mastodon Facebook X LinkedIn More