Jakie klasy programów matematycznych można rozwiązać dokładnie lub w przybliżeniu w czasie wielomianowym?

31

Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie rozwiązać, ale uważam, że ich definicja „wydajnego” nie pokrywa się z definicją TCS.

To pytanie bardzo mnie niepokoi w ciągu ostatnich kilku lat i nie mogę znaleźć na to jednoznacznej odpowiedzi. Mam nadzieję, że pomożesz mi rozwiązać to raz na zawsze: jakie klasy posłów można rozwiązać dokładnie w czasie wielomianowym i za pomocą jakich środków; a co wiadomo o przybliżeniu optymalnego rozwiązania MP, którego nie możemy rozwiązać dokładnie w czasie wielomianowym?

Poniżej podaję niepełną odpowiedź na to pytanie, która w niektórych miejscach może być również niepoprawna, więc mam nadzieję, że możesz mnie zweryfikować i poprawić w punktach, w których się mylę. Zawiera także pytania, na które nie mogę odpowiedzieć.

Wszyscy wiemy, że programowanie liniowe można rozwiązać dokładnie w czasie wielomianowym, uruchamiając metodę elipsoidy lub metodę punktu wewnętrznego, a następnie uruchamiając procedurę zaokrąglania. Programowanie liniowe można nawet rozwiązać w postaci wielomianu czasowego w liczbie zmiennych w obliczu rodziny LP z dowolną dużą ilością wiązań liniowych, o ile można dla niego zapewnić „wyrocznię separacyjną”: algoritm, który, biorąc pod uwagę punkt , albo określa, czy ten punkt jest wykonalny, albo wysyła hiperpłaszczyznę, która oddziela punkt od wielościanu wykonalnych punktów. Podobnie, liniowe programowanie w wielomianie czasowym w liczbie ograniczeń w obliczu rodziny LP z dowolną bardzo dużą liczbą zmiennych, jeśli zapewnia się algorytm separacji dla podwójnych tych LP.

Metoda elipsoidy jest również w stanie rozwiązać programy kwadratowe w czasie wielomianowym, w przypadku gdy macierz w funkcji celu jest dodatnia (pół?) Określona. Podejrzewam, że stosując sztuczkę separacyjną wyroczni, możemy w niektórych przypadkach zrobić to również, jeśli mamy do czynienia z niewiarygodną liczbą ograniczeń. Czy to prawda?

Ostatnio programowanie semidefinite (SDP) zyskało dużą popularność w społeczności TCS. Można je rozwiązać z dowolną precyzją, stosując metody punktów wewnętrznych lub metodę elipsoidy. Myślę, że SDP nie można rozwiązać dokładnie ze względu na problem polegający na tym, że pierwiastków kwadratowych nie można dokładnie obliczyć. (?) Czy byłoby zatem poprawne, jeśli powiem, że istnieje FPTAS dla SDP? Nigdzie tego nie widziałem, więc prawdopodobnie nie jest to właściwe. Ale dlaczego?

Możemy dokładnie rozwiązać LP i SDP z dowolną precyzją. Co z innymi klasami programów stożkowych? Czy możemy rozwiązywać programy stożkowe drugiego rzędu z dowolną dokładnością, stosując metodę elipsoidy? Nie wiem

Na jakich klasach posłów możemy zastosować metodę elipsoidy? Jakie właściwości musi spełnić taki MP, aby można było udzielić odpowiedzi z dowolną precyzją i jakich dodatkowych właściwości potrzebujemy, aby uzyskać dokładne rozwiązanie w czasie wielomianowym? Te same pytania dotyczące metod punktów wewnętrznych.

Aha, i na koniec, co powoduje, że ciągłe optymalizatory mówią, że programy wypukłe można skutecznie rozwiązać? Czy to prawda, że ​​odpowiedź na wypukły program o dowolnej dokładności można znaleźć w czasie wielomianowym? Nie wierzę, więc w jakich aspektach ich definicja „wydajnego” różni się od naszej?

Każdy wkład jest mile widziany! Z góry dziękuję.

Bart
źródło
6
Tytuł tego pytania jest o wiele za szeroki; wydaje się, że tak naprawdę chcesz wiedzieć, czy programy wypukłe można naprawdę rozwiązać w czasie wielomianowym.
Peter Shor
Oddelegowany. Bart, może potrafisz podzielić rzeczy na konkretne pytania?
Suresh Venkat
Peter i Suresh, dziękuję za te sugestie. Z tego, co napisałem, wynika, że ​​jestem zainteresowany nie tylko pytaniem, czy programy wypukłe można rozwiązać lub aproksymować w czasie wieloczasowym. Zasadniczo interesują mnie ograniczenia metod elipsoidy i punktów wewnętrznych i mam nadzieję, że ktoś wie dokładnie, na których klasach posłów pracuje wydajnie. Pytam o to, ponieważ obecna literatura na ten temat nie jest dla mnie jasna (dla mnie).
Bart
Osobiście uważam, że dobrze byłoby mieć dobry przegląd tego w jednym miejscu (np. Jako odpowiedź na to pytanie dotyczące wymiany stosów). Również dla mnie wydaje się to dość spójne pytanie. Ponieważ jednak jestem nowy w stosach wymiany, nie znam tutaj kultury i etyki ... więc jeśli nalegasz, postaram się dowiedzieć, jak podzielić to pytanie na wiele mniejszych pytań.
Bart
1
Myślę, że zakres tego pytania jest o wiele za szeroki, aby uzyskać odpowiedź. Dobrym pytaniem byłyby granice metod elipsoidy i punktów wewnętrznych, a to, co można zrobić dla programów wypukłych, jest dobrym pytaniem, ale jeśli nie określisz typu algorytmu lub typu programu, w zasadzie pytasz dla podsumowania całego pola ciągłej optymalizacji w odpowiedzi, a jest to prawie niemożliwe. To nie jest małe pole. Jeśli jednak pozostawisz swoje pytanie, jest całkiem możliwe, że otrzymasz kolejną dobrą częściową odpowiedź.
Peter Shor

Odpowiedzi:

18

Mogę odpowiedzieć na tę część:

Czy to byłoby poprawne, jeśli powiem, że istnieje FPTAS dla SDP? Nigdzie tego nie widziałem, więc prawdopodobnie nie jest to właściwe. Ale dlaczego?

Stwierdzenie jest poprawne, ale często go nie widzimy, ponieważ mocniejsze stwierdzenie jest ważne i jest ważniejsze niż to osłabienie.

FPTAS jest algorytmem czasu wielomianowego, który, biorąc pod uwagę problem i parametr dokładności 1 k , daje rozwiązanie przybliżone (1 + 1 / k ).

Jednak w przypadku SDP metoda elipsoidalna i metoda punktu wewnętrznego zapewniają algorytmy wielomianowe, które, biorąc pod uwagę problem i parametr dokładności 1 k , dają rozwiązanie przybliżone (1 + 2 - k ). Zauważ, że współczynnik aproksymacji jest znacznie lepszy niż wymagany dla FPTAS.

Tsuyoshi Ito
źródło
To wymaga nieco więcej uwagi, ponieważ metoda elipsoidy i metoda punktu wewnętrznego wymagają dodatkowych warunków do działania w czasie wielomianowym.
Yoshio Okamoto
Dzięki za to, Tsuyoshi! Yoshio, czy możesz wyjaśnić, co przez to rozumiesz? Czy naprawdę masz na myśli, że istnieją warunki dotyczące konkretnego SDP, ponieważ w przeciwnym razie SDP nie może być zbliżony w taki sposób w czasie wielu? W tym przypadku jest to dla mnie niespodzianka i chciałbym wiedzieć o tych warunkach. Dzięki.
Bart
@Bart: Na przykład, jeśli spojrzysz na notatki z wykładów autorstwa Lovasz cs.elte.hu/~lovasz/semidef.ps , możesz znaleźć Twierdzenie 3.7 (strona 19) mówi o czasie wykonywania metody elipsoidy dla minimalizacji wypukłości . Tam narzucone są pewne założenia techniczne.
Yoshio Okamoto
4
rRlogR/r
Wielkie dzięki za to. To odpowiada bardzo dużej części mojego pytania. Wydaje się, że ta wiedza może być bardzo przydatnym narzędziem dla teoretycznych informatyków, a mimo to wydaje mi się, że wcale nie jest dobrze znana i prawie nie ma jej wcale. Dziwne.
Bart