Karmarkar algoritme

Karmarkars algoritme  er en algoritme introduceret af Narendra Karmarkar i 1984 til løsning af lineære programmeringsproblemer . Det var den første tilstrækkeligt effektive algoritme til at løse problemer i polynomisk tid . Ellipsoidmetoden er også en polynomisk tidsalgoritme, men den har vist sig at være ineffektiv i praktiske anvendelser.

Hvis  er antallet af variable og  er antallet af inputbits, kræver Karmarkars algoritme operationer på tal med fortegn , mens ellipsoidmetoden kræver sådanne operationer. Køretiden for Karmarkar-algoritmen er

ved brug af Schönhage-Strassen multiplikationsmetoden (se "O" stor ).

Karmarkar-algoritmen tilhører klassen af ​​indre punktmetoder  - den nuværende mulige løsning bevæger sig ikke langs grænsen af ​​domænet af mulige løsninger som i simplex-metoden , men bevæger sig langs de indre punkter af domænet af mulige værdier og forbedres med hver iteration tilnærmelsen af ​​den optimale løsning med en bestemt brøkdel og fører til en optimal løsning med rationelle data [1] .

Algoritme

Overvej et lineært programmeringsproblem i matrixform:

maksimer c T x
under restriktioner Axe ≤ b.

Algoritmen bestemmer den næste mulige retning mod den optimale løsning og trækker sig tilbage med en faktor 0 < γ ≤ 1.

Karmarkars algoritme er ret kompliceret. Interesserede læsere kan finde information om referencer [2] [3] [4] [5] [6] [7] [8] . En forenklet version kaldet "Affine Scaling Method" analyseret i andre artikler [9] kan kort beskrives som følger. Bemærk, at den affine skaleringsmetode, når den bruges til problemer med små størrelser, ikke er en polynomiel tidsalgoritme. For store og komplekse problemer bør den oprindelige tilgang følges. Karmarkar udvidede også metoden [10] [11] [12] [13] til at løse problemer med heltalsbegrænsninger og ikke-konvekse problemer [14] .

Input: A, b, c, , Stop kriterium , . gør mens stop kriterium mislykkes hvis derefter returnere ubegrænset beslutning end hvis ende gør

Her

Eksempel

Lad et lineært programmeringsproblem blive givet

maksimere +
under forhold + ,

Det vil sige, at der er to variable og 11 begrænsninger svarende til forskellige værdier af . Figuren viser hver iteration af algoritmen som en rød prik. Grænserne vises som blå linjer.

Patentdebat - Kan matematik patenteres?

På det tidspunkt, hvor Narenda Karmarkar foreslog sin algoritme, arbejdede han hos AT&T . Efter implementeringen af ​​algoritmen til optimering af AT&T-telefonnettet [15] indså de, at det kunne være af praktisk betydning. I april 1985 ansøgte AT&T hurtigt om patent på Karmarkars algoritme, og denne begivenhed tilføjede brændstof til den ophedede softwarepatentdebat [16] . Dette har givet anledning til bekymring hos mange matematikere, såsom Ronald Rivest (han er en af ​​patentindehaverne af RSA-algoritmen ), som udtrykte den opfattelse, at forskning baseret på denne algoritme burde være gratis. Allerede før patentet blev godkendt, hævdede nogle, at der var en urealiseret prototype [17] .

Matematikere med speciale i beregningsmetoder , såsom Philip Gill og andre, har hævdet, at Karmarkars algoritme svarer til Newtons projektive barrieremetode med en logaritmisk barrierefunktion, hvis parametrene er valgt korrekt [18] . Gills argumentation har dog en fejl, da den metode han beskriver ikke engang betragtes som en "algoritme", da den kræver valg af parametre, der ikke er bestemt af metodens interne logik og udelukkende er afhængig af ekstern kontrol, især mht. til Karmarkars algoritme [19] . Desuden er Karmarkars bidrag langt fra indlysende i lyset af alt tidligere arbejde, inklusive det af Fiacco-McCormick, Gill og andre opført af Saltzman [19] [20] [21] . Patentet blev diskuteret i det amerikanske senat, blev godkendt i erkendelse af den betydelige originalitet af Karmarkars arbejde og blev indleveret som US patent 4.744.026 "Methods and Apparatus for Efficient Resource Allocation" i maj 1988. AT&T leverede KORBX [22] [23 ] ] system baseret på dette patent, The Pentagon [24] [25] , som brugte det til at løse matematiske problemer, der tidligere blev anset for uløselige.

Modstandere af softwarepatentering hævdede senere, at patenter forstyrrede den positive cyklus, der karakteriserede forholdet mellem forskere inden for lineær programmering og produktion, og især isolerede Karmarkar selv fra matematisk forskning inden for hans felt [26] .

Patentet udløb i april 2006, og algoritmen er i øjeblikket i det offentlige domæne.

Noter

  1. ↑ Gilbert Strang. Karmarkars algoritme og dens plads i anvendt matematik  (engelsk)  // The Mathematical Intelligencer . - New York: Springer, 1987. - Vol. 9 , iss. 2 . - S. 4-10 . — ISSN 0343-6993 . - doi : 10.1007/BF03025891 .
  2. ↑ En ny polynomiel-tidsalgoritme til lineær programmering . Hentet 26. august 2015. Arkiveret fra originalen 14. februar 2019.
  3. ↑ En ny polynomiel-tidsalgoritme til lineær programmering - Springer . Hentet 29. september 2017. Arkiveret fra originalen 6. september 2017.
  4. ↑ Power Series Varianter af Karmarkar-Type Algorithms - Karmarkar - 2013 - AT&T Technical Journal - Wiley Online Library . Hentet 26. august 2015. Arkiveret fra originalen 16. juli 2015.
  5. ↑ Karmarkar NK, An InteriorPoint Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, s. 297308 (juni 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Arkiveret 4. marts 2016 på Wayback Machine
  6. ↑ Karmarkar, NK., Riemannian Geometry Underlying Interior Point Methods for Linear programmering, AMS series on Contemporary Mathematics 114, pp. 5175 (juni 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Arkiveret 4. marts 2016 på Wayback Machine
  7. ↑ Karmarkar NK, Lagarias, JC, Slutsman, L., og Wang, P., Power Series Variants of KarmarkarType Algorithm, AT&T teknisk tidsskrift 68, nr. 3, maj/juni (1989).
  8. ↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 26. august 2015. Arkiveret fra originalen 4. marts 2016. 
  9. ↑ Robert J. Vanderbei , Marc Meketon, Barry Freedman. En ændring af Karmarkars lineære programmeringsalgoritme // Algorithmica. - 1986. - T. 1 . - S. 395-407 . - doi : 10.1007/BF01840454 .
  10. ↑ Karmarkar, NK, Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)
  11. ↑ Karmarkar, NK og Kamath, AP, A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, s. 125140, Princeton University Press (1992).
  12. ↑ 26. Karmarkar, NK, Thakur, SA, An Interior Point Approach to a Tensor Optimization Problem with Application to Upper Bounds in Integer Quadratic Optimization Problemer, Proceedings of Second Conference on Heltal Programming and Combinatorial Optimization, (maj 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, dec 2010
  15. ↑ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A., og Ramakrishnan KG, Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (juni 1986).
  16. ↑ Gina Kolata. IDÉER & TRENDS; Matematikere er urolige over påstande om deres opskrifter  //  The New York Times . — 1989-03-12.
  17. ↑ Forskellige indlæg af Matthew Saltzman, Clemson University . Hentet 26. august 2015. Arkiveret fra originalen 23. september 2015.
  18. ↑ Philip E. Gill, Walter Murray, Michael A. Saunders, JA Tomlin, Margaret H. Wright. Om projekterede Newton-barrieremetoder til lineær programmering og en ækvivalens til Karmarkars projektive metode // Matematisk programmering. - 1986. - T. 36 . - S. 183-209 . - doi : 10.1007/BF02592025 .
  19. ↑ 12 Andrew Chin . Om abstraktion og ækvivalens i softwarepatentdoktrin: et svar på Bessen, Meurer og Klemens // Journal of Intellectual Property Law. - 2009. - T. 16 . - S. 214-223 .
  20. ↑ Mark A. Paley (1995). "Karmarkar-patentet: Hvorfor kongressen bør "åbne døren" for algoritmer som patenterbart emne". 22 COMPUTER L. REP. 7
  21. ↑ Margaret H. Wright. The Interior-Point Revolution in Optimization: History, Recent Developments and Lasting Consequences // Bulletins of the American Mathematical Society. - 2004. - T. 42 . - S. 39-56 .
  22. ↑ Marc S. Meketon, YC Cheng, DJ Houck, JMLiu, L. Slutsman, Robert J. Vanderbei , P. Wang. AT&T KORBX System // AT&T Technical Journal. - 1989. - T. 68 . - S. 7-19 .
  23. ↑ Stor AT&T. Computer til kompleksiteter - NYTimes.com . Hentet 29. september 2017. Arkiveret fra originalen 1. februar 2018.
  24. ↑ Militær er først annonceret som kunde af AT&T-software . Hentet 26. august 2015. Arkiveret fra originalen 6. september 2015.
  25. ↑ IEEE Xplore Abstract - Brug af KORBX til militære luftbroapplikationer . Hentet 26. august 2015. Arkiveret fra originalen 13. november 2014.
  26. ↑ 今野浩: カーマーカー特許とソフトウェア – 数学は 特許に なるか The Kamark Hiroshien Software: Mathematics, Patent og Patent. — FFI . Arkiveret fra originalen den 27. juni 2008.

Litteratur