Karmarkarův algoritmus

Karmarkarův algoritmus  je algoritmus představený Narendrou Karmarkarem v roce 1984 pro řešení problémů lineárního programování . Byl to první dostatečně účinný algoritmus pro řešení problémů v polynomiálním čase . Elipsoidní metoda je také polynomiální časový algoritmus, ale v praktických aplikacích se ukázala jako neefektivní.

If  je počet proměnných a  je počet vstupních bitů, Karmarkarův algoritmus vyžaduje operace na číslech se znaménkem , zatímco elipsoidní metoda takové operace vyžaduje. Doba běhu algoritmu Karmarkar je

při použití metody násobení Schönhage-Strassen (viz "O" velké ).

Algoritmus Karmarkar patří do třídy metod vnitřních bodů  - současné proveditelné řešení se nepohybuje po hranici oboru proveditelných řešení jako u simplexové metody , ale pohybuje se po vnitřních bodech oboru proveditelných hodnot a zlepšuje se s každým iterace aproximace optimálního řešení určitým zlomkem a vedoucí k optimálnímu řešení s racionálními daty [1] .

Algoritmus

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

maximalizovat c T x
pod omezeními Ax ≤ b.

Algoritmus určí další možný směr k optimálnímu řešení a ustoupí faktorem 0 < γ ≤ 1.

Karmarkarův algoritmus je poměrně komplikovaný. Zájemci o čtenáře mohou najít informace o odkazech [2] [3] [4] [5] [6] [7] [8] . Zjednodušená verze nazvaná "Affine Scaling Method" analyzovaná v jiných článcích [9] může být stručně popsána následovně. Všimněte si, že metoda afinního škálování, pokud se používá pro problémy s malou velikostí, není polynomiální časový algoritmus. U velkých a složitých problémů by se měl použít původní přístup. Karmarkar také rozšířil metodologii [10] [11] [12] [13] řešení problémů s celočíselnými omezeními a nekonvexních problémů [14] .

Vstup: A, b, c, , Kritérium zastavení , . kritérium do while stop selže , jestliže potom vraťte neomezené rozhodnutí end if end do

Tady

Příklad

Nechť je dán problém lineárního programování

maximalizovat +
za podmínek + ,

To znamená, že existují dvě proměnné a 11 omezení odpovídajících různým hodnotám . Obrázek ukazuje každou iteraci algoritmu jako červený bod. Limity jsou zobrazeny jako modré čáry.

Debata o patentech – Lze patentovat matematiku?

V době, kdy Narenda Karmarkar navrhl svůj algoritmus, pracoval v AT&T . Po implementaci algoritmu pro optimalizaci telefonní sítě AT&T [15] si uvědomili, že by to mohlo mít praktický význam. V dubnu 1985 společnost AT&T rychle požádala o patent na Karmarkarův algoritmus a tato událost přidala palivo do vášnivé debaty o softwarovém patentu [16] . To vyvolalo obavy mnoha matematiků, jako je Ronald Rivest (je jedním z držitelů patentu algoritmu RSA ), který vyjádřil názor, že výzkum založený na tomto algoritmu by měl být bezplatný. Ještě před schválením patentu někteří tvrdili, že existuje nerealizovaný prototyp [17] .

Matematici specializující se na výpočetní metody , jako je Philip Gill a další, tvrdili, že Karmarkarův algoritmus je ekvivalentní Newtonově projektivní bariérové ​​metodě s logaritmickou bariérovou funkcí , pokud jsou parametry zvoleny správně [18] . Gillův argument má však chybu, protože metoda, kterou popisuje, není ani považována za „algoritmus“, protože vyžaduje volbu parametrů, které nejsou určeny vnitřní logikou metody a spoléhají výhradně na vnější kontrolu, zejména pokud jde o na Karmarkarův algoritmus [19] . Karmarkarův příspěvek navíc není zdaleka zřejmý ve světle všech předchozích prací, včetně práce Fiacca-McCormicka, Gilla a dalších, které Saltzman uvádí [19] [20] [21] . Patent byl projednáván v Senátu USA, byl schválen jako uznání významné originality Karmarkarovy práce a byl podán jako americký patent 4 744 026 "Metody a zařízení pro efektivní přidělování zdrojů" v květnu 1988. AT&T dodal KORBX [22] [23 ] systém založený na tomto patentu The Pentagon [24] [25] , který jej používal k řešení matematických problémů, které byly dříve považovány za neřešitelné.

Odpůrci patentování softwaru později tvrdili, že patenty narušily pozitivní cyklus, který charakterizoval vztah výzkumníků v lineárním programování a výrobě, a zejména izolovaly samotného Karmarkara od matematického výzkumu ve svém oboru [26] .

Platnost patentu vypršela v dubnu 2006 a algoritmus je v současné době ve veřejné doméně.

Poznámky

  1. ↑ Gilbert Strang. Karmarkarův algoritmus a jeho místo v aplikované matematice  (anglicky)  // The Mathematical Intelligencer . - New York: Springer, 1987. - Sv. 9 , iss. 2 . - str. 4-10 . — ISSN 0343-6993 . - doi : 10.1007/BF03025891 .
  2. ↑ Nový polynomiální algoritmus pro lineární programování . Získáno 26. srpna 2015. Archivováno z originálu 14. února 2019.
  3. ↑ Nový polynomiální algoritmus pro lineární programování - Springer . Získáno 29. září 2017. Archivováno z originálu 6. září 2017.
  4. ↑ Varianty výkonových řad algoritmů typu Karmarkar – Karmarkar – 2013 – AT&T Technical Journal – Wiley Online Library . Získáno 26. srpna 2015. Archivováno z originálu 16. července 2015.
  5. ↑ Karmarkar NK, An InteriorPoint Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, pp. 297308 (červen 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Archivováno 4. března 2016 na Wayback Machine
  6. ↑ Karmarkar, NK., Riemannian Geometry Underlying Interior Point Methods for Linear programming, AMS series on Contemporary Mathematics 114, pp. 5175 (červen 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Archivováno 4. března 2016 na Wayback Machine
  7. ↑ Karmarkar NK, Lagarias, JC, Slutsman, L. a Wang, P., Power Series Variants of KarmarkarType Algorithm, AT&T technical Journal 68, no. 3, květen/červen (1989).
  8. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 26. srpna 2015. Archivováno z originálu dne 4. března 2016. 
  9. ↑ Robert J. Vanderbei , Marc Meketon, Barry Freedman. Modifikace Karmarkarova algoritmu lineárního programování // Algorithmica. - 1986. - T. 1 . - S. 395-407 . - doi : 10.1007/BF01840454 .
  10. ↑ Karmarkar, NK, Interior Point Methods in Optimization, Sborník příspěvků z druhé mezinárodní konference průmyslové a aplikované matematiky, SIAM, pp. 160181 (1991)
  11. ↑ Karmarkar, NK a Kamath, AP, Nepřetržitý přístup k odvozování horních hranic v problémech kvadratické maximalizace s celočíselnými omezeními, Nedávné pokroky v globální optimalizaci, str. 125140, Princeton University Press (1992).
  12. ↑ 26. Karmarkar, NK, Thakur, SA, Vnitřní bodový přístup k problému optimalizace tenzoru s aplikací na horní hranice v problémech celočíselné kvadratické optimalizace, sborník z druhé konference o celočíselném programování a kombinatorické optimalizaci, (květen 1992).
  13. ↑ 27. Kamath, A., Karmarkar, NK, A Continuous Method for Computing Bounds in Integer Quadratic Optimization Problems, Journal of Global Optimization (1992).
  14. ↑ Karmarkar, NK, Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, prosinec 2010
  15. ↑ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A. a Ramakrishnan KG, Overseas Network Planning, Proceedings of Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (červen 1986).
  16. ↑ Gina Kolata. NÁPADY A TRENDY; Matematiky trápí tvrzení o jejich receptech  //  The New York Times . — 12. 3. 1989.
  17. ↑ Různé příspěvky od Matthewa Saltzmana, Clemson University . Získáno 26. 8. 2015. Archivováno z originálu 23. 9. 2015.
  18. ↑ Philip E. Gill, Walter Murray, Michael A. Saunders, JA Tomlin, Margaret H. Wright. O projektovaných metodách Newtonovy bariéry pro lineární programování a ekvivalenci s Karmarkarovou projektivní metodou // Mathematical Programming. - 1986. - T. 36 . - S. 183-209 . - doi : 10.1007/BF02592025 .
  19. ↑ 12 Andrew Chin . O abstrakci a ekvivalenci v softwarové patentové doktríně: Odpověď Bessenovi, Meurerovi a Klemensovi // Journal of Intellectual Property Law. - 2009. - T. 16 . - S. 214-223 .
  20. ↑ Mark A. Paley (1995). „Karmarkarův patent: Proč by měl Kongres „otevřít dveře“ algoritmům jako patentovatelnému předmětu“. 22 POČÍTAČ L. REP. 7
  21. ↑ Margaret H. Wrightová. Vnitřní bodová revoluce v optimalizaci: Historie, nedávný vývoj a trvalé důsledky // Bulletiny Americké matematické společnosti. - 2004. - T. 42 . - S. 39-56 .
  22. ↑ Marc S. Meketon, YC Cheng, DJ Houck, JMLiu, L. Slutsman, Robert J. Vanderbei , P. Wang. Systém AT&T KORBX // AT&T Technical Journal. - 1989. - T. 68 . - S. 7-19 .
  23. ↑ Velký AT&T. Počítač pro složitosti – NYTimes.com . Získáno 29. září 2017. Archivováno z originálu 1. února 2018.
  24. ↑ Armáda je prvním oznámeným zákazníkem AT&T Software . Získáno 26. srpna 2015. Archivováno z originálu 6. září 2015.
  25. ↑ Abstrakt IEEE Xplore – Použití KORBX pro aplikace vojenského leteckého transportu . Získáno 26. srpna 2015. Archivováno z originálu 13. listopadu 2014.
  26. ↑ 今野浩: カーマーカー特許とソフトウェア – 数学は? — FFI . Archivováno z originálu 27. června 2008.

Literatura