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

В математике , в форме (то есть однородный многочлен) ч ( х ) от степени 2 м в реальном п - мерного вектора х является суммой квадратов форм (SOS) , если и только если существуют формы степени т таким образом, что ${\ Displaystyle g_ {1} (х), \ ldots, g_ {k} (х)}$

{\ displaystyle h (x) = \ sum _ {i = 1} ^ {k} g_ {i} (x) ^ {2}.}

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

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

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

Чтобы установить, является ли форма h ( x ) SOS, нужно решить задачу выпуклой оптимизации . В самом деле, любую h ( x ) можно записать как

{\ Displaystyle ч (х) = х ^ {\ {м \} '} \ влево (Н + L (\ альфа) \ вправо) х ^ {\ {м \}}}

где представляет собой вектор , содержащий базу для форм степени т в х (например, всех одночленов степени т в х ), штрих 'обозначает транспонирование , Н любая симметричная матрица , удовлетворяющая ${\ Displaystyle х ^ {\ {м \}}}$

{\ displaystyle h (x) = x ^ {\ left \ {m \ right \} '} Hx ^ {\ {m \}}}

и является линейной параметризацией линейного пространства ${\ Displaystyle L (\ альфа)}$

{\ displaystyle {\ mathcal {L}} = \ left \ {L = L ': ~ x ^ {\ {m \}'} Lx ^ {\ {m \}} = 0 \ right \}.}

Размерность вектора определяется выражением ${\ Displaystyle х ^ {\ {м \}}}$

{\ Displaystyle \ сигма (п, т) = {\ бином {п + м-1} {м}},}

тогда как размерность вектора дается ${\ displaystyle \ alpha}$

{\ displaystyle \ omega (n, 2m) = {\ frac {1} {2}} \ sigma (n, m) \ left (1+ \ sigma (n, m) \ right) - \ sigma (n, 2m ).}

Тогда h ( x ) является SOS тогда и только тогда, когда существует такой вектор , что ${\ displaystyle \ alpha}$

{\ Displaystyle Н + L (\ альфа) \ geq 0,}

это означает , что матрица является положительной полуопределенной . Это проверка выполнимости линейного матричного неравенства (LMI), которая представляет собой задачу выпуклой оптимизации. Выражение было введено вместе с квадратным матричным представлением имени (SMR), чтобы установить, является ли форма SOS через LMI. Это представление также известно как матрица Грама. ${\ Displaystyle Н + L (\ альфа)}$ ${\ Displaystyle ч (х) = х ^ {\ {м \} '} \ влево (Н + L (\ альфа) \ вправо) х ^ {\ {м \}}}$

Примеры

Рассмотрим форму степени 4 от двух переменных . У нас есть ${\ displaystyle h (x) = x_ {1} ^ {4} -x_ {1} ^ {2} x_ {2} ^ {2} + x_ {2} ^ {4}}$

{\ displaystyle m = 2, ~ x ^ {\ {m \}} = \ left ({\ begin {array} {c} x_ {1} ^ {2} \\ x_ {1} x_ {2} \\ x_ {2} ^ {2} \ end {array}} \ right) \ !, ~ H + L (\ alpha) = \ left ({\ begin {array} {ccc} 1 & 0 & - \ alpha _ {1} \ \ 0 & -1 + 2 \ alpha _ {1} & 0 \\ - \ alpha _ {1} & 0 & 1 \ end {array}} \ right) \ !.}

Поскольку существует такое α, что , а именно , отсюда следует, что h ( x ) является SOS.

{\ Displaystyle Н + L (\ альфа) \ geq 0}

{\ Displaystyle \ альфа = 1}

Рассмотрим форму степени 4 от трех переменных . У нас есть ${\ displaystyle 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}}$

{\ displaystyle m = 2, ~ x ^ {\ {m \}} = \ left ({\ begin {array} {c} x_ {1} ^ {2} \\ x_ {1} x_ {2} \\ x_ {1} x_ {3} \\ x_ {2} ^ {2} \\ x_ {2} x_ {3} \\ x_ {3} ^ {2} \ end {array}} \ right) \ !, ~ H + L (\ alpha) = \ left ({\ begin {array} {cccccc} 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 {array}} \ right) \!}

Поскольку при , то h ( x ) является SOS.

{\ Displaystyle Н + L (\ альфа) \ geq 0}

{\ Displaystyle \ альфа = (1,18, -0,43,0,73,1,13, -0,37,0,57)}

Обобщения

Матрица SOS

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

{\ Displaystyle F (x) = \ sum _ {i = 1} ^ {k} G_ {i} (x) 'G_ {i} (x).}

Матрица SMR

Чтобы установить, является ли матричная форма F ( x ) SOS, нужно решить задачу выпуклой оптимизации. Действительно, аналогично скалярному случаю любая F ( x ) может быть записана согласно SMR как

{\ Displaystyle F (x) = \ left (x ^ {\ {m \}} \ otimes I_ {r} \ right) '\ left (H + L (\ alpha) \ right) \ left (x ^ {\ {m \}} \ otimes I_ {r} \ right)}

где - кронекеровское произведение матриц, H - любая симметричная матрица, удовлетворяющая условию ${\ displaystyle \ otimes}$

{\ Displaystyle F (x) = \ left (x ^ {\ {m \}} \ otimes I_ {r} \ right) 'H \ left (x ^ {\ {m \}} \ otimes I_ {r} \ верно)}

и является линейной параметризацией линейного пространства ${\ Displaystyle L (\ альфа)}$

{\ displaystyle {\ mathcal {L}} = \ left \ {L = L ': ~ \ left (x ^ {\ {m \}} \ otimes I_ {r} \ right)' L \ left (x ^ { \ {m \}} \ otimes I_ {r} \ right) = 0 \ right \}.}

Размерность вектора определяется выражением ${\ displaystyle \ alpha}$

{\ Displaystyle \ омега (п, 2 м, г) = {\ гидроразрыва {1} {2}} г \ влево (\ сигма (п, м) \ влево (г \ сигма (п, м) +1 \ вправо) - (r + 1) \ sigma (n, 2m) \ right).}

Тогда F ( x ) является SOS тогда и только тогда, когда существует такой вектор , что выполняется следующая LMI: ${\ displaystyle \ alpha}$

{\ Displaystyle Н + L (\ альфа) \ geq 0.}

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

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

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

Некоммутативный многочлен называется SOS, если существуют некоммутативный многочлен такой, что ${\ displaystyle h_ {1}, \ ldots, h_ {k}}$

{\ displaystyle f (X) = \ sum _ {i = 1} ^ {k} h_ {i} (X) ^ {T} h_ {i} (X).}

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

Languages

In other projects