Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials

Zheng Y, Papachristodoulou A (2019)

Publication Type: Conference contribution

Publication year: 2019

Journal

Proceedings of the American Control Conference

Publisher: Institute of Electrical and Electronics Engineers Inc.

Book Volume: 2019-July

Pages Range: 5513-5518

Conference Proceedings Title: Proceedings of the American Control Conference

Event location: Philadelphia, PA US

ISBN: 9781538679265

DOI: 10.23919/acc.2019.8814998

Abstract

Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. This work investigates the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. For problems with sparse polynomials, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.

Authors with CRIS profile

Giovanni Fantuzzi

Involved external institutions

University of Oxford GB United Kingdom (GB) Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Zheng, Y., & Papachristodoulou, A. (2019). Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials. In Proceedings of the American Control Conference (pp. 5513-5518). Philadelphia, PA, US: Institute of Electrical and Electronics Engineers Inc..

MLA:

Zheng, Yang, and Antonis Papachristodoulou. "Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials." Proceedings of the 2019 American Control Conference, ACC 2019, Philadelphia, PA Institute of Electrical and Electronics Engineers Inc., 2019. 5513-5518.

BibTeX: Download