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

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

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

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

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

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

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

{ 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 ).}

Потом, час(Икс) является SOS тогда и только тогда, когда существует вектор ${ displaystyle alpha}$ такой, что

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

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

Примеры

Рассмотрим форму степени 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).}

Поскольку существует такое α, что

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

, а именно

{ Displaystyle альфа = 1}

, следует, что час(Икс) - это SOS.

Рассмотрим форму степени 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).}

С

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

за

{ displaystyle alpha = (1,18, -0,43,0,73,1,13, -0,37,0,57)}

, следует, что час(Икс) - это SOS.

Обобщения

Матрица SOS

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

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

Матрица SMR

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

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

куда ${ 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(Икс) является SOS тогда и только тогда, когда существует вектор ${ displaystyle alpha}$ такая, что выполняется следующая LMI:

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

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

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

Рассмотрим свободная алгебра р⟨Икс⟩ Порожденная п некоммерческие письма Икс = (Икс₁,...,Икс_п) и снабжена инволюцией ^Т, так что ^Т исправления р и Икс₁,...,Икс_п и обратные слова, образованные Икс₁,...,Икс_п.По аналогии с коммутативным случаем некоммутативные симметрические многочлены ж - некоммутативные многочлены вида ж = ж^Т. Когда любая реальная матрица любого измерения r x r вычисляется на симметричном некоммутативном полиноме ж приводит к положительная полуопределенная матрица, ж называется матрично-положительным.

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

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

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

Смотрите также

[1] Гильберт, Дэвид (сентябрь 1888 г.). "Ueber die Darstellung Definiter Formen als Summe von Formenquadraten". Mathematische Annalen. 32 (3): 342–350. Дои:10.1007 / bf01443605.

[2] Choi, M.D .; Лам, Т. Ю. (1977). «Старый вопрос Гильберта». Статьи Королевы по чистой и прикладной математике. 46: 385–405.

[3] Гоэль, Чару; Кульман, Сальма; Резник, Брюс (Май 2016). «Об аналоге Чой – Лама теоремы Гильберта 1888 г. для симметричных форм». Линейная алгебра и ее приложения. 496: 114–120. arXiv:1505.08145. Дои:10.1016 / j.laa.2016.01.024.

[4] Лассер, Жан Б. (2007). «Достаточные условия того, чтобы действительный многочлен был суммой квадратов». Archiv der Mathematik. 89 (5): 390–398. arXiv:математика / 0612358. CiteSeerX 10.1.1.240.4438. Дои:10.1007 / s00013-007-2251-у.

[5] Пауэрс, Виктория; Вёрманн, Торстен (1998). «Алгоритм суммирования квадратов действительных многочленов» (PDF). Журнал чистой и прикладной алгебры. 127 (1): 99–104. Дои:10.1016 / S0022-4049 (97) 83827-3.

[6] Лассер, Жан Б. (2007). «Аппроксимация суммой квадратов неотрицательных многочленов». SIAM Обзор. 49 (4): 651–669. arXiv:математика / 0412398. Bibcode:2007SIAMR..49..651L. Дои:10.1137/070693709.

[7] Chesi, G .; Tesi, A .; Вичино, А .; Дженезио, Р. (1999). «О выпуклости некоторых задач о минимальном расстоянии». Труды 5-й Европейской конференции по контролю. Карлсруэ, Германия: IEEE. С. 1446–1451.

[8] Choi, M .; Lam, T .; Резник, Б. (1995). «Суммы квадратов действительных многочленов». Труды симпозиумов по чистой математике. С. 103–125.

[9] Chesi, G .; Garulli, A .; Tesi, A .; Вичино, А. (2003). «Робастная устойчивость политопных систем с помощью полиномиально зависящих от параметров функций Ляпунова». Материалы 42-й конференции IEEE по принятию решений и контролю. Мауи, Гавайи: IEEE. С. 4670–4675. Дои:10.1109 / CDC.2003.1272307.

[10] Хелтон, Дж. Уильям (сентябрь 2002 г.). ""Положительные «некоммутативные многочлены - это суммы квадратов». Анналы математики. 156 (2): 675–694. Дои:10.2307/3597203. JSTOR 3597203.

[11] Бургдорф, Сабина; Кафута, Кристиан; Клеп, Игорь; Повх, Янез (25 октября 2012 г.). «Алгоритмические аспекты сумм эрмитовых квадратов некоммутативных многочленов». Вычислительная оптимизация и приложения. 55 (1): 137–153. CiteSeerX 10.1.1.416.543. Дои:10.1007 / s10589-012-9513-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]