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

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

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

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

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

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

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

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

Примеры

• Рассмотрим форму степени 4 от двух переменных . Имеем Поскольку существует α такое, что , а именно , то отсюда следует, что h ( x ) есть SOS. ${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$ $${\displaystyle 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}}\!.}$$ ${\displaystyle H+L(\alpha )\geq 0}$ ${\displaystyle \alpha =1}$
• Рассмотрим форму степени 4 от трех переменных . Имеем Поскольку для , то h ( x ) есть SOS. ${\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\}}={\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}}.}$$ ${\displaystyle H+L(\alpha )\geq 0}$ ${\displaystyle \alpha =(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}(x),\ldots ,G_{k}(x)}$ $${\displaystyle F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).}$$

Матрица SMR

Установить, является ли матричная форма F ( x ) SOS, означает решить задачу выпуклой оптимизации. Действительно, аналогично скалярному случаю любую F ( x ) можно записать в соответствии с SMR как где — произведение Кронекера матриц, H — любая симметричная матрица, удовлетворяющая , а — линейная параметризация линейного пространства $${\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}\right)}$$ ${\displaystyle L(\alpha )}$ $${\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 \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 тогда и только тогда, когда существует вектор, такой что выполняется следующее LMI: ${\displaystyle \alpha }$ $${\displaystyle H+L(\alpha )\geq 0.}$$

Выражение было введено в ^[9] для того, чтобы установить, является ли матричная форма 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 ⟩, порожденную n некоммутирующими буквами X = ( X ₁ , ..., X _n ) и снабженную инволюцией ^T , такой, что ^T фиксирует R и X ₁ , ..., X _n и переворачивает слова, образованные X ₁ , ..., X _n . По аналогии с коммутативным случаем некоммутативные симметрические многочлены f являются некоммутативными многочленами вида 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 тогда и только тогда, когда он является матрично-положительным. ^[10] Более того, существуют алгоритмы, позволяющие разложить матрично-положительные многочлены на сумму квадратов некоммутативных многочленов. ^[11]

Ссылки

1. Гильберт, Дэвид (сентябрь 1888 г.). «Ueber die Darstellung definer Formen als Summe von Formenquadraten». Математические Аннален . 32 (3): 342–350. дои : 10.1007/bf01443605. S2CID  177804714.
2. Чой, МД; Лам, ТЙ (1977). «Старый вопрос Гильберта». Queen's Papers in Pure and Applied Mathematics . 46 : 385–405.
3. Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (май 2016 г.). «Об аналоге Чоя–Лама теоремы Гильберта 1888 года для симметричных форм». Линейная алгебра и ее приложения . 496 : 114–120. arXiv : 1505.08145 . doi : 10.1016/j.laa.2016.01.024. S2CID  17579200.
4. Лассер, Жан Б. (2007). «Достаточные условия для того, чтобы действительный многочлен был суммой квадратов». Архив математики . 89 (5): 390–398. arXiv : math/0612358 . CiteSeerX 10.1.1.240.4438 . doi :10.1007/s00013-007-2251-y. S2CID  9319455. 
5. Powers, Victoria ; Wörmann, Thorsten (1998). "Алгоритм для сумм квадратов действительных многочленов" (PDF) . Журнал чистой и прикладной алгебры . 127 (1): 99–104. doi : 10.1016/S0022-4049(97)83827-3 .
6. Лассер, Жан Б. (2007). «Приближение суммы квадратов неотрицательных многочленов». Обзор SIAM . 49 (4): 651–669. arXiv : math/0412398 . Bibcode : 2007SIAMR..49..651L. doi : 10.1137/070693709.
7. Chesi, G.; Tesi, A.; Vicino, A.; Genesio, R. (1999). «О выпуклости некоторых задач на минимальное расстояние». Труды 5-й Европейской конференции по управлению . Карлсруэ, Германия: IEEE. С. 1446–1451.
8. Чой, М.; Лам, Т.; Резник, Б. (1995). «Суммы квадратов действительных многочленов». Труды симпозиумов по чистой математике . С. 103–125.
9. Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A. (2003). «Робастная устойчивость для политопных систем с помощью полиномиально зависящих от параметров функций Ляпунова». Труды 42-й конференции IEEE по принятию решений и управлению . Мауи, Гавайи: IEEE. стр. 4670–4675. doi :10.1109/CDC.2003.1272307.
10. Хелтон, Дж. Уильям (сентябрь 2002 г.).«Положительные» некоммутативные многочлены являются суммами квадратов». Анналы математики . 156 (2): 675–694. doi :10.2307/3597203. JSTOR  3597203.
11. Бургдорф, Сабина; Кафута, Кристиан; Клеп, Игорь; Повх, Янез (25 октября 2012 г.). «Алгоритмические аспекты сумм эрмитовых квадратов некоммутативных многочленов». Computational Optimization and Applications . 55 (1): 137–153. CiteSeerX 10.1.1.416.543 . doi :10.1007/s10589-012-9513-8. S2CID  254416733. 

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

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