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ę.
Odpowiedzi:
Mogę odpowiedzieć na tę część:
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.
źródło
Nie wiem, czy wszystkie problemy wypukłe są w P, ale mogę odpowiedzieć na pokrewne pytanie: optymalizacja niep wypukła jest trudna NP. Zobacz „Programowanie kwadratowe z jedną ujemną wartością własną jest trudne dla NP” .
źródło