Karmarkarův algoritmus - Karmarkar's algorithm

Karmarkarův algoritmus je algoritmus zavedený Narendrou Karmarkarem v roce 1984 pro řešení problémů lineárního programování . Byl to první přiměřeně účinný algoritmus, který řeší tyto problémy v polynomiálním čase . Elipsoid metoda je také polynom čas, ale se ukázal jako neúčinný v praxi.

Karmarkarův algoritmus, označovaný jako počet proměnných a jako počet bitů vstupu do algoritmu, vyžaduje operace s číselnými čísly ve srovnání s takovými operacemi pro elipsoidní algoritmus. Doba běhu Karmarkarova algoritmu je tedy ${\ displaystyle n}$${\ displaystyle L}$${\ displaystyle O (n^{3,5} L)}$${\ displaystyle O (L)}$${\ displaystyle O (n^{6} L)}$

${\ Displaystyle O (n^{3.5} L^{2} \ cdot \ log L \ cdot \ log \ log L)}$

pomocí multiplikace založené na FFT (viz notace Big O ).

Karmarkarův algoritmus spadá do třídy vnitřních bodových metod : aktuální odhad řešení nesleduje hranici proveditelné množiny jako v simplexové metodě , ale pohybuje se vnitřkem proveditelné oblasti a zlepšuje aproximaci optimálního řešení. o určitý zlomek s každou iterací a konvergující k optimálnímu řešení s racionálními daty.

Algoritmus

Zvažte problém lineárního programování ve formě matice:

Karmarkarův algoritmus určuje další proveditelný směr k optimalitě a zmenšuje se o faktor 0 <γ ≤ 1 . Je popsána v řadě zdrojů. Karmarkar také rozšířil metodu pro řešení problémů s celočíselnými omezeními a nekonvexními problémy.

Algorithm Affine-Scaling

Input:  A, b, c, ${\displaystyle x^{0}}$, stopping criterion, γ.

${\displaystyle k\leftarrow 0}$
do while stopping criterion not satisfied
    ${\displaystyle v^{k}\leftarrow b-Ax^{k}}$
    ${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$
    ${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$
    ${\displaystyle h_{v}\leftarrow -Ah_{x}}$
    if ${\displaystyle h_{v}\geq 0}$ then
        return unbounded
    end if
    ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$
    ${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$
    ${\displaystyle k\leftarrow k+1}$
end do

Příklad

Příklad řešení

Zvažte lineární program

${\ displaystyle {\ begin {array} {lrclr} {\ text {maximize}} & x_ {1}+x_ {2} \\ {\ text {subject to}} & 2px_ {1}+x_ {2} & \ leq & p^{2}+1, & p = 0,0,0,1,0,2, \ ldots, 0,9,1,0. \ end {array}}}$

To znamená, že s proměnnými hodnotami jsou spojeny 2 proměnné a 11 omezení . Tento obrázek ukazuje každou iteraci algoritmu jako body červeného kruhu. Omezení jsou zobrazena jako modré čáry. ${\ displaystyle x_ {1}, x_ {2}}$${\ displaystyle p}$

Patentová kontroverze - lze matematiku patentovat?

V době, kdy vynalezl algoritmus, byl Karmarkar zaměstnán společností IBM jako postdoktorand ve výzkumné laboratoři IBM San Jose v Kalifornii. 11. srpna 1983 uspořádal seminář na Stanfordské univerzitě, kde vysvětlil algoritmus, přičemž jeho příslušnost byla stále uvedena jako IBM. Na podzim roku 1983 začal Karmarkar pracovat ve společnosti AT&T a předložil svůj příspěvek na sympozium ACM z roku 1984 o teorii výpočetní techniky (STOC, které se konalo 30. dubna - 2. května 1984) s uvedením společnosti AT&T Bell Laboratories jako své příslušnosti. Po aplikaci algoritmu na optimalizaci telefonní sítě AT & T si uvědomili, že jeho vynález může mít praktický význam. V dubnu 1985 společnost AT&T okamžitě požádala o patent na Karmarkarův algoritmus.

Patent se stal palivem pro pokračující kontroverze ohledně problematiky softwarových patentů . To zanechalo mnoho matematiků neklidných, například Ronald Rivest (sám jeden z držitelů patentu na algoritmus RSA ), který vyjádřil názor, že výzkum probíhal na základě toho, že algoritmy by měly být zdarma. Ještě předtím, než byl patent skutečně udělen, se tvrdilo, že mohlo existovat dosavadní umění, které bylo použitelné. Matematici, kteří se specializovali na numerickou analýzu , včetně Philipa Gilla a dalších, tvrdili, že Karmarkarův algoritmus je ekvivalentní projektované Newtonově bariérové ​​metodě s logaritmickou bariérovou funkcí , pokud jsou parametry zvoleny vhodně. Právní vědec Andrew Chin se domnívá, že Gillův argument byl chybný, pokud metoda, kterou popisují, nepředstavuje „algoritmus“, protože vyžaduje volby parametrů, které nevyplývají z vnitřní logiky metody, ale spoléhají na externí vedení, v podstatě z Karmarkarova algoritmu. Kromě toho jsou Karmarkarovy příspěvky považovány za zdaleka ne zjevné ve světle všech předchozích prací, včetně Fiacco-McCormicka, Gilla a dalších citovaných Saltzmanem. Patent byl projednán v americkém Senátu a udělen jako uznání zásadní originality Karmarkarovy práce, jako US patent 4 744 028 : „Metody a zařízení pro efektivní alokaci zdrojů“ v květnu 1988.

Společnost AT&T navrhla vektorový víceprocesorový počítačový systém speciálně pro spuštění Karmarkarova algoritmu, přičemž výslednou kombinaci hardwaru a softwaru nazval KORBX, a tento systém uvedl na trh za cenu 8,9 milionu USD. Jeho prvním zákazníkem byl Pentagon .

Odpůrci softwarových patentů dále tvrdili, že patenty zničily pozitivní interakční cykly, které dříve charakterizovaly vztah mezi výzkumníky v lineárním programování a průmyslu, a konkrétně izolovalo samotného Karmarkara ze sítě matematických výzkumníků ve svém oboru.

Samotný patent vypršel v dubnu 2006 a algoritmus je v současné době veřejně dostupný .

Nejvyšší soud Spojených států rozhodl, že matematika nemůže být patentován v Gottschalk v. Benson , V tomto případě Soudní dvůr nejprve určeno, zda počítačové algoritmy by mohly být patentovány a rozhodl, že oni nemohli, protože patentový systém nechrání myšlenky a podobné abstrakce . V Diamond v. Diehr , Nejvyšší soud konstatoval, „matematický vzorec jako takový není přiznána ochrana našich patentových zákonů, a tento princip nelze obejít tím, že pokouší omezit použití vzorce pro konkrétního technologického prostředí. V Mayo Collaborative Services v. Prometheus Labs., Inc. , Nejvyšší soud dále vysvětlil, že „pouhá implementace matematického principu na fyzický stroj, konkrétně počítač, [není] patentovatelná aplikace tohoto principu“.

Reference

• Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio GC; Veiga, Geraldo (1989). „Implementace Karmarkarova algoritmu pro lineární programování“. Matematické programování . 44 (1–3): 297–335. doi : 10,1007/bf01587095 . S2CID  12851754 .
• Narendra Karmarkar (1984). „ Nový polynomiální časový algoritmus pro lineární programování “, Combinatorica , sv. 4 , č. 4, s. 373–395.