В математике , в форме (то есть однородный многочлен) ч ( х ) степени 2 м в реальном п - мерного вектора х является суммой квадратов форм (SOS) , если и только если существуют формыстепени m такая, что
Каждая форма, которая является SOS, также является положительным полиномом , и хотя обратное не всегда верно, Гильберт доказал, что для n = 2, 2m = 2 или n = 3 и 2 m = 4 форма является SOS тогда и только тогда, когда она положительный. [1] То же самое верно и для аналоговой задачи о положительных симметрических формах. [2] [3]
Хотя не каждая форма может быть представлена как SOS, были найдены явные достаточные условия для того, чтобы форма была SOS. [4] [5] Более того, каждая действительная неотрицательная форма может быть аппроксимирована сколь угодно точно (в-норма его вектора коэффициентов) последовательностью форм это SOS. [6]
Квадратное матричное представление (SMR)
Чтобы установить, является ли форма h ( x ) SOS, нужно решить задачу выпуклой оптимизации . В самом деле, любую h ( x ) можно записать как
где представляет собой вектор , содержащий базу для форм степени т в й (например, всех мономах степени т в й ), штрихе 'обозначает транспонирование , Н является любой симметричной матрицей , удовлетворяющей
а также является линейной параметризацией линейного пространства
Размерность вектора дан кем-то
тогда как размерность вектора дан кем-то
Тогда h ( x ) является SOS тогда и только тогда, когда существует вектор такой, что
это означает, что матрица является положительным полуопределенной . Это проверка выполнимости линейного матричного неравенства (LMI), которая представляет собой задачу выпуклой оптимизации. Выражениебыл введен в [7] под названием квадратное матричное представление (SMR), чтобы установить, является ли форма SOS через LMI. Это представление также известно как матрица Грама. [8]
Примеры
- Рассмотрим форму степени 4 от двух переменных . У нас есть
- Поскольку существует такое α, что , а именно , отсюда следует, что h ( x ) является SOS.
- Рассмотрим форму степени 4 от трех переменных . У нас есть
- С для , отсюда следует, что h ( x ) является SOS.
Обобщения
Матрица SOS
Матричная форма F ( x ) (т. Е. Матрица, элементы которой являются формами) размерности r и степени 2m в вещественном n -мерном векторе x называется SOS тогда и только тогда, когда существуют матричные формыстепени m такая, что
Матрица SMR
Чтобы установить, является ли матричная форма F ( x ) SOS, нужно решить задачу выпуклой оптимизации. Действительно, аналогично скалярному случаю любая F ( x ) может быть записана согласно SMR как
где - кронекеровское произведение матриц, H - любая симметричная матрица, удовлетворяющая
а также является линейной параметризацией линейного пространства
Размерность вектора дан кем-то
Тогда F ( x ) является SOS тогда и только тогда, когда существует вектор такая, что выполняется следующая LMI:
Выражение был введен в [9] , чтобы установить, является ли матричная форма SOS через LMI.
Некоммутативный полином SOS
Рассмотрим свободную алгебру R ⟨ X ⟩ , порожденное п некоммутирующими буквы Х = ( Х 1 , ..., Х п ) и оснащены инволюции T , таким образом, что T фиксирует R и X 1 , ..., Х п и обратные слова, образованные X 1 , ..., X n . По аналогии с коммутативным случаем, некоммутативный симметрические многочлены F являются некоммутативными полиномами вида ф = F T . Когда любая вещественная матрица любой размерности rxr вычисляется на симметричном некоммутативном полиноме f, в результате получается положительная полуопределенная матрица , f называется матрично-положительной.
Некоммутативный многочлен называется SOS, если существуют некоммутативные многочлены такой, что
Удивительно, но в некоммутативном сценарии некоммутативный многочлен является SoS тогда и только тогда, когда он матрично-положительный. [10] Более того, существуют алгоритмы, позволяющие разложить матрично-положительные многочлены в сумму квадратов некоммутативных многочленов. [11]
Рекомендации
- ↑ Гильберт, Дэвид (сентябрь 1888 г.). "Ueber die Darstellung Definiter Formen als Summe von Formenquadraten" . Mathematische Annalen . 32 (3): 342–350. DOI : 10.1007 / bf01443605 .
- ^ Чой, доктор медицины; Лам, Т. Я. (1977). «Старый вопрос Гильберта». Статьи Королевы по чистой и прикладной математике . 46 : 385–405.
- ^ Гоэль, Чару; Кульман, Сальма; Резник, Брюс (май 2016 г.). «Об аналоге Чой – Лама теоремы Гильберта 1888 г. для симметричных форм». Линейная алгебра и ее приложения . 496 : 114–120. arXiv : 1505.08145 . DOI : 10.1016 / j.laa.2016.01.024 .
- ^ Лассер, Жан Б. (2007). «Достаточные условия для того, чтобы действительный многочлен был суммой квадратов» . Archiv der Mathematik . 89 (5): 390–398. arXiv : математика / 0612358 . CiteSeerX 10.1.1.240.4438 . DOI : 10.1007 / s00013-007-2251-у .
- ^ Пауэрс, Виктория ; Вёрманн, Торстен (1998). «Алгоритм для сумм квадратов действительных многочленов» (PDF) . Журнал чистой и прикладной алгебры . 127 (1): 99–104. DOI : 10.1016 / S0022-4049 (97) 83827-3 .
- ^ Лассер, Жан Б. (2007). «Аппроксимация суммой квадратов неотрицательных многочленов». SIAM Обзор . 49 (4): 651–669. arXiv : математика / 0412398 . Bibcode : 2007SIAMR..49..651L . DOI : 10.1137 / 070693709 .
- ^ Chesi, G .; Tesi, A .; Вичино, А .; Дженезио, Р. (1999). «О выпуклости некоторых задач о минимальном расстоянии» . Труды 5-й Европейской конференции по контролю . Карлсруэ, Германия: IEEE. С. 1446–1451.
- ^ Чой, М .; Lam, T .; Резник, Б. (1995). «Суммы квадратов действительных многочленов» . Труды симпозиумов по чистой математике . С. 103–125.
- ^ Chesi, G .; Garulli, A .; Tesi, A .; Вичино, А. (2003). «Робастная устойчивость политопических систем с помощью полиномиально зависящих от параметров функций Ляпунова». Труды 42-й конференции IEEE по решениям и контролю . Мауи, Гавайи: IEEE. С. 4670–4675. DOI : 10.1109 / CDC.2003.1272307 .
- ^ Хелтон, Дж. Уильям (сентябрь 2002 г.). « » Позитивный «Некоммутативные Полиномы суммы квадратов». Анналы математики . 156 (2): 675–694. DOI : 10.2307 / 3597203 . JSTOR 3597203 .
- ^ Бургдорф, Сабина; Кафута, Кристиан; Клеп, Игорь; Повх, Янез (25 октября 2012 г.). «Алгоритмические аспекты сумм эрмитовых квадратов некоммутативных многочленов». Вычислительная оптимизация и приложения . 55 (1): 137–153. CiteSeerX 10.1.1.416.543 . DOI : 10.1007 / s10589-012-9513-8 .
Смотрите также
- Оптимизация по сумме квадратов
- Положительный многочлен
- Семнадцатая проблема Гильберта
- SOS-выпуклость