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

SOS-convexity

А многомерный полином является SOS-выпуклый (или сумма квадратов выпуклых) если это Матрица Гессе ЧАС можно разложить на множители как ЧАС(Икс) = SТ(Икс)S(Икс) где S - матрица (возможно, прямоугольная), элементы которой являются полиномами от Икс.[1] Другими словами, матрица Гессе - это SOS матричный полином.

Эквивалентное определение - форма, определяемая как г(Икс,y) = yТЧАС(Икс)y это сумма квадратов форм.[2]

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

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

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

В том же году Григорий Блехерман проявил себя в неконструктивный способ, которым существуют выпуклые формы, которые не могут быть представлены в виде суммы квадратов.[5]

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

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

использованная литература

  1. ^ Хелтон, Дж. Уильям; Не, Цзяванг (2010). «Полуопределенное представление выпуклых множеств». Математическое программирование. 122 (1): 21–64. arXiv:0705.4068. Дои:10.1007 / s10107-008-0240-у. 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. ^ Ахмади, Амир Али; Ольшевский, Алексей; Parrilo, Pablo A .; Цициклис, Джон Н. (2013). «NP-трудность решения выпуклости многочленов четвертой степени и смежные проблемы». Математическое программирование. 137 (1–2): 453–476. arXiv:1012.1908. Дои:10.1007 / s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.
  4. ^ а б Ахмади, Амир Али; Паррило, Пабло А. (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.10.2009). «Выпуклые формы, не являющиеся суммами квадратов». arXiv:0910.0656 [math.AG].
  6. ^ Ахмади, Амир Али; Паррило, Пабло А. (2013). «Полная характеристика разрыва между выпуклостью и SOS-выпуклостью». SIAM Journal по оптимизации. 23 (2): 811–833. arXiv:1111.4587. Дои:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.

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