Co można rozwiązać za pomocą programowania półfinałowego, czego nie można rozwiązać za pomocą programowania liniowego?

9

Znam programy liniowe, ponieważ mogą one rozwiązywać problemy z liniowymi funkcjami celu i ograniczeniami liniowymi. Ale co programowanie półfinalne może rozwiązać, czego programowanie liniowe nie jest w stanie? Wiem już, że programy półfinałowe są uogólnieniem programów liniowych.

Jak rozpoznać problem, który można rozwiązać za pomocą programowania półfinałowego? Jakiego typowego problemu używa się do programowania półfinałowego, którego nie można rozwiązać za pomocą programowania liniowego?

Bardzo dziękuję za każdą odpowiedź.

linear-programming convex-optimization semidefinite-programming

— użytkownik11094
źródło

2

Może możesz sprecyzować swoje pytanie? W końcu programowanie liniowe jest

P

$\mathsf{P}$ -kompletny.

— Kristoffer Arnsfelt Hansen

5

@KristofferArnsfeltHansen Nigdy nie przestaję się zastanawiać, dlaczego ludzie wciąż poruszają ten fakt w podobnych dyskusjach. P-kompletność jest nieistotna, chyba że mówimy o oddzieleniu P od L lub NC - jeśli mówimy o politytime, wszystko w P jest „P-zupełne”. Aby zasugerować odpowiedź na OP: po naprawieniu liniowego kodowania problemu (tj. Napisaniu jako optymalizacja funkcji liniowej na polytopie) warto zapytać, czy polisize LP / SDP może rozwiązać problem.

— Sasho Nikolov,

18

Typowym problemem jest MaxCut: wyprowadza cięcie na wykresie, który (w przybliżeniu) maksymalizuje liczbę ciętych krawędzi. Goemans i Williamson wykazali, że SDP przybliża wartość MaxCut do wartości co najmniej 0,878. Ostatnio Chan, Lee, Raghavendra i Steurer wykazali, że dla naturalnego liniowego kodowania problemu MaxCut wszystkie LP wielomianowe osiągają aproksymację nie lepszą niż 0,5.

Trudno powiedzieć w zwięzły sposób, jakie problemy zwykle korzystają z SDP. Systematyczne podejście do konstruowania relaksacji SDP opiera się na hierarchiach, z których najpotężniejszą jest hierarchia Lasserre: miłe wprowadzenie znajduje się w ankiecie Rothvoßa . Do tej pory istnieje zbyt wiele przykładów sukcesów SDP w optymalizacji pod względem listy. Ponadto Raghavendra wykazał, że jeden konkretny SDP daje najlepsze przybliżenie wszystkich problemów MaxCSP, jeśli hipoteza Unikalnych gier jest prawdziwa.

Sprawdź książki Gaertnera i Matouseka , rozdziały 6 i 13 książki Willimsona i Shmoysa , ankieta Lovasz .

— Sasho Nikolov
źródło

12

W przypadku wielu problemów optymalizacji kombinatorycznej (na przykład Max-Cut) programowanie półfinałowe daje znacznie silniejsze relaksacje niż relaksacja LP formuł IP. Pozwala to na projektowanie algorytmów aproksymacyjnych i dokładnych algorytmów, które są bardziej wydajne niż ich odpowiedniki liniowe ze względu na lepszą jakość granic. Przykłady można znaleźć w pracy habilitacyjnej Christopha Helmberga , w tej ankiecie i na stronie kursu .

Kolejną niedawną sekwencją spektakularnych wyników wykorzystujących programowanie półfinałów jest zastosowanie algebry flag Razborova do udowodnienia wyników problemów typu Turan (zobacz tę ankietę i projekt flagowy ).

— Thomas Kalinowski
źródło