Decomposition and Completion of Sum-of-Squares Matrices
Zheng Y, Papachristodoulou A, Fantuzzi G (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Institute of Electrical and Electronics Engineers Inc.
Book Volume: 2018-December
Pages Range: 4026-4031
Conference Proceedings Title: Proceedings of the IEEE Conference on Decision and Control
Event location: Miami, FL, USA
ISBN: 9781538613955
Abstract
This paper introduces a notion of decomposition and completion of sum-of-squares (SOS) matrices. We show that a subset of sparse SOS matrices with chordal sparsity patterns can be equivalently decomposed into a sum of multiple SOS matrices that are nonzero only on a principal submatrix. Also, the completion of an SOS matrix is equivalent to a set of SOS conditions on its principal submatrices and a consistency condition on the Gram representation of the principal submatrices. These results are partial extensions of chordal decomposition and completion of scalar matrices to matrices with polynomial entries. We apply the SOS decomposition result to exploit sparsity in matrix-valued SOS programs. Numerical results demonstrate the high potential of this approach for solving large-scale sparse matrix-valued SOS programs.
Authors with CRIS profile
Involved external institutions
University of Oxford
United Kingdom (GB)
Imperial College London / The Imperial College of Science, Technology and Medicine
United Kingdom (GB)
United Kingdom (GB)
Imperial College London / The Imperial College of Science, Technology and Medicine
United Kingdom (GB)
How to cite
APA:
Zheng, Y., Papachristodoulou, A., & Fantuzzi, G. (2018). Decomposition and Completion of Sum-of-Squares Matrices. In Proceedings of the IEEE Conference on Decision and Control (pp. 4026-4031). Miami, FL, USA: Institute of Electrical and Electronics Engineers Inc..
MLA:
Zheng, Yang, Antonis Papachristodoulou, and Giovanni Fantuzzi. "Decomposition and Completion of Sum-of-Squares Matrices." Proceedings of the 57th IEEE Conference on Decision and Control, CDC 2018, Miami, FL, USA Institute of Electrical and Electronics Engineers Inc., 2018. 4026-4031.
BibTeX: Download