SOS-выпуклость

Многомерный полином является SOS-выпуклым (или выпуклой суммой квадратов ), если его матрица Гессе H может быть факторизована как H ( x ) = S ^Т( x ) S ( x ) где S — матрица (возможно, прямоугольная), элементы которой являются полиномами от x . ^[1] Другими словами, матрица Гессиана представляет собой матричный полином SOS .

Эквивалентное определение состоит в том, что форма, определенная как g ( x , y ) = y ^ТH ( x ) y представляет собой сумму квадратов форм . ^[2]

Связь с выпуклостью

Если многочлен SOS-выпуклый, то он также выпуклый. ^{[ нужна ссылка ]} Поскольку установление того, является ли полином SOS-выпуклым, равносильно решению полуопределенной задачи программирования , SOS-выпуклость может использоваться как показатель для установления того, является ли полином выпуклым. Напротив, определение того, является ли общий полином степени больше четырех выпуклым, является NP-трудной проблемой. ^[3]

Первый контрпример многочлена, который является выпуклым, но не SOS-выпуклым, был построен Амиром Али Ахмади и Пабло Паррило в 2009 году. ^[4] Полином — это однородный многочлен, представляющий собой сумму квадратов и определяемый формулой: ^[4]

$p(x)=32x_{1}^{8}+118x_{1}^{6}x_{2}^{2}+40x_{1}^{6}x_{3}^{2}+25x_{1}^{4}x_{2}^{4}-43x_{1}^{4}x_{2}^{2}x_{3}^{2}-35x_{1}^{4}x_{3}^{4}+3x_{1}^{2}x_{2}^{4}x_{3}^{2}-16x_{1}^{2}x_{2}^{2}x_{3}^{4}+24x_{1}^{2}x_{3}^{6}+16x_{2}^{8}+44x_{2}^{6}x_{3}^{2}+70x_{2}^{4}x_{3}^{4}+60x_{2}^{2}x_{3}^{6}+30x_{3}^{8}$

В том же году Григорий Блехерман неконструктивным образом доказал существование выпуклых форм, не представимых в виде суммы квадратов. ^[5] Явный пример выпуклой формы (со степенью 4 и 272 переменными), которая не является суммой квадратов, был заявлен Джеймсом Сондерсоном в 2021 году. ^[6]

Связь с неотрицательностью и суммой квадратов

В 2013 году Амир Али Ахмади и Пабло Паррило показали, что каждый выпуклый однородный полином от n переменных и степени 2 d является SOS-выпуклым тогда и только тогда, когда либо (a) n = 2, либо (b) 2 d = 2, либо (c) n = 3 и 2 д = 4. ^[7] Впечатляет то, что то же самое соотношение справедливо для неотрицательного однородного многочлена от n переменных и степени 2 d , который можно представить как сумму квадратов многочленов (см. семнадцатую проблему Гильберта ).

Ссылки

^ Хелтон, Дж. Уильям; Не, Цзяван (2010). «Полуопределенное представление выпуклых множеств». Математическое программирование . 122 (1): 21–64. arXiv : 0705.4068 . дои : 10.1007/s10107-008-0240-y . ISSN 0025-5610 . S2CID 1352703 .
^ Ахмади, Амир Али; Паррило, Пабло А. (2010). «Об эквивалентности алгебраических условий выпуклости и квазивыпуклости многочленов». 49-я конференция IEEE по принятию решений и управлению (CDC) . стр. 3343–3348. дои : 10.1109/CDC.2010.5717510 . hdl : 1721.1/74151 . ISBN 978-1-4244-7745-6 . S2CID 11904851 .
^ Ахмади, Амир Али; Ольшевский, Алекс; Паррило, Пабло А.; Цициклис, Джон Н. (2013). «NP-трудность определения выпуклости многочленов четвертой степени и связанные с ней проблемы». Математическое программирование . 137 (1–2): 453–476. arXiv : 1012.1908 . дои : 10.1007/s10107-011-0499-2 . ISSN 0025-5610 . S2CID 2319461 .
^ Jump up to: ^а ^б Ахмади, Амир Али; Паррило, Пабло А. (2009). «Положительно определенный полиномиальный гессиан, который не учитывает». Материалы 48-й конференции IEEE по принятию решений и управлению (CDC), проведенной совместно с 28-й китайской конференцией по управлению в 2009 году . стр. 1195–1200. дои : 10.1109/CDC.2009.5400519 . hdl : 1721.1/58871 . ISBN 978-1-4244-3871-6 . S2CID 5344338 .
^ Блехерман, Григорий (04 октября 2009 г.). «Выпуклые формы, не являющиеся суммами квадратов». arXiv : 0910.0656 [ math.AG ].
^ Сондерсон, Джеймс (2022). «Выпуклая форма, не являющаяся суммой квадратов». Математика исследования операций . 48 : 569–582. arXiv : 2105.08432 . дои : 10.1287/moor.2022.1273 . S2CID 234763204 .
^ Ахмади, Амир Али; Паррило, Пабло А. (2013). «Полная характеристика разрыва между выпуклостью и SOS-выпуклостью». SIAM Journal по оптимизации . 23 (2): 811–833. arXiv : 1111.4587 . дои : 10.1137/110856010 . ISSN 1052-6234 . S2CID 16801871 .

См. также

[1] Хелтон, Дж. Уильям; Не, Цзяван (2010). «Полуопределенное представление выпуклых множеств». Математическое программирование . 122 (1): 21–64. arXiv : 0705.4068 . дои : 10.1007/s10107-008-0240-y . ISSN 0025-5610 . S2CID 1352703 .

[2] Ахмади, Амир Али; Паррило, Пабло А. (2010). «Об эквивалентности алгебраических условий выпуклости и квазивыпуклости многочленов». 49-я конференция IEEE по принятию решений и управлению (CDC) . стр. 3343–3348. дои : 10.1109/CDC.2010.5717510 . hdl : 1721.1/74151 . ISBN 978-1-4244-7745-6 . S2CID 11904851 .

[3] Ахмади, Амир Али; Ольшевский, Алекс; Паррило, Пабло А.; Цициклис, Джон Н. (2013). «NP-трудность определения выпуклости многочленов четвертой степени и связанные с ней проблемы». Математическое программирование . 137 (1–2): 453–476. arXiv : 1012.1908 . дои : 10.1007/s10107-011-0499-2 . ISSN 0025-5610 . S2CID 2319461 .

[:0-4] Jump up to: ^а ^б Ахмади, Амир Али; Паррило, Пабло А. (2009). «Положительно определенный полиномиальный гессиан, который не учитывает». Материалы 48-й конференции IEEE по принятию решений и управлению (CDC), проведенной совместно с 28-й китайской конференцией по управлению в 2009 году . стр. 1195–1200. дои : 10.1109/CDC.2009.5400519 . hdl : 1721.1/58871 . ISBN 978-1-4244-3871-6 . S2CID 5344338 .

[5] Блехерман, Григорий (04 октября 2009 г.). «Выпуклые формы, не являющиеся суммами квадратов». arXiv : 0910.0656 [ math.AG ].

[6] Сондерсон, Джеймс (2022). «Выпуклая форма, не являющаяся суммой квадратов». Математика исследования операций . 48 : 569–582. arXiv : 2105.08432 . дои : 10.1287/moor.2022.1273 . S2CID 234763204 .

[7] Ахмади, Амир Али; Паррило, Пабло А. (2013). «Полная характеристика разрыва между выпуклостью и SOS-выпуклостью». SIAM Journal по оптимизации . 23 (2): 811–833. arXiv : 1111.4587 . дои : 10.1137/110856010 . ISSN 1052-6234 . S2CID 16801871 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]