Это продолжение недавнего вопроса, заданного А. Палом: Решение полуопределенных программ за полиномиальное время .
Я все еще ломаю голову над фактическим временем выполнения алгоритмов, которые вычисляют решение полуопределенной программы (SDP). Как отметил Робин в своем комментарии к вышеуказанному вопросу, SDP не могут быть решены за полиномиальное время в целом.
Оказывается, что если мы тщательно определим наш SDP и наложим условие на то, насколько хорошо ограничена первичная выполнимая область, мы можем использовать метод эллипсоидов, чтобы задать полиномиальную границу времени, необходимого для решения SDP (см. Раздел 3.2. в L. Lovász, Полуопределенные программы и комбинаторная оптимизация ). Приведенная оценка представляет собой общее « полиномиальное время », и здесь меня интересует менее грубая оценка.
Мотивация исходит из сравнения двух алгоритмов, используемых для проблемы квантовой отделимости (актуальная проблема здесь не актуальна, поэтому не переставайте читать классических читателей!). Алгоритмы основаны на иерархии тестов, которые могут быть преобразованы в SDP, и каждый тест в иерархии находится на большем пространстве, то есть размер соответствующего SDP больше. Два алгоритма, которые я хочу сравнить, отличаются следующим компромиссом: в первом, чтобы найти решение, вам нужно подняться на большее количество ступеней иерархии, а во втором - ступени иерархии выше, но вам нужно подняться меньше. их. Ясно, что при анализе этого компромисса важно точное время выполнения алгоритма, используемого для решения SDP. Анализ этих алгоритмов сделан Navascués et al. в архиве: 0906.2731где пишут:
... временная сложность SDP с переменными и размером матрицы n равна O ( m 2 n 2 ) (с небольшими дополнительными затратами, вытекающими из итерации алгоритмов).
В другой статье , где этот подход к проблеме был впервые предложен, авторы дают ту же оценку, но они используют более осторожный термин « число арифметических операций » вместо « сложность времени ».
У меня вопрос двоякий:
- Какой алгоритм / границы являются Navascués et al. ссылаясь на?
- Могу ли я заменить выражение «полиномиальное время» в Lovász на что-то менее грубое (придерживаясь тех же предположений)?
источник
Ответы:
Я не знаком с деталями метода эллипсоидов специально для полуопределенных программ, но даже для линейных программ анализ метода эллипсоидов довольно тонок.
Во-первых, необходимо ограничить число итераций алгоритма идеального эллипсоида. Пусть будет эллипсоидом, использованным в i- й итерации алгоритма эллипсоида, и пусть c i будет его центроидом. В идеальном алгоритме оракул разделения / членства дает вам полупространство h i, которое содержит оптимальную точку x ∗, но не центроид c i . Следующий эллипсоид E i + 1 является наименьшим эллипсоидом, содержащим E i ∩ h i . Для каждого я имеемЕя я ся чася Икс* ся Ея + 1 Ея∩ чя я , гдепесть размерность. Таким образом, при разумном начальном эллипсоиде число итераций является полиномиальным поnиlog(1/ε). ВычислениеEi+1изEiиhiтребует (грубо)O(n2)арифметических операций. Таким образом, число арифметических операций также полиномиально поnиlog(v o l ( Eя + 1) < ( 1 - 1N) ⋅ V о л ( Ея) N N журнал( 1 / ε ) Ея + 1 Ея чася O ( n2) N .журнал( 1 / ε )
Однако некоторые из этих арифметических операций являются квадратными корнями! Отсюда следует, что коэффициенты идеального эллипсоида являются иррациональными числами степени 2 i , и поэтому нет никакой надежды на то, что фактически вычислить E i + 1 точно в любое разумное время. Таким образом, вместо этого вычисляется близкое внешнее приближение ˜ E i ⊃ E i на каждой итерации с использованием арифметики конечной точности. Grötschel, Lovasz и Schrijver доказывают, что если в i- й итерации использовать (скажем) 10 i бит точности , у нас все еще будет v o l (Ея 2я Ея + 1 Е~я⊃ Eя 10 я я , так что число итераций возрастаетболеена фактор постоянной. Но теперь каждая арифметическая операция во времяi-й итерации (включая операции, выполняемые оракулом разделения) требует времениO(ipolylogi).v o l ( E~я + 1) < O ( 1 - 1)N) ⋅ V о л ( Е~я) я O ( я полилог я )
В целом, общее время работы метода эллипсоидов очень приблизительно равно квадрату числа арифметических операций. Поскольку число арифметических операций является полиномиальным по и log ( 1 / ε ) , то же самое относится и к времени выполнения.N журнал( 1 / ε )
источник