Decomposition and Completion of Sum-of-Squares Matrices
For researchers in optimization and control, this provides a method to exploit sparsity in matrix-valued SOS programs, enabling solution of larger-scale problems.
This paper extends chordal decomposition and completion from scalar matrices to sum-of-squares (SOS) matrices, showing that sparse SOS matrices with chordal sparsity can be decomposed into a sum of principal submatrix SOS matrices, and that SOS matrix completion reduces to SOS conditions on principal submatrices plus a consistency condition. Numerical results demonstrate high potential for solving large-scale sparse matrix-valued SOS programs.
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.