Sum-of-squares chordal decomposition of polynomial matrix inequalities

Zheng Y, Fantuzzi G (2021)

Publication Type: Journal article

Publication year: 2021

Journal

Mathematical Programming Springer Verlag (Germany)

DOI: 10.1007/s10107-021-01728-w

Abstract

We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert–Artin, Reznick, Putinar, and Putinar–Vasilescu Positivstellensätze. First, we establish that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x∈ Rn if and only if there exists a sum-of-squares (SOS) polynomial σ(x) such that σP is a sum of sparse SOS matrices. Second, we show that setting σ(x)=(x12+⋯+xn2)ν for some integer ν suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set K= { x: g1(x) ≥ 0 , … , gm(x) ≥ 0 } satisfying the Archimedean condition, then P(x) = S(x) + g1(x) S1(x) + ⋯ + gm(x) Sm(x) for matrices Si(x) that are sums of sparse SOS matrices. Finally, if K is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x12+⋯+xn2)νP(x) with some integer ν≥ 0 when P and g1, … , gm are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones.

Authors with CRIS profile

Giovanni Fantuzzi

Involved external institutions

University of California, San Diego US United States (USA) (US) Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Zheng, Y., & Fantuzzi, G. (2021). Sum-of-squares chordal decomposition of polynomial matrix inequalities. Mathematical Programming. https://dx.doi.org/10.1007/s10107-021-01728-w

MLA:

Zheng, Yang, and Giovanni Fantuzzi. "Sum-of-squares chordal decomposition of polynomial matrix inequalities." Mathematical Programming (2021).

BibTeX: Download