Полиномиальный SOS

Эта статья о представлении неотрицательного многочлена как суммы квадратов многочленов. О представлении многочлена в виде суммы квадратов рациональных функций см. семнадцатую проблему Гильберта . Чтобы узнать о сумме квадратов последовательных целых чисел, см. квадратное пирамидальное число . Чтобы представить целое число в виде суммы квадратов целых чисел, см. теорему Лагранжа о четырёх квадратах .

В математике форма мерном (т.е. однородный многочлен) h ( x ) степени 2 m в вещественном n- векторе x является суммой квадратов форм (SOS) тогда и только тогда, когда существуют формы $g_{1}(x),\ldots ,g_{k}(x)$ степени m такая, что $$h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.$$

Каждая форма, являющаяся SOS, также является положительным полиномом , и хотя обратное не всегда верно, Гильберт доказал, что для n = 2, 2 m = 2 или n = 3 и 2 m = 4 форма является SOS тогда и только тогда, когда это позитивно. То же справедливо и для аналоговой задачи о положительных симметричных формах.

Хотя не всякая форма может быть представлена ​​как SOS, найдены явные достаточные условия для того, чтобы форма была SOS. Более того, любую вещественную неотрицательную форму можно аппроксимировать сколь угодно точно (в $l_{1}$-норма вектора его коэффициентов) последовательностью форм $\{f_{\epsilon }\}$ это SOS.

Квадратное матричное представление (SMR)

Чтобы установить, является ли форма h ( x ) SOS, необходимо решить задачу выпуклой оптимизации . Действительно, любой h ( x ) можно записать как $$h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$$где $x^{\{m\}}$ — вектор, содержащий базу для форм степени m от x (таких как все мономы степени m от x ), штрих ′ обозначает транспонирование , H — любая симметричная матрица, удовлетворяющая $$h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}$$и $L(\alpha )$ является линейной параметризацией линейного пространства $${\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.$$

Размерность вектора $x^{\{m\}}$ дается $$\sigma (n,m)={\binom {n+m-1}{m}},$$тогда как размерность вектора $\alpha$ дается $$\omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).$$

Тогда h ( x ) является SOS тогда и только тогда, когда существует вектор $\alpha$ такой, что $$H+L(\alpha )\geq 0,$$означает, что матрица $H+L(\alpha )$ является положительно-полуопределенным . Это тест осуществимости линейного матричного неравенства (LMI), который представляет собой задачу выпуклой оптимизации. Выражение $h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$ был представлен в с квадратно-матричным представлением имени (SMR), чтобы через LMI установить, является ли форма SOS. Это представление также известно как матрица Грама.

Примеры

• Рассмотрим вид степени 4 от двух переменных $h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}$. У нас есть $$m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{pmatrix}}\!,~H+L(\alpha )={\begin{pmatrix}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{pmatrix}}\!.$$ Поскольку существует α такое, что $H+L(\alpha )\geq 0$, а именно $\alpha =1$, отсюда следует, что h ( x ) является SOS.
• Рассмотрим вид степени 4 от трех переменных $h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}$. У нас есть $$m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{pmatrix}},~H+L(\alpha )={\begin{pmatrix}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{pmatrix}}.$$ С $H+L(\alpha )\geq 0$ для $\alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)$, отсюда следует, что h ( x ) является SOS.

Обобщения

Матрица SOS

Матричная форма F ( x ) (т. е. матрица, элементы которой являются формами) размерности r и степени 2 m в вещественном n -мерном векторе x является SOS тогда и только тогда, когда существуют матричные формы $G_{1}(x),\ldots ,G_{k}(x)$ степени m такая, что $$F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).$$

Матрица СМР

Чтобы установить, является ли матричная форма F ( x ) SOS, необходимо решить задачу выпуклой оптимизации. Действительно, аналогично скалярному случаю любую F ( x ) можно записать в соответствии с СМР как $$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$$где $\otimes$ — произведение Кронекера матриц, H — любая симметричная матрица, удовлетворяющая $$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)$$и $L(\alpha )$ является линейной параметризацией линейного пространства $${\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.$$

Размерность вектора $\alpha$ дается $$\omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right)-(r+1)\sigma (n,2m)\right).$$

Тогда F ( x ) является SOS тогда и только тогда, когда существует вектор $\alpha$ такой, что выполняется следующее LMI: $$H+L(\alpha )\geq 0.$$

Выражение $F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$ был представлен в для того, чтобы через LMI установить, является ли матричная форма SOS.

Некоммутативный полином SOS

Рассмотрим свободную алгебру R ⟨ X ⟩, порожденную n некоммутирующими буквами X = ( X ₁ , ..., X _n ) и снабженную инволюцией ^Т , такой, что ^Т исправляет R и X ₁ , ..., X _n и меняет местами слова, образованные X ₁ , ..., X _n .По аналогии с коммутативным случаем некоммутативные симметричные многочлены f — это некоммутативные многочлены вида f = f ^Т . Когда любая действительная матрица любого размера r × r оценивается как симметричный некоммутативный полином f, в результате получается положительная полуопределенная матрица , f называется матрично-положительной.

Некоммутативный полином называется SOS, если существуют некоммутативные полиномы. $h_{1},\ldots ,h_{k}$ такой, что $$f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).$$

Удивительно, но в некоммутативном сценарии некоммутативный полином является SOS тогда и только тогда, когда он положителен по матрице. Более того, существуют алгоритмы, позволяющие разлагать матрично-положительные полиномы в сумму квадратов некоммутативных полиномов.

См. также

• Оптимизация суммы квадратов
• Положительный полином
• Семнадцатая проблема Гильберта
• SOS-выпуклость