Sum-of-squares chordal decomposition of polynomial matrix inequalities
Yang Zheng, Giovanni Fantuzzi
Abstract
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\in \mathbb {R}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> if and only if there exists a sum-of-squares (SOS) polynomial $$\sigma (x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> such that $$\sigma P$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> is a sum of sparse SOS matrices. Second, we show that setting $$\sigma (x)=(x_1^2 + \cdots + x_n^2)^\nu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msubsup> <mml:mi>x</mml:mi> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>+</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>+</mml:mo> <mml:msubsup> <mml:mi>x</mml:mi> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ν</mml:mi> </mml:msup> </mml:mrow> </mml:math> for some integer $$\nu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ν</mml:mi> </mml:math> suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set $$\mathcal {K}=\{x:g_1(x)\ge 0,\ldots ,g_m(x)\ge 0\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> satisfying the Archimedean condition, then $$P(x) = S_0(x) + g_1(x)S_1(x) + \cdots + g_m(x)S_m(x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for matrices $$S_i(x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> that are sums of sparse SOS matrices. Finally, if $$\mathcal {K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> </mml:math> is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for $$(x_1^2 + \cdots + x_n^2)^\nu P(x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msubsup> <mml:mi>x</mml:mi> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>+</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>+</mml:mo> <mml:msubsup> <mml:mi>x</mml:mi> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ν</mml:mi> </mml:msup> <mml:mi>P</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> with some