Problém typu LP - LP-type problem

Při studiu algoritmů je problém typu LP (nazývaný také zobecněný lineární program ) problémem optimalizace, který sdílí určité vlastnosti s nízko dimenzionálními lineárními programy a který lze vyřešit podobnými algoritmy. Problémy typu LP zahrnují mnoho důležitých optimalizačních problémů, které samy o sobě nejsou lineárními programy, jako je například problém nalezení nejmenší kružnice obsahující danou sadu rovinných bodů. Lze je vyřešit kombinací randomizovaných algoritmů za dobu, která je lineární v počtu prvků definujících problém, a subexponenciální v dimenzi problému.

Definice

Problémy typu LP definoval Sharir & Welzl (1992) jako problémy, ve kterých je jako vstup zadána konečná množina prvků S a funkce f, která mapuje podmnožiny S na hodnoty z úplně uspořádané množiny. Funkce je požadována pro splnění dvou klíčových vlastností:

  • Monotónnost: pro každé dvě sady A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Lokalita: pro každé dvě množiny A ⊆ B ⊆ S a každý prvek x v S , pokud f ( A ) = f ( B ) = f ( A ∪ { x }) , pak f ( A ) = f ( B ∪ { x }) .

Základ z problému LP typu je množina B ⊆ S s vlastností, že každý vlastní podmnožinou B má menší hodnotu f než B sám, a rozměr (nebo kombinatorické rozměr ) ze problémem LP typu je definován být maximální mohutností základu.

Předpokládá se, že optimalizační algoritmus může vyhodnotit funkci f pouze na sadách, které jsou samy základnami nebo které jsou vytvořeny přidáním jediného prvku do základu. Alternativně může být algoritmus omezen na dvě primitivní operace: test narušení, který pro základnu B a prvek x určí, zda f ( B ) = f ( B ∪ { x }) , a výpočet základu, který (se stejným vstupy) najde základ B ∪ { x }. Úkolem, který má algoritmus provést, je vyhodnotit f ( S ) pouze pomocí těchto omezených hodnocení nebo primitiv.

Příklady a aplikace

Lp Balls

Lineární program, může být definován pomocí systému d nezáporných reálných proměnných , je vázán na n lineární nerovností omezeními, zároveň s nezáporné lineární cílové funkce, které mají být minimalizován. To lze umístit do rámce problémů typu LP tak, že necháme S jako množinu omezení a definujeme f ( A ) (pro podmnožinu A omezení) jako minimální objektivní funkční hodnotu menšího lineárního programu definovaného . S vhodnými obecnými předpoklady polohy (aby se zabránilo tomu, že více bodů řešení má stejnou optimální hodnotu objektivní funkce), to splňuje požadavky monotónnosti a lokality problému typu LP a má kombinatorický rozměr rovný počtu d proměnných. Podobně celočíselný program (sestávající ze souboru lineárních omezení a lineární objektivní funkce, jako v lineárním programu, ale s dodatečným omezením, že proměnné musí nabývat pouze celočíselných hodnot) splňuje monotónnost i vlastnosti lokality LP -typový problém, se stejnými obecnými předpoklady polohy jako u lineárních programů. Věty Bell (1977) a Šála (1977) ukazují, že pro celočíselný program s d proměnnými je kombinatorický rozměr nejvýše  2 d .

Mnoho problémů s přirozenou optimalizací ve výpočetní geometrii je typu LP:

Image
Nejmenší kruhový problém
  • Problém nejmenší kružnice je problém nalezení minimálního poloměru kružnice obsahující danou sadu n bodů v rovině. Splňuje monotónnost (přidáním dalších bodů lze kruh pouze zvětšit) a lokalitou (pokud nejmenší kruh pro množinu A obsahuje B a x , pak stejný kruh také obsahuje B ∪ { x }). Protože nejmenší kruh je vždy určen některými třemi body, problém nejmenšího kruhu má kombinatorický rozměr tři, přestože je definován pomocí dvojrozměrné euklidovské geometrie. Obecněji řečeno, nejmenší uzavírající koule bodů v dimenzích d tvoří problém typu LP kombinatorické dimenze d + 1 . Problém nejmenšího kruhu lze zobecnit na nejmenší kouli obklopující sadu míčků, na nejmenší kouli, která se dotýká nebo obklopuje každou ze sady koulí, na vážený problém s 1 středem nebo na podobné menší problémy s uzavřením koule v ne Euklidovské prostory, jako je prostor se vzdálenostmi definovanými Bregmanovou divergencí . Související problém nalezení nejmenšího uzavírajícího elipsoidu je také problém typu LP, ale s větším kombinatorickým rozměrem d ( d + 3)/2 .
  • Nechť K 0 , K 1 , ... je posloupnost n konvexních množin v d -dimenzionálním euklidovském prostoru, a předpokládejme, že bychom chtěli najít nejdelší předponu této sekvence, která má společný průsečík. To lze vyjádřit jako problém typu LP, ve kterém f ( A ) = -i kde K i je první člen A , který nepatří do protínající se předpony A , a kde f ( A ) = -n, pokud existuje není takový člen. Kombinatorický rozměr tohoto systému je d + 1 .
  • Předpokládejme, že dostaneme kolekci obdélníkových polí zarovnaných v ose v trojrozměrném prostoru a přejeme si najít přímku směřující do kladného oktantu prostoru, která prochází všemi rámečky. To může být vyjádřeno jako problém typu LP s kombinatorickou dimenzí 4.
  • Problém nalezení nejbližší vzdálenosti mezi dvěma konvexními polytopy , specifikovanou jejich sadami vrcholů, může být reprezentován jako problém typu LP. V této formulaci je množina S množinou všech vrcholů v obou polytopech a funkční hodnota f ( A ) je negací nejmenší vzdálenosti mezi konvexními slupkami dvou podmnožin A vrcholů ve dvou polytopech. Kombinatorický rozměr problému je d + 1, pokud jsou dva polytopy disjunktní, nebo d + 2, pokud mají neprázdný průsečík.
  • Nechť S = { f 0 , f 1 , ... } je množina kvazikonvexních funkcí . Pak je bodové maximum max i f i samo o sobě kvazikonvexní a problém nalezení minimální hodnoty max i f i je problém typu LP. Má kombinatorický rozměr nejvýše 2 d + 1 , kde d je rozměr domény funkcí, ale pro dostatečně hladké funkce je kombinatorický rozměr menší, maximálně d + 1 . Mnoho dalších problémů typu LP lze také vyjádřit pomocí kvazikonvexních funkcí tímto způsobem; například nejmenší problém uzavírajícího kruhu je problém minimalizace max i f i, kde každá z funkcí f i měří euklidovskou vzdálenost od jednoho z daných bodů.

Problémy typu LP byly také použity ke stanovení optimálních výsledků určitých her v algoritmické teorii her , zlepšení umístění vrcholů v sítích metod konečných prvků , řešení problémů s umístěním zařízení , analyzování časové složitosti určitých algoritmů pro hledání v exponenciálním čase a rekonstrukce trojrozměrné polohy objektů z jejich dvourozměrných obrazů.

Algoritmy

Seidel

Seidel (1991) poskytl algoritmus pro nízkodimenzionální lineární programování, který může být přizpůsoben rámci problémů typu LP. Seidelův algoritmus bere jako vstup množinu S a samostatnou sadu X (původně prázdnou) prvků, o nichž je známo, že patří k optimálnímu základu. Poté zvažuje zbývající prvky jeden po druhém v náhodném pořadí, pro každý z nich provede testy narušení a v závislosti na výsledku provede rekurzivní volání stejného algoritmu s větší sadou známých základních prvků. Může být vyjádřen následujícím pseudokódem: 

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

V případě problému s kombinatorickou dimenzí d test narušení v i -té iteraci algoritmu selže pouze tehdy, když x je jedním z d - | X | zbývající základní prvky, k čemuž dochází maximálně s pravděpodobností ( d - | X |)/ i . Na základě tohoto výpočtu lze ukázat, že celkově je očekávaný počet testů porušení provedených algoritmem O ( d ! N) , lineární v n, ale horší než exponenciální v d .

Clarkson

Clarkson (1995) definuje dva algoritmy, rekurzivní algoritmus a iterační algoritmus, pro lineární programování založené na technikách náhodného vzorkování, a navrhuje kombinaci těchto dvou, která volá iterační algoritmus z rekurzivního algoritmu. Rekurzivní algoritmus opakovaně vybírá náhodné vzorky, jejichž velikost je přibližně druhá odmocnina vstupní velikosti, rekurzivně řeší problém se vzorkem a poté pomocí testů narušení najde podmnožinu zbývajících prvků, které musí obsahovat alespoň jeden základní prvek: 

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

V každé iteraci, očekávaná velikost V je O ( √ n ) , a vždy, když V je neprázdný, že obsahuje alespoň jeden nový prvek eventuální základě S . Algoritmus proto provádí nanejvýš d iterací, z nichž každá provede n testů narušení a provede jedno rekurzivní volání dílčího problému velikosti O ( d √ n ) .

Clarksonův iterační algoritmus přiřazuje váhy každému prvku S , zpočátku všechny stejné. To pak vybere nastavenou R o 9 d 2 prvky z S náhodně, a vypočítá sady B a V jako v předchozím algoritmu. Pokud je celková hmotnost V nejvýše 2/(9 d - 1) násobek celkové hmotnosti S (jak se to stává s konstantní pravděpodobností), pak algoritmus zdvojnásobí váhy každého prvku V a jako předtím tento proces opakuje, dokud V se stává prázdným. V každé iteraci může být ukázáno, že váha optimálního základu narůstá větší rychlostí, než je celková hmotnost S , z čehož vyplývá, že algoritmus musí skončit v rámci O (log n ) iterací.

Pomocí rekurzivního algoritmu k řešení daného problému, přepnutím na iterační algoritmus pro jeho rekurzivní volání a opětovným přepnutím na Seidelův algoritmus pro volání provedená iteračním algoritmem je možné vyřešit daný problém typu LP pomocí O ( dn + d ! d O (1) log n ) testy porušení.

Při aplikaci na lineární program lze tento algoritmus interpretovat jako metodu dual simplex . S určitými dalšími výpočetními primitivy nad rámec testu porušení a primitiv pro výpočet základů lze tuto metodu učinit deterministickou.

Matoušek, Sharir a Welzl

Matoušek, Sharir & Welzl (1996) popisují algoritmus, který využívá další vlastnost lineárních programů, která není vždy držena jinými problémy typu LP, že všechny báze mají navzájem stejnou mohutnost. Pokud problém typu LP tuto vlastnost nemá, lze jej vytvořit přidáním d nových fiktivních prvků a úpravou funkce f tak, aby vrátila uspořádanou dvojici její staré hodnoty f ( A ) a čísla min ( d , | A |) , seřazeno lexikograficky .

Matoušek, Sharir & Welzl (1996) namísto přidávání prvků S po jednom nebo hledání vzorků těchto prvků popisují algoritmus, který odstraňuje prvky jeden po druhém. V každém kroku udržuje základ C, který může být zpočátku sadou fiktivních prvků. Může být popsán následujícím pseudokódem: 

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

Ve většině rekurzivních volání algoritmu je test porušení úspěšný a příkaz if je přeskočen. S malou pravděpodobností však test narušení nezdaří a algoritmus provede další základní výpočet a poté další rekurzivní volání. Jak autoři ukazují, očekávaný čas algoritmu je lineární v n a exponenciální v odmocnině d log n . Kombinací této metody s rekurzivními a iteračními procedurami společnosti Clarkson lze tyto dvě formy časové závislosti od sebe oddělit, což má za následek algoritmus, který provádí testy narušení O ( dn ) ve vnějším rekurzivním algoritmu a číslo, které je exponenciální v druhá odmocnina d log d v nižších úrovních algoritmu.

Variace

Optimalizace s odlehlými hodnotami

Matoušek (1995) uvažuje o variantě optimalizačních problémů typu LP, ve které je dán jeden, společně s množinou S a objektivní funkcí f , číslo k ; úkolem je odstranit k prvků ze S , aby objektivní funkce na zbývající sadě byla co nejmenší. Například při aplikaci na problém nejmenšího kruhu by to dalo nejmenší kruh, který obsahuje všechny kromě k dané sady rovinných bodů. Ukazuje, že pro všechny nedegenerované problémy typu LP (tj. Problémy, ve kterých mají všechny báze odlišné hodnoty) lze tento problém vyřešit v čase O ( nk d ) řešením sady O ( k d ) LP -typu problémy definované podmnožiny s .

Implicitní problémy

Některé problémy s geometrickou optimalizací mohou být vyjádřeny jako problémy typu LP, ve kterých je počet prvků ve formulaci typu LP výrazně větší než počet hodnot vstupních dat pro problém optimalizace. Jako příklad uvažujme soubor n bodů v rovině, z nichž se každý pohybuje konstantní rychlostí. V každém okamžiku je průměr tohoto systému maximální vzdálenost mezi dvěma jeho body. Problém nalezení času, ve kterém je průměr minimalizován, může být formulován jako minimalizace bodového maxima O ( n 2 ) kvazikonvexních funkcí, jedna pro každou dvojici bodů, měření euklidovské vzdálenosti mezi dvojicí jako funkce času. Lze jej tedy vyřešit jako problém typu LP kombinatorické dimenze dva na sadě prvků O ( n 2 ) , ale tato sada je výrazně větší než počet vstupních bodů.

Chan (2004) popisuje algoritmus pro řešení implicitně definovaných problémů typu LP, jako je tento, ve kterém je každý prvek typu LP určen k -tuplem vstupních hodnot, pro nějakou konstantu k . Aby bylo možno použít svůj přístup, musí existovat rozhodovací algoritmus , který může určit pro danou LP typu bázi B a nastavte S o n vstupních hodnot, zda B je základem pro problém LP typu určeného S .

Chanův algoritmus provádí následující kroky:

  • Pokud je počet vstupních hodnot pod nějakou prahovou hodnotou, najděte sadu prvků typu LP, které určuje, a vyřešte výsledný explicitní problém typu LP.
  • Jinak rozdělte vstupní hodnoty na vhodný počet větší než k stejných velikostí podmnožin S i .
  • Pokud f je objektivní funkcí pro řešení implicitně definovaného problému typu LP, definujte funkci g, která mapuje kolekce podmnožin S i na hodnotu f při sjednocení kolekce. Poté kolekce podmnožin S i a samotná objektivní funkce g definuje problém typu LP, stejného rozměru jako implicitní problém, který má být vyřešen.
  • Vyřešte (explicitní) problém typu LP definovaný pomocí g pomocí Clarksonova algoritmu, který provádí lineární počet testů porušení a polylogaritmický počet vyhodnocení základen. Vyhodnocení základny pro g může být prováděno rekurzivními voláními Chanova algoritmu a testy porušení mohou být prováděny voláním rozhodovacího algoritmu.

Za předpokladu, že rozhodovací algoritmus trvá určitý čas O ( T ( n )), který roste alespoň polynomicky jako funkce vstupní velikosti n , Chan ukazuje, že práh pro přepnutí na explicitní LP formulaci a počet podmnožin v oddílu lze zvolit tak, že implicitní algoritmus optimalizace typu LP také běží v čase O ( T ( n )) .

Například pro minimální průměr pohybujících se bodů musí rozhodovací algoritmus pouze vypočítat průměr sady bodů v pevném čase, což je problém, který lze vyřešit v čase O ( n log n ) pomocí techniky rotujících posuvných měřítek . Chanův algoritmus pro nalezení času, ve kterém je průměr minimalizován, proto také potřebuje čas O ( n log n ) . Chan používá tuto metodu k nalezení bodu maximální hloubky Tukey mezi danou kolekcí n bodů v d -dimenzionálním euklidovském prostoru, v čase O ( n d -1 + n log n ) . Podobnou techniku ​​použili Braß, Heinrich-Litan & Morin (2003) k nalezení bodu maximální hloubky Tukey pro rovnoměrné rozložení na konvexním polygonu.

Historie a související problémy

Objev algoritmů lineárního času pro lineární programování a pozorování, že stejné algoritmy lze v mnoha případech použít k řešení problémů s geometrickou optimalizací, které nebyly lineárními programy, sahá přinejmenším k Megiddovi ( 1983 , 1984 ), který dal lineární očekávaný čas algoritmus jak pro tři proměnné lineární programy, tak pro problém nejmenších kruhů. Megiddo však zobecnění lineárního programování formuloval spíše geometricky než kombinatoricky, spíše jako problém konvexní optimalizace než jako abstraktní problém v soustavách množin. Podobně Dyer (1986) a Clarkson (v konferenční verzi Clarkson 1995 z roku 1988 ) zjistili, že jejich metody lze použít na konvexní i lineární programy. Dyer (1992) ukázal, že problém minimálního obklopujícího elipsoidu by mohl být také formulován jako problém konvexní optimalizace přidáním malého počtu nelineárních omezení. Využití randomizace ke zlepšení časových hranic pro nízkodimenzionální lineární programování a související problémy propagovali Clarkson a Dyer & Frieze (1989) .

Definice problémů typu LP z hlediska funkcí splňujících axiomy lokality a monotonicity je od Sharir & Welzl (1992) , ale další autoři ve stejném časovém rámci formulovali alternativní kombinatorické zobecnění lineárních programů. Například, v rámci vyvinuté Gärtner (1995) , funkce f je nahrazen celkové uspořádání na podmnožiny S . Je možné přetrhat pouta v problému typu LP k vytvoření celkového řádu, ale pouze na úkor zvýšení kombinatorické dimenze. Navíc, jako v problémech typu LP, Gärtner definuje určitá primitiva pro provádění výpočtů na podmnožinách prvků; jeho formalizace však nemá analogii kombinatorické dimenze.

Další abstraktní zobecnění obou lineárních programů a problémů lineární komplementarity , formulované Stickneyem a Watsonem (1978) a později zkoumané několika dalšími autory, se týká orientace hran hyperkrychle s vlastností, že každá tvář hyperkocky (včetně celé hyperkocky) jako obličej) má jedinečný dřez , vrchol bez odchozích hran. Orientaci tohoto typu lze vytvořit z problému typu LP tak, že podmnožiny S odpovídáme vrcholům hyperkrychle takovým způsobem, že se dvě podmnožiny liší jediným prvkem právě tehdy, když sousedící vrcholy sousedí, a orientace hrany mezi sousedními množinami A ⊆ B směrem k B, pokud f ( A ) ≠ f ( B ) a směrem k A jinak. Výsledná orientace má další vlastnost, že tvoří směrovaný acyklický graf , ze kterého je možné ukázat, že randomizovaný algoritmus dokáže v několika krocích najít jedinečný propad celé hyperkrychle (optimální základ problému typu LP) exponenciální v odmocnině  n .

Nověji vyvinutý rámec prostorů pro narušitele zobecňuje problémy typu LP v tom smyslu, že každý problém typu LP může být modelován prostorem pro narušitele, ale ne nutně naopak. Prostory narušitele jsou definovány podobně jako problémy typu LP funkcí f, která mapuje sady na objektivní funkční hodnoty, ale hodnoty f nejsou uspořádány. Navzdory nedostatku uspořádání má každá sada S dobře definovanou sadu základen (minimální sady se stejnou hodnotou jako celá sada), které lze nalézt pomocí variací Clarksonových algoritmů pro problémy typu LP. Ukázalo se, že mezery pro narušitele přesně charakterizují systémy, které lze vyřešit Clarksonovými algoritmy.

Poznámky

Reference