On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2018
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917593535741952 |
|---|---|
| author | Niu, Yi-Shuai Thi, Hoai An Le Pham, Dinh Tao |
| author_facet | Niu, Yi-Shuai Thi, Hoai An Le Pham, Dinh Tao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1803_09900 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials Niu, Yi-Shuai Thi, Hoai An Le Pham, Dinh Tao Optimization and Control 12Y05, 65K05, 90C22, 90C25, 90C26, 90C30, 90C90 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. |
| title | On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials |
| topic | Optimization and Control 12Y05, 65K05, 90C22, 90C25, 90C26, 90C30, 90C90 |
| url | https://arxiv.org/abs/1803.09900 |