Problem typu LP - LP-type problem

W badaniu algorytmów , problemem PR-type (zwany także uogólnione Program liniowy ) jest problem optymalizacji , że akcje niektórych właściwości z niskowymiarowych programów liniowych i które mogą być rozwiązane przez podobnych algorytmów. Problemy typu LP zawierają wiele ważnych problemów optymalizacyjnych, które same w sobie nie są programami liniowymi, np. problem znajdowania najmniejszego okręgu zawierającego dany zbiór punktów płaskich. Można je rozwiązywać kombinacją algorytmów losowych w czasie, który jest liniowy pod względem liczby elementów definiujących problem i podwykładniczy pod względem wymiaru problemu.

Definicja

Problemy typu LP zostały zdefiniowane przez Sharira i Welzla (1992) jako problemy, w których jako dane wejściowe podano skończony zbiór S elementów oraz funkcję f, która odwzorowuje podzbiory S na wartości z całkowicie uporządkowanego zbioru. Funkcja musi spełniać dwie kluczowe właściwości:

  • Monotoniczność: dla każdych dwóch zbiorów A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Lokalność: dla każdych dwóch zbiorów A ⊆ B ⊆ S i każdego elementu x w S , jeśli f ( A ) = f ( B ) = f ( A ∪ { x } ) , to f ( A ) = f ( B ∪ { x }) .

Podstawę z problemem LP typu jest zestaw B ⊆ S z właściwości, co podzbiorem B ma mniejszą wartość f niż B siebie, a wymiar (lub kombinatorycznej wymiaru ) od problemem PR typu jest zdefiniowana być maksymalną kardynalnością podstawy.

Zakłada się, że algorytm optymalizacji może oceniać funkcję f tylko na zbiorach, które same są bazą lub które powstają przez dodanie do bazy pojedynczego elementu. Alternatywnie, algorytm może być ograniczony do dwóch podstawowych operacji: testu naruszenia, który określa, dla bazy B i elementu x, czy f ( B ) = f ( B ∪ { x } ) , oraz obliczenia bazy, które (z tym samym input) znajduje bazę B ∪ { x }. Zadaniem algorytmu jest obliczenie f ( S ) tylko przy użyciu tych ograniczonych ocen lub prymitywów.

Przykłady i zastosowania

Kulki Lp

Program liniowy może być zdefiniowany przez układ d nieujemnych zmiennych rzeczywistych , podlegających n liniowym ograniczeniom nierówności, wraz z nieujemną liniową funkcją celu, która ma zostać zminimalizowana. Można to umieścić w ramach problemów typu LP, pozwalając S być zbiorem ograniczeń i zdefiniować f ( A ) (dla podzbioru A ograniczeń) jako minimalną wartość funkcji celu mniejszego programu liniowego zdefiniowanego przez . Przy odpowiednich ogólnych założeniach dotyczących pozycji (aby uniknąć wielu punktów rozwiązania mających tę samą optymalną wartość funkcji celu), spełnia to wymagania monotoniczności i lokalności problemu typu LP i ma wymiar kombinatoryczny równy liczbie d zmiennych. Podobnie program całkowitoliczbowy (składający się ze zbioru ograniczeń liniowych i liniowej funkcji celu, jak w programie liniowym, ale z dodatkowym ograniczeniem, że zmienne muszą przyjmować tylko wartości całkowite) spełnia zarówno monotoniczność, jak i lokalność LP -typ problemu, przy tych samych ogólnych założeniach dotyczących pozycji, jak dla programów liniowych. Twierdzenia Bella (1977) i Scarfa (1977) pokazują, że dla programu całkowitoliczbowego ze zmiennymi d , wymiar kombinatoryczny wynosi co najwyżej  2 d .

Wiele naturalnych problemów optymalizacyjnych w geometrii obliczeniowej jest typu LP:

Image
Problem z najmniejszym okręgiem
  • Problem najmniejszego okręgu to problem znalezienia minimalnego promienia okręgu zawierającego dany zbiór n punktów na płaszczyźnie. Spełnia monotoniczność (dodanie kolejnych punktów może tylko powiększyć okrąg) i lokalność (jeśli najmniejszy okrąg dla zbioru A zawiera B i x , to ten sam okrąg zawiera również B ∪ { x }). Ponieważ najmniejszy okrąg jest zawsze określony przez jakieś trzy punkty, problem najmniejszego koła ma kombinatoryczny wymiar trzeci, mimo że jest zdefiniowany przy użyciu dwuwymiarowej geometrii euklidesowej. Mówiąc bardziej ogólnie, najmniejsza obejmująca kulę punktów w wymiarach d tworzy problem typu LP o wymiarze kombinatorycznym d + 1 . Problem najmniejszych okręgów można uogólnić na najmniejszą kulkę zawierającą zestaw kulek, na najmniejszą kulkę, która dotyka lub otacza każdą z kulek, na problem ważony z jednym środkiem lub na podobne problemy z mniejszą kulą obejmującą w innych sytuacjach. Przestrzenie euklidesowe, takie jak przestrzeń o odległościach określonych przez dywergencję Bregmana . Powiązany problem ze znalezieniem najmniejszej obejmującej elipsoidy jest również problemem typu LP, ale o większym wymiarze kombinatorycznym, d ( d + 3)/2 .
  • Niech K 0 , K 1 , ... będzie ciągiem n zbiorów wypukłych w d- wymiarowej przestrzeni euklidesowej i załóżmy, że chcemy znaleźć najdłuższy przedrostek tego ciągu, który ma wspólny punkt przecięcia. Można to wyrazić jako problem typu LP, w którym f ( A ) = − i gdzie K i jest pierwszym elementem A , który nie należy do przecinającego się przedrostka A , oraz gdzie f ( A ) = − n jeśli istnieje nie jest takim członkiem. Kombinatoryczny wymiar tego systemu to d + 1 .
  • Załóżmy, że otrzymaliśmy zbiór prostokątnych pudełek ustawionych względem osi w trójwymiarowej przestrzeni i chcemy znaleźć linię skierowaną do dodatniego oktantu przestrzeni, która przecina wszystkie pudła. Można to wyrazić jako problem typu LP o kombinatorycznym wymiarze 4.
  • Problem znajdowania najbliższej odległości między dwoma politopami wypukłymi , określonych przez ich zbiory wierzchołków, można przedstawić jako problem typu LP. W tym ujęciu zbiór S jest zbiorem wszystkich wierzchołków w obu politopach, a wartość funkcji f ( A ) jest negacją najmniejszej odległości między wypukłymi kadłubami dwóch podzbiorów A wierzchołków w dwóch politopach. Kombinatoryczny wymiar problemu to d +1, jeśli dwa wielotopy są rozłączne, lub d +2, jeśli mają niepuste przecięcie.
  • Niech S = { f 0 , f 1 , ... } będzie zbiorem funkcji quasiwypukłych . Wtedy punktowe maksimum max i f i jest samo w sobie quasi-wypukłe, a problem znalezienia minimalnej wartości max i f i jest problemem typu LP. Ma wymiar kombinatoryczny co najwyżej 2 d + 1 , gdzie d jest wymiarem dziedziny funkcji, ale dla funkcji wystarczająco gładkich wymiar kombinatoryczny jest mniejszy, co najwyżej d + 1 . Wiele innych problemów typu LP można również wyrazić za pomocą funkcji quasi-wypukłych w ten sposób; Na przykład, najmniejszy błąd zakrywające koła jest problem minimalizacji max I K I w którym każdy z funkcji f i mierzy odległość euklidesową z tych pięciu punktów.

Problemy typu LP zostały również wykorzystane do określenia optymalnych wyników niektórych gier w algorytmicznej teorii gier , poprawy rozmieszczenia wierzchołków w siatkach metody elementów skończonych , rozwiązywania problemów z lokalizacją obiektu , analizy złożoności czasowej niektórych algorytmów wyszukiwania w czasie wykładniczym i rekonstrukcji trójwymiarowe pozycje obiektów z ich dwuwymiarowych obrazów.

Algorytmy

Seidela

Seidel (1991) podał algorytm niskowymiarowego programowania liniowego, który można dostosować do struktury problemu typu LP. Algorytm Seidela przyjmuje jako dane wejściowe zbiór S i oddzielny zbiór X (początkowo pusty) elementów, o których wiadomo, że należą do bazy optymalnej. Następnie analizuje pozostałe elementy jeden po drugim w losowej kolejności, wykonując testy naruszeń dla każdego z nich i, w zależności od wyniku, wykonując rekurencyjne wywołanie tego samego algorytmu z większym zestawem znanych elementów bazowych. Może być wyrażony następującym pseudokodem: 

function seidel(S, f, X) is
    R := empty set
    B := X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B := seidel(R, f, basis(X ∪ {x}))
        R := R ∪ {x}
    return B

Na problem z kombinatorycznej wymiaru d , test naruszenie w I th iteracji algorytmu nie tylko wtedy, gdy x jest jednym z d - | X | pozostałe elementy bazowe, co dzieje się z co najwyżej prawdopodobieństwem ( d − | X |)/ i . Na podstawie tego obliczenia można wykazać, że ogólna oczekiwana liczba testów naruszeń wykonywanych przez algorytm wynosi O( d ! n) , liniowa w n, ale gorsza niż wykładnicza w d .

Clarkson

Clarkson (1995) definiuje dwa algorytmy, algorytm rekurencyjny i algorytm iteracyjny, dla programowania liniowego opartego na losowych technikach próbkowania i sugeruje kombinację tych dwóch, która wywołuje algorytm iteracyjny z algorytmu rekurencyjnego. Algorytm rekurencyjny wielokrotnie wybiera losowe próbki, których rozmiar jest w przybliżeniu pierwiastkiem kwadratowym z rozmiaru wejściowego, rekurencyjnie rozwiązuje próbkowany problem, a następnie wykorzystuje testy naruszeń, aby znaleźć podzbiór pozostałych elementów, który musi zawierać co najmniej jeden element bazowy: 

function recursive(S, f) is
    X := empty set
    repeat
        R := a random subset of S with size d√n
        B := basis for R ∪ X, computed recursively
        V := {x | f(B) ≠ f(B ∪ {x})}
        X := X ∪ V
    until V is empty
    return B

W każdej iteracji oczekiwany rozmiar V to O( √ n ) , a gdy V jest niepuste, zawiera co najmniej jeden nowy element ostatecznej bazy S . Dlatego też wykonuje algorytm co najwyżej d iteracji, z których każdy wykonuje n testy naruszenie oraz stanowi jeden rekurencyjne połączenia na subproblem o rozmiarze O ( d √ n ) .

Iteracyjny algorytm Clarksona przypisuje wagi każdemu elementowi S , początkowo wszystkie są równe. Następnie wybiera losowo zbiór R składający się z 9 d 2 elementów z S i oblicza zbiory B i V jak w poprzednim algorytmie. Jeśli całkowita waga V jest co najwyżej 2/(9 d − 1) razy większa od całkowitej wagi S (co dzieje się ze stałym prawdopodobieństwem), to algorytm podwaja wagi każdego elementu V , i jak poprzednio powtarza ten proces do V staje się pusty. W każdej iteracji można wykazać, że waga optymalnej bazy rośnie szybciej niż całkowita waga S , z czego wynika, że ​​algorytm musi zakończyć się w O(log n ) iteracjach.

Używając algorytmu rekurencyjnego do rozwiązania danego problemu, przełączając się na algorytm iteracyjny dla jego wywołań rekurencyjnych, a następnie przełączając się ponownie na algorytm Seidela dla wywołań wykonywanych przez algorytm iteracyjny, można rozwiązać dany problem typu LP za pomocą O( dn + d ! d O(1) log n ) testy naruszeń.

W przypadku zastosowania do programu liniowego, algorytm ten może być interpretowany jako metoda dual simplex . Z pewnymi dodatkowymi prymitywami obliczeniowymi poza testem naruszenia i podstawowymi prymitywami obliczeniowymi, metoda ta może być deterministyczna.

Matoušek, Sharir i Welzl

Matoušek, Sharir i Welzl (1996) opisują algorytm, który wykorzystuje dodatkową właściwość programów liniowych, nie zawsze posiadaną przez inne problemy typu LP, polegającą na tym, że wszystkie bazy mają tę samą kardynalność. Jeśli problem typu LP nie ma tej właściwości, można go uzyskać, dodając d nowych elementów fikcyjnych i modyfikując funkcję f, aby zwrócić uporządkowaną parę jego starej wartości f ( A ) i liczby min ( d , | A | ) , uporządkowane leksykograficznie .

Zamiast dodawać elementy S pojedynczo lub znajdować próbki elementów, Matoušek, Sharir i Welzl (1996) opisują algorytm, który usuwa elementy pojedynczo. Na każdym kroku utrzymuje bazę C, która początkowo może być zbiorem elementów fikcyjnych. Można go opisać następującym pseudokodem: 

function msw(S, f, C) is
    if S = C then
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}) then
        B := basis(B ∪ {x})
        B := msw(S, f, B)
    return B

W większości rekurencyjnych wywołań algorytmu test naruszenia kończy się pomyślnie, a instrukcja if jest pomijana. Jednak z małym prawdopodobieństwem test na naruszenie kończy się niepowodzeniem i algorytm wykonuje dodatkowe obliczenia bazowe, a następnie dodatkowe wywołanie rekurencyjne. Jak pokazują autorzy, oczekiwany czas działania algorytmu jest liniowy w n i wykładniczy w pierwiastku kwadratowym z d log n . Łącząc tę ​​metodę z rekurencyjnymi i iteracyjnymi procedurami Clarksona, te dwie formy zależności czasowej można od siebie oddzielić, co skutkuje algorytmem wykonującym testy naruszenia O( dn ) w zewnętrznym algorytmie rekurencyjnym oraz liczbą wykładniczą w pierwiastek kwadratowy z d log d na niższych poziomach algorytmu.

Wariacje

Optymalizacja z wartościami odstającymi

Matoušek (1995) rozważa odmianę problemów optymalizacyjnych typu LP, w których jeden jest zadany, wraz ze zbiorem S i funkcją celu f , liczbą k ; zadaniem jest usunięcie k elementów z S , aby funkcja celu na pozostałym zbiorze była jak najmniejsza. Na przykład, gdy zastosujemy do problemu najmniejszych okręgów, da to najmniejszy okrąg, który zawiera wszystko oprócz k danego zestawu punktów płaskich. Pokazuje, że dla wszystkich niezdegenerowanych problemów typu LP (czyli takich, w których wszystkie zasady mają różne wartości) problem ten można rozwiązać w czasie O( nk d ) , rozwiązując zbiór O( k d ) LP -typowe problemy zdefiniowane przez podzbiory S .

Ukryte problemy

Niektóre problemy optymalizacji geometrycznej mogą być wyrażone jako problemy typu LP, w których liczba elementów w sformułowaniu typu LP jest znacznie większa niż liczba wartości danych wejściowych dla problemu optymalizacji. Jako przykład rozważmy zbiór n punktów na płaszczyźnie, z których każdy porusza się ze stałą prędkością. W dowolnym momencie średnica tego systemu jest maksymalną odległością między dwoma jego punktami. Problem znalezienia czasu, w którym średnica jest zminimalizowane mogą być formułowane jako minimalizując maksymalnie punktowo o O ( N 2 ) funkcji quasiconvex, jednej dla każdej pary punktów pomiarowych odległość euklidesową między parą w funkcji czasu. Można go więc rozwiązać jako problem typu LP o wymiarze kombinatorycznym dwa na zbiorze O( n 2 ) elementów, ale zbiór ten jest znacznie większy niż liczba punktów wejściowych.

Chan (2004) opisuje algorytm rozwiązywania niejawnie zdefiniowanych problemów typu LP, takich jak ten, w którym każdy element typu LP jest określony przez k- krotkę wartości wejściowych, dla pewnej stałej k . Aby zastosować jego podejście, musi istnieć algorytm decyzyjny, który może określić, dla danej bazy B typu LP i zestawu S o n wartości wejściowych, czy B jest bazą problemu typu LP określonego przez S .

Algorytm Chana wykonuje następujące kroki:

  • Jeśli liczba wartości wejściowych jest poniżej pewnej wartości progowej, znajdź zestaw elementów typu LP, który określa i rozwiąż wynikowy problem jawnego typu LP.
  • W przeciwnym przypadku, partycja wartości wejściowe z odpowiednią liczbą większą niż k o równej wielkości podzbiorów S I .
  • Jeśli f jest funkcją celu dla niejawnie zdefiniowanego problemu typu LP do rozwiązania, zdefiniuj funkcję g, która odwzorowuje kolekcje podzbiorów S i na wartość f na unii kolekcji. Następnie zbiór podzbiorów Si i sama funkcja celu g definiuje problem typu LP o tym samym wymiarze, co problem niejawny do rozwiązania.
  • Rozwiąż (jawny) problem typu LP zdefiniowany przez g za pomocą algorytmu Clarksona, który wykonuje liniową liczbę testów naruszeń i polilogarytmiczną liczbę baz ocen. Oceny bazowe dla g mogą być wykonane przez rekurencyjne wywołania algorytmu Chana, a testy naruszeń mogą być wykonane przez wywołania algorytmu decyzyjnego.

Przy założeniu, że algorytm decyzyjny zajmuje czas O( T ( n )) , który rośnie co najmniej wielomianowo w funkcji rozmiaru wejściowego n , Chan pokazuje, że próg przejścia na jawną formułę LP i liczbę podzbiorów w partycji można wybrać w taki sposób, aby niejawny algorytm optymalizacji typu LP działał również w czasie O( T ( n )) .

Na przykład, dla minimalnej średnicy ruchomych punktów, algorytm decyzyjny musi tylko obliczyć średnicę zbioru punktów w ustalonym czasie, problem, który można rozwiązać w czasie O( n log n ) przy użyciu techniki suwmiarek obrotowych . Dlatego algorytm Chana do znalezienia czasu, w którym średnica jest minimalizowana, również zajmuje czas O( n log n ) . Chan używa tej metody, aby znaleźć punkt o maksymalnej głębokości Tukeya wśród danego zbioru n punktów w d- wymiarowej przestrzeni euklidesowej, w czasie O( n d − 1 + n log n ) . Podobną technikę zastosowali Braß, Heinrich-Litan i Morin (2003) w celu znalezienia punktu maksymalnej głębokości Tukeya dla rozkładu jednostajnego na wielokącie wypukłym.

Historia i związane z nią problemy

Odkrycie algorytmów czasu liniowego dla programowania liniowego i obserwacja, że ​​te same algorytmy mogą w wielu przypadkach być użyte do rozwiązywania problemów optymalizacji geometrycznej, które nie były programami liniowymi, sięga co najmniej od Megiddo ( 1983 , 1984 ), który podał liniowy oczekiwany czas algorytm zarówno dla trzech zmiennych programów liniowych, jak i problemu najmniejszego okręgu. Jednak Megiddo sformułował uogólnienie programowania liniowego geometrycznie, a nie kombinatorycznie, jako problem optymalizacji wypukłej, a nie abstrakcyjny problem dotyczący systemów zbiorów. Podobnie Dyer (1986) i Clarkson (w wersji konferencyjnej Clarkson 1995 ) zaobserwowali, że ich metody mogą być stosowane zarówno do programów wypukłych, jak i liniowych. Dyer (1992) wykazał, że problem minimalnej elipsoidy obejmującej można również sformułować jako problem optymalizacji wypukłej przez dodanie niewielkiej liczby więzów nieliniowych. Wykorzystanie randomizacji do poprawy granic czasowych dla niskowymiarowego programowania liniowego i powiązanych problemów zostało zapoczątkowane przez Clarksona oraz Dyera i Frieze'a (1989) .

Definicja problemów typu LP w kategoriach funkcji spełniających aksjomaty lokalności i monotoniczności pochodzi z Sharira i Welzla (1992) , ale inni autorzy sformułowali w tym samym czasie alternatywne kombinatoryczne uogólnienia programów liniowych. Na przykład w strukturze opracowanej przez Gärtnera (1995) funkcja f jest zastąpiona przez całkowite uporządkowanie podzbiorów S . Możliwe jest zerwanie więzi w problemie typu LP w celu stworzenia całościowego porządku, ale tylko kosztem zwiększenia wymiaru kombinatorycznego. Dodatkowo, podobnie jak w problemach typu LP, Gärtner definiuje pewne prymitywy do wykonywania obliczeń na podzbiorach elementów; jego sformalizowanie nie ma jednak odpowiednika wymiaru kombinatorycznego.

Kolejne abstrakcyjne uogólnienie zarówno programów liniowych, jak i problemów liniowej komplementarności , sformułowane przez Stickneya i Watsona (1978), a następnie badane przez kilku innych autorów, dotyczy orientacji krawędzi hipersześcianu o własności, że każda ściana hipersześcianu (w tym cały hipersześcian) jako twarz) ma unikalny zlew , wierzchołek bez krawędzi wychodzących. Orientację tego typu można utworzyć z problemu typu LP, odpowiadając podzbiorom S z wierzchołkami hipersześcianu w taki sposób, że dwa podzbiory różnią się jednym elementem wtedy i tylko wtedy, gdy odpowiednie wierzchołki sąsiadują ze sobą, oraz przez orientowanie krawędzi między sąsiednimi zbiorami A ⊆ B w kierunku B, jeśli f ( A ) ≠ f ( B ) i w kierunku A w przeciwnym razie. Otrzymana orientacja ma tę dodatkową właściwość, że tworzy ukierunkowany graf acykliczny , z którego można wykazać, że algorytm zrandomizowany może w kilku krokach znaleźć unikalne ujście całego hipersześcianu (optymalną podstawę problemu typu LP). wykładniczy w pierwiastku kwadratowym z  n .

Niedawno opracowane ramy przestrzeni naruszających uogólniają problemy typu LP w tym sensie, że każdy problem typu LP może być modelowany przez przestrzeń naruszającą, ale niekoniecznie odwrotnie. Przestrzenie naruszające są definiowane podobnie do problemów typu LP, przez funkcję f, która odwzorowuje zbiory na wartości funkcji celu, ale wartości f nie są uporządkowane. Pomimo braku uporządkowania, każdy zbiór S ma dobrze zdefiniowany zbiór baz (minimalne zbiory o takiej samej wartości jak cały zbiór), które można znaleźć za pomocą odmian algorytmów Clarksona dla problemów typu LP. Rzeczywiście, wykazano, że przestrzenie naruszające dokładnie charakteryzują systemy, które można rozwiązać za pomocą algorytmów Clarksona.

Uwagi

Bibliografia