Rozwiązywanie programów półfinałowych w czasie wielomianowym

Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym, pod warunkiem, że możemy dla nich zaprojektować wielomianową wyrocznię z separacją czasu.

Co z programami półfinałowymi (SDP)? Jakie klasy SDP można rozwiązać dokładnie w czasie wielomianowym? Kiedy SDP nie da się dokładnie rozwiązać, czy zawsze możemy zaprojektować FPTAS / PTAS do jego rozwiązania? Jakie są warunki techniczne, w których można to zrobić? Czy możemy rozwiązać SDP z wykładniczą liczbą zmiennych / ograniczeń w czasie wielomianowym, jeśli możemy zaprojektować dla niego wielomianową wyrocznię z separacją czasu?

Czy możemy skutecznie rozwiązać SDP występujące w kombinatorycznych problemach optymalizacyjnych (MAX-CUT, kolorowanie grafów)? Jeśli możemy rozwiązać tylko w czynnikiem, nie będzie to miało wpływ na stałych algorytmów aproksymacji (jak współczynnik 0,878 dla Goemans-Williamson MAX-CUT Algorithm)? $1+\epsilon$

Wszelkie dobre referencje będą mile widziane.

linear-programming semidefinite-programming convex-optimization

— Arindam Pal
źródło

W rzeczywistości metoda ta działa ogólnie na programowanie wypukłe

— Suresh Venkat

Istnieją co najmniej dwa powody, dla których nie można rozwiązać ogólnego SDP w czasie wielomianowym. (1) Istnieją SDP, których rozwiązanie ma wielkość wykładniczą. (2) SDP mogą kodować sumę problemu pierwiastków kwadratowych, o którym nie wiadomo, że jest rozwiązaniem wielomianowym.

— Robin Kothari,

@RobinKothari W przypadku SDP, zwykle „rozwiązany w czasie wielomianowym” jest zastępowany przez „wchodzi w

(dodatek) do OPT w czasie wielomianowym w

” IIRC. ps w jaki sposób SDP koduje pierwiastek kwadratowy?

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

— Suresh Venkat

@SureshVenkat: Powiedzmy, że mamy macierz 2x2 z wpisami [ab; Płyta CD]. Załóżmy, że jest to dodatnia półfinał id = 1. Oznacza to, że b = c oraz a> = b ^ 2. Więc b jest górną granicą pierwiastka kwadratowego z. Teraz możemy zmaksymalizować sumę kilku takich b. Optymalna wartość będzie sumą pierwiastków kwadratowych odpowiednich a.

— Robin Kothari,

To nie jest multiplikatywne, ale addytywne. Ponadto, en.wikipedia.org/wiki/Semidefinite_programming#Al Algorytmy

— Suresh Venkat

Metody elipsoidalne i metody punktów wewnętrznych można rozszerzyć również w celu rozwiązania SDP. Szczegółowe informacje można znaleźć w standardowych tekstach SDP. Tu jest jeden:

Programowanie półfinałowe . Vandenberge i Stephen Boyd, 1996.

— Jagadish
źródło

Miłe referencje Jagadish.

— Arindam Pal

Miłe referencje też! Dzięki! Czy zastanawiasz się, mówiąc, że algorytm wielomianowy rozwiązujący SDP, czy algorytmy rozwiązują optymalne rozwiązanie, dokładnie czy w przybliżeniu?

— StackExchange dla wszystkich