Karmarkar-algoritmi

Karmarkarin algoritmi  on Narendra Karmarkarin vuonna 1984 esittämä algoritmi lineaaristen ohjelmointiongelmien ratkaisemiseksi . Se oli ensimmäinen riittävän tehokas algoritmi ongelmien ratkaisemiseksi polynomiajassa . Ellipsoidimenetelmä on myös polynomiaikaalgoritmi, mutta se on osoittautunut tehottomaksi käytännön sovelluksissa.

If  on muuttujien  määrä ja on syötebittien määrä, Karmarkarin algoritmi vaatii operaatioita etumerkeille luvuille , kun taas ellipsoidimenetelmä vaatii tällaisia ​​operaatioita. Karmarkar-algoritmin ajoaika on

kun käytetään Schönhage-Strassen-kertomenetelmää (katso "O" iso ).

Karmarkar-algoritmi kuuluu sisäpistemenetelmien luokkaan -  nykyinen toteutettavissa oleva ratkaisu ei liiku toteutettavissa olevien ratkaisujen alueen rajaa pitkin kuten simpleksimenetelmässä , vaan liikkuu toteutettavissa olevien arvojen alueen sisäpisteitä pitkin parantaen jokaisen kanssa. iteroi optimaalisen ratkaisun approksimaatio tietyllä murto-osalla ja johtaa optimaaliseen ratkaisuun rationaalisilla tiedoilla [1] .

Algoritmi

Harkitse lineaarista ohjelmointiongelmaa matriisimuodossa:

maksimoi c T x
rajoitusten alla Ax ≤ b.

Algoritmi määrittää seuraavan mahdollisen suunnan kohti optimaalista ratkaisua ja vetäytyy kertoimella 0 < γ ≤ 1.

Karmarkarin algoritmi on melko monimutkainen. Kiinnostuneet lukijat voivat löytää tietoa viitteistä [2] [3] [4] [5] [6] [7] [8] . Yksinkertaistettu versio nimeltä "Affine Scaling Method", jota on analysoitu muissa julkaisuissa [9] , voidaan kuvata lyhyesti seuraavasti. Huomaa, että affine skaalausmenetelmä, kun sitä käytetään pienikokoisiin ongelmiin, ei ole polynomiaikaalgoritmi. Suurikokoisissa ja monimutkaisissa ongelmissa tulee noudattaa alkuperäistä lähestymistapaa. Karmarkar laajensi myös metodologiaa [10] [11] [12] [13] kokonaislukurajoitteisten ja ei-konveksien ongelmien ratkaisemiseksi [14] .

Syöttö: A, b, c, , Pysäytyskriteeri , . do while stop kriteeri epäonnistuu if sitten palauta rajaton päätös end if end do

Tässä

Esimerkki

Olkoon lineaarinen ohjelmointitehtävä

maksimoida +
olosuhteissa + ,

Eli on olemassa kaksi muuttujaa ja 11 rajoitusta, jotka vastaavat eri arvoja . Kuvassa jokainen algoritmin iteraatio näkyy punaisena pisteenä. Rajat näkyvät sinisinä viivoina.

Patenttikeskustelu – Voidaanko matematiikka patentoida?

Kun Narenda Karmarkar ehdotti algoritmiaan, hän työskenteli AT&T :ssä . AT&T-puhelinverkon optimointialgoritmin [15] käyttöönoton jälkeen he ymmärsivät, että sillä voi olla käytännön merkitystä. Huhtikuussa 1985 AT&T haki nopeasti patenttia Karmarkarin algoritmille, ja tämä tapahtuma lisäsi polttoainetta kiihkeään ohjelmistopatenttikeskusteluun [16] . Tämä on herättänyt huolta monille matemaatikoille, kuten Ronald Rivestille (hän ​​on yksi RSA-algoritmin patentinhaltijoista ), joka ilmaisi mielipiteen, että tähän algoritmiin perustuvan tutkimuksen pitäisi olla ilmaista. Jo ennen patentin hyväksymistä jotkut väittivät, että olemassa oli toteuttamaton prototyyppi [17] .

Laskennallisiin menetelmiin erikoistuneet matemaatikot , kuten Philip Gill ja muut, ovat väittäneet, että Karmarkarin algoritmi vastaa Newtonin projektiivista estemenetelmää logaritmisella estefunktiolla, jos parametrit valitaan oikein [18] . Gillin väitteessä on kuitenkin puute, koska hänen kuvaamaansa menetelmää ei pidetä edes "algoritmina", koska se edellyttää sellaisten parametrien valintaa, jotka eivät ole menetelmän sisäisen logiikan määräämiä ja jotka perustuvat täysin ulkoiseen ohjaukseen, varsinkin mitä tulee. Karmarkarin algoritmiin [19] . Lisäksi Karmarkarin panos ei ole läheskään ilmeinen kaiken aikaisemman työn valossa, mukaan lukien Fiacco-McCormickin, Gillin ja muiden Saltzmanin luetteloimien [19] [20] [21] töiden valossa . Patentista keskusteltiin Yhdysvaltain senaatissa, se hyväksyttiin tunnustuksena Karmarkarin työn merkittävästä omaperäisyydestä, ja se jätettiin US-patentiksi 4 744 026 "Methods and Apparatus for Efficient Resource Allocation" toukokuussa 1988. AT&T toimitti KORBX:n [22] [23 ] ] tähän patenttiin perustuva järjestelmä, The Pentagon [24] [25] , joka käytti sitä ratkaistakseen matemaattisia ongelmia, joita aiemmin pidettiin ratkaisemattomina.

Ohjelmistopatentoinnin vastustajat väittivät myöhemmin, että patentit katkaisivat positiivisen kierteen, joka oli ominaista tutkijoiden suhteelle lineaarisen ohjelmoinnin ja tuotannon alalla, ja erityisesti eristi Karmarkarin itsensä alansa matemaattisesta tutkimuksesta [26] .

Patentti päättyi huhtikuussa 2006 ja algoritmi on tällä hetkellä julkisessa käytössä.

Muistiinpanot

  1. ↑ Gilbert Strang. Karmarkarin algoritmi ja sen paikka sovelletussa matematiikassa  (englanniksi)  // The Mathematical Intelligencer . - New York: Springer, 1987. - Voi. 9 , iss. 2 . - s. 4-10 . — ISSN 0343-6993 . - doi : 10.1007/BF03025891 .
  2. ↑ Uusi polynomi-aikaalgoritmi lineaariseen ohjelmointiin . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 14. helmikuuta 2019.
  3. ↑ Uusi polynomiaikaalgoritmi lineaariseen ohjelmointiin - Springer . Haettu 29. syyskuuta 2017. Arkistoitu alkuperäisestä 6. syyskuuta 2017.
  4. ↑ Karmarkar-tyyppisten algoritmien Power Series -versiot - Karmarkar - 2013 - AT&T Technical Journal - Wiley Online Library . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 16. heinäkuuta 2015.
  5. ↑ Karmarkar NK, An InteriorPoint Approach to NPComplete Problems Osa I, AMS-sarja Contemporary Mathematics 114, pp. 297308 (kesäkuu 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa
  6. ↑ Karmarkar, NK., Riemannian Geometry Underlying Interior Point Methods for Lineaar Programming, AMS series on Contemporary Mathematics 114, pp. 5175 (kesäkuu 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa
  7. ↑ Karmarkar NK, Lagarias, JC, Slutsman, L. ja Wang, P., Power Series Variants of KarmarkarType Algorithm, AT&T Technical Journal 68, no. 3, touko/kesäkuu (1989).
  8. ↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016. 
  9. ↑ Robert J. Vanderbei, Marc Meketon, Barry Freedman. Karmarkarin lineaarisen ohjelmointialgoritmin muunnos // 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 ja Kamath, AP, Jatkuva lähestymistapa ylärajojen johtamiseen neliöllisen maksimointiongelmissa kokonaislukurajoitteilla, viimeaikaiset edistysaskeleet globaalissa optimoinnissa, s. 125140, Princeton University Press (1992).
  12. ↑ 26. Karmarkar, NK, Thakur, SA, An Interior Point Approach to a Tensor Optimization Problem with Application Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatoral Optimization, (toukokuu 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. Springerin luentomuistiinpanot tietojenkäsittelytieteessä LNCS 6457, joulukuu 2010
  15. ↑ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A. ja Ramakrishnan KG, Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (kesäkuu 1986).
  16. ↑ Gina Kolata. IDEOITA JA TRENDIT; Matemaatikkoja vaivaa resepteihin liittyvät väitteet  //  The New York Times . – 12.3.1989.
  17. ↑ Matthew Saltzmanin Clemson Universityn eri julkaisuja . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 23. syyskuuta 2015.
  18. ↑ Philip E. Gill, Walter Murray, Michael A. Saunders, JA Tomlin, Margaret H. Wright. Projisoiduista Newtonin estemenetelmistä lineaariseen ohjelmointiin ja vastaavuudesta Karmarkarin projektiiviseen menetelmään // Matemaattinen ohjelmointi. - 1986. - T. 36 . - S. 183-209 . - doi : 10.1007/BF02592025 .
  19. ↑ 12 Andrew Chin . Abstraktiosta ja vastaavuudesta ohjelmistopatenttidoktriinissa: vastaus Bessenille, Meurerille ja Klemensille // Journal of Intellectual Property Law. - 2009. - T. 16 . - S. 214-223 .
  20. ↑ Mark A. Paley (1995). "Karmarkar-patentti: Miksi kongressin pitäisi "avata ovi" algoritmeille patentoitavana aiheena". 22 COMPUTER L. TASAVALTA 7
  21. ↑ Margaret H. Wright. Optimoinnin sisäinen vallankumous: historia, viimeaikainen kehitys ja pysyvät seuraukset // 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 -järjestelmä // AT&T Technical Journal. - 1989. - T. 68 . - S. 7-19 .
  23. ↑ Iso AT&T. Tietokone monimutkaisille asioille - NYTimes.com . Haettu 29. syyskuuta 2017. Arkistoitu alkuperäisestä 1. helmikuuta 2018.
  24. ↑ Military on ensimmäinen ilmoitettu AT&T Softwaren asiakas . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 6. syyskuuta 2015.
  25. ↑ IEEE Xplore Abstract - KORBX:n käyttäminen sotilaslentosovelluksissa . Haettu 26. elokuuta 2015. Arkistoitu alkuperäisestä 13. marraskuuta 2014.
  26. ↑ 今野浩: カーマーカー特許とソフトウェア – 数学は 特許に なるか Software なるか (Konnomark?) Beartens-Patheentable. – FFI . Arkistoitu alkuperäisestä 27. kesäkuuta 2008.

Kirjallisuus