Title: Difference-of-SOS and Difference-of-Convex-SOS Decomposition Techniques for Polynomials
SJTU-Paristech & Maths department Shanghai Jiao Tong University
We are interested in polynomial decomposition techniques for reformulating any multivariate polynomial into difference-of-sums-of-squares (DSOS) and difference-of-convex-sums-of-squares (DCSOS) polynomials. Firstly, we prove that the set of DSOS and DCSOS polynomials are vector spaces and equivalent to the set of real valued polynomials R[x]. We also show that the problem of finding DSOS and DCSOS decompositions are equivalent to semidefinite programs (SDPs). Then, we focus on establishing several practical algorithms for DSOS and DCSOS decompositions with and without solving SDPs. Moreover, the DCSOS decomposition is indeed a difference-of-convex (DC) decomposition for polynomials which helps to reformulate any polynomial optimization into DC program, the later one can be solved by an efficient DC algorithm - DCA. Some numerical examples illustrate the good performance of our methods.
200 University Avenue West
Waterloo, ON N2L 3G1