Насколько я знаю, такого исследования нет; Более того, без каких-либо нетривиальных достижений в технологии проблем с квадратами (SOS) в настоящее время не ясно, какой будет непосредственная выгода от такого исследования. (Я сосредоточусь на связи SOS, поскольку, насколько я знаю, это лучший способ решения этих общих квартичных проблем.) Это утверждение следует рассматривать в положительном свете: я считаю, что существует много глубины исследований, окружающих эти проблемы. Я буду обосновывать свои претензии несколькими способами, надеюсь, так, чтобы люди находили полезными ..
Во-первых, для большинства основных проблем обсуждаемого вами типа, SVD-соединение дает гораздо лучший решатель, чем черный ящик SOS; в частности, последний создает SDP с , где - общее количество переменных в задаче оптимизации источника (например, общее количество элементов во всех неизвестных матрицах; чтобы увидеть где я получил эти цифры, см. лекцию 10 из курса Пабло Паррило 2006 года: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization -spring-2006 / lecture-notes / lecture_10.pdf ). Это SDP, который вы никогда не захотите решить (время выполнения зависит от как(n + 22)NNN6используя средство расчета внутренних точек?), особенно если сравнивать со смехотворной скоростью решателя SVD (при использовании согласованной нотации SVD будет выглядеть как ; вы можете отменить мои вычисления, отследив количество столбцов, строк и целевого ранга, но это беда, как бы вы ни исправляли мою небрежность). В том же духе, если вы разработали специализированный алгоритм для решения задач SOS, где максимальная степень в любом полиноме равна двум: это было бы удивительно, и тогда вид опроса, который вы ищете, будет иметь большую ценность.O (N1,5)
Во-вторых, поскольку основная формулировка этих проблем выходит за рамки, можно задаться вопросом, хорошо ли решаются некоторые варианты этих проблем с помощью решателей SOS. В качестве важного примера рассмотрим проблему NMF (факторизации неотрицательной матрицы), где теперь неизвестные матрицы, по которым вы оптимизируете (в приведенной выше формулировке), должны иметь неотрицательные записи. К сожалению, если вы возьмете стандартную SDP, используемую для решения этих проблем (см., Например, заметки Пабло Паррило выше), нет способа ввести эти ограничения. (А поскольку некоторые формулировки возникающих проблем являются NP-сложными, вы бы сейчас строили схему аппроксимации; т. Е. Это может стать неприятным.) Кроме того, есть недавняя работа, в которой использовалась полиномиальная структура этой задачи для построения решателей с некоторыми гарантии: см.http://arxiv.org/abs/1111.0952 от Arora, Ge, Kannan и Moitra. Они строят несколько алгоритмов, однако, когда они решают «точную» проблему NMF (где есть точная факторизация, то есть та, которая дает объективное значение 0), они не используют решатель SOS: они используют решатель, проверяющий выполнимость «полу -алгебраические множества ", гораздо более сложная задача оптимизации, которая допускает виды ограничений, которые поднимает НМФ, но теперь с экспоненциальным временем выполнения.
Во всяком случае, чтобы подвести итог и дать некоторые дальнейшие перспективы; Так как SOS является afaik единственным решателем для квартальных задач, о которых вы говорите (то есть я не думаю, что существует специализированный квартирный решатель), я обсуждал, как эти решатели имеют лучшие альтернативы для таких квартирных проблем, которые волнуют людей. Чтобы эффективно использовать инструменты SOS здесь, вы должны были бы либо создать какой-то удивительный решатель для случая квартики (внутренние полиномы степени не более 2), либо вам нужно было бы найти способ добавить ограничения к этим задачам. В противном случае, связь с проблемами SOS, хотя и увлекательная, не дает вам много.
Вы также упоминаете, что удивлены тем, что найденная вами литература не имеет такой связи. Я думаю, что это в основном из-за новизны практических решателей SOS (хотя абстрактное рассмотрение проблем SOS уходит очень далеко) и того, что я сказал выше. Фактически, когда я впервые нашел SOS-решатели, это было из заметок и документов Паррило, и я также удивился: «Почему он не говорит о проблемах типа PCA»? Потом я проверил вышеизложенные факты и много нахмурился. Я думаю, что это также плохой признак того, что сам Паррило, насколько я могу судить, не обсуждал эти проблемы за пределами упоминания, которое вы упомянули в своей диссертации (тем временем, у него есть документы по различным расширениям, и я очень уважаю за свою работу в этой области: он, должно быть, много раз думал об этих специфических квартичных проблемах ..http://arxiv.org/abs/1111.1498 ).