Przyspieszenia wielomianowe z algorytmami opartymi na programowaniu półfinałowym

Jest to kontynuacja ostatniego pytania zadanego przez A. Pala: Rozwiązywanie programów półfinałowych w czasie wielomianowym .

Nadal zastanawiam się nad faktycznym czasem działania algorytmów obliczających rozwiązanie programu półfinałowego (SDP). Jak zauważył Robin w swoim komentarzu do powyższego pytania, SDP-ów nie można ogólnie rozwiązać w czasie wielomianowym.

Okazuje się, że jeśli dokładnie zdefiniujemy nasz SDP i nałożymy warunek na to, jak dobrze ograniczony jest pierwotny możliwy do wykonania region, możemy zastosować metodę elipsoidy, aby wyznaczyć wielomian związany z czasem potrzebnym do rozwiązania SDP (patrz sekcja 3.2 w L. Lovász, Programy półfinałowe i optymalizacja kombinatoryczna ). Podana tam granica to ogólny „ czas wielomianowy ”, a tutaj interesuje mnie granica mniej zgrubna.

Motywacja pochodzi z porównania dwóch algorytmów zastosowanych do problemu separacji kwantowej (rzeczywisty problem nie ma tutaj znaczenia, więc nie przestawaj czytać klasycznych czytników!). Algorytmy są oparte na hierarchii testów, które można rzutować na SDP, a każdy test w hierarchii jest na większej przestrzeni, to znaczy rozmiar odpowiedniego SDP jest większy. Dwa algorytmy, które chcę porównać, różnią się następującymi kompromisami: w pierwszym, aby znaleźć rozwiązanie, musisz wspiąć się na większą liczbę etapów hierarchii, aw drugim kroki w hierarchii są wyższe, ale musisz wspiąć się mniej z nich. Oczywiste jest, że w analizie tego kompromisu ważny jest dokładny czas działania algorytmu zastosowanego do rozwiązania SDP. Analiza tych algorytmów została przeprowadzona przez Navascués i in. w arxiv: 0906.2731, gdzie piszą:

... złożoność czasowa SDP z zmiennymi i rozmiarem macierzy wynosi (przy niewielkim dodatkowym koszcie pochodzącym z iteracji algorytmów). $m$ $n$ $O(m^2 n^2)$

W innym artykule , w którym po raz pierwszy zaproponowano takie podejście do problemu, autorzy dają to samo ograniczenie, ale używają bardziej ostrożnego terminu „ liczba operacji arytmetycznych ” zamiast „ złożoności czasowej ”.

Moje pytanie jest dwojakie:

Który algorytm / granica to Navascués i in. odwołujący się do?
Czy mogę zastąpić wyrażenie „czas wielomianowy” w Lovászu czymś mniej szorstkim (zachowując te same założenia)?

quantum-information semidefinite-programming analysis-of-algorithms Alessandro Cosentino
źródło

Rozumiem, że metoda elipsoidy dała odpowiedzi

w błędzie addytywnym

w czasie wielomianu w

. Dla większości problemów, można przypuszczać, że

może wystarczyć.

ϵ

$\epsilon$

\log (1 / ϵ)

$\log(1/\epsilon)$

ϵ = Ω (1 / 2^{n})

$\epsilon = \Omega(1/2^n)$

Suresh Venkat,

@SureshVenkat: Zgadza się, metoda elipsoidy działa w wielomianie czasowym pod względem wielkości macierzy wejściowych, wielkości ograniczeń i

. Problem polega na tym, że w przypadku aplikacji, o której wspomniałem w pytaniu, powiedzenie „wielomian” nie wystarczy, potrzebuję bardziej precyzyjnego powiązania.

\log (1 / ϵ)

$\log(1/\epsilon)$

Alessandro Cosentino,

Odpowiedzi:

Nie znam szczegółów metody elipsoidalnej specjalnie dla programów półokreślonych, ale nawet dla programów liniowych analiza metody elipsoidalnej jest dość subtelna.

Po pierwsze, należy ograniczyć liczbę iteracji idealnego algorytmu elipsoidy. Niech być ellispoid stosowany w th iteracji algorytmu elipsoidy, i niech być jej ciężkości. W algorytmie ideał, oracle separacji / członkostwo daje półprzestrzeni który zawiera punkt optymalny , ale nie ciężkości . Następna elipsoida jest najmniejszą elipsoidą zawierającą . Dla każdego mamy $E_i$ $i$ $c_i$ $h_i$ $x^*$ $c_i$ $E_{i+1}$ $E_i\cap h_i$ $i$ , gdziejest wymiarem. Tak więc, biorąc pod uwagę rozsądne wyjścia elipsoidalne, liczba iteracji jest wielomiani. Obliczanieziwymaga (grubsza)operacje arytmetyczne. Zatem liczba operacji arytmetycznych jest również wielomianowa wi $vol(E_{i+1}) < (1-\frac{1}{n})\cdot vol(E_i)$ $n$ $n$ $\log(1/\varepsilon)$ $E_{i+1}$ $E_i$ $h_i$ $O(n^2)$ $n$ $\log(1/\varepsilon)$ .
Jednak niektóre z tych operacji arytmetycznych są pierwiastkami kwadratowymi! Wynika z tego, że współczynniki idealnej elipsoidy są nieracjonalnymi liczbami stopnia , więc nie ma nadziei na faktyczne obliczenie dokładnie w rozsądnym czasie. Zamiast tego oblicza się ścisłe przybliżenie zewnętrzne przy każdej iteracji przy użyciu arytmetyki skończonej precyzji. Grötschel, Lovász i Schrijver okazać się, że przy użyciu (powiedzmy) bity precyzji w XX iteracji jeszcze $E_i$ $2^i$ $E_{i+1}$ $\tilde{E}_i \supset E_i$ $10i$ $i$ , więc liczba iteracji wzrasta co najwyżej o stały współczynnik. Teraz jednak każda operacja arytmetyczna wtą iterację (w tym operacje przeprowadzane przez wyroczni rozdzielania) wymagarazem. $vol(\tilde E_{i+1}) < O(1-\frac{1}{n})\cdot vol(\tilde E_i)$ $i$ $O(i~\text{polylog}~i)$

$n$ $\log(1/\varepsilon)$

Jeffε
źródło

\sum_{i = 1}^{n. of iterations} O (n^{2})

$\sum_{i = 1}^{\text{n. of iterations}} O(n^2)$

\times O (i polylog i)

$\times O(i \operatorname{polylog}i)$

n

$n$

\log (1 / ϵ)

$\log(1/\epsilon)$

n

$n$

n^{2}

$n^2$ , ...).

Alessandro Cosentino,

Jeszcze jedno: czy liczba ograniczeń nie powinna pojawić się gdzieś w analizie? Czy jest to również specyficzne dla programów liniowych?

Alessandro Cosentino,

Musisz także wziąć pod uwagę czas działania wyroczni separacyjnej; tam pojawia się liczba ograniczeń. W przypadku jawnych płyt LP wyrocznia separacyjna po prostu wypróbowuje ograniczenia pojedynczo. W przypadku niejawnie reprezentowanych płyt LP jest to bardziej skomplikowane.

Jeffε