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
źródło
Odpowiedzi:
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 .
źródło
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 ).
źródło