Алгоритм Кармаркара

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм Кармаркара — это алгоритм, представленный Нарендрой Кармаркаром в 1984 году для решения задач линейного программирования. Это был первый достаточно эффективный алгоритм, который решал задачи за полиномиальное время. Метод эллипсоидов является также алгоритмом полиномиального времени, но он оказался неэффективным в практических приложениях.

Если  — число переменных, и  — число битов входных данных, алгоритм Кармаркара требует операций над числами с знаками, в то время как метод эллипсоидов требует таких операций. Время работы алгоритма Кармаркара равно

при использовании метода умножения Шёнхаге — Штрассена (см. «O» большое).

Алгоритм Кармаркара принадлежит классу методов внутренней точки — текущее допустимое решение не передвигается по границе области допустимых решений как в симплекс-методе, а движется по внутренним точкам области допустимых значений, улучшая с каждой итерацией аппроксимацию оптимального решения определённой дробью и приводя к оптимальному решению с рациональными данными[1].

Рассмотрим задачу линейного программирования в матричной форме:

максимизировать cTx
при ограничениях Axb.

Алгоритм определяет очередное допустимое направление в сторону оптимального решения и отступает на множитель 0 < γ ⩽ 1.

Алгоритм Кармаркара весьма сложен. Заинтересованные читатели могут найти информацию по ссылкам[2][3][4] [5][6][7][8]. Упрощённая версия, носящая название «Метод аффинного масштабирования», анализируемая в других статьях[9], может быть описана кратко следующим образом. Заметьте, что метод аффинного масштабирования, когда используется для задач малых размеров, не является алгоритмом полиномиального времени. Для задач большого размера и сложных задач следует придерживаться исходного подхода. Кармаркар также расширил методологию[10][11][12][13] решения задач с целыми ограничениями и невыпуклых задач[14].

  Вход:  A, b, c, , Критерий остановки, .
  
  do while критерий остановки не выполняется
     
     
     
     
     if  then
        return неограниченное решение
     end if
     
     
     
  end do

Здесь

  • «←» является сокращением «изменить на». Например, «largest ← item» означает, что значение переменной largest заменяется на значение переменной item.
  • «return» прерывает работу алгоритма и выводит значение, которое записано после команды.
Пример решения

Пусть дана задача линейного программирования

максимизировать
при условиях

То есть имеются две переменные и 11 ограничений, соответствующих различным значениям . Рисунок показывает каждую итерацию алгоритма как красную точку. Ограничения показаны синими прямыми.

Дебаты о патентовании — Можно ли патентовать математику?

[править | править код]

Во время, когда Наренда Кармаркар предложил свой алгоритм, он работал в AT&T. После внедрения алгоритма для оптимизации телефонной сети AT&T[15] там осознали, что он может иметь практическую важность. В апреле 1985 года AT&T быстро подала заявку на патент алгоритма Кармаркара, и это событие подлило масла в разгорающиеся дебаты вокруг патентования программного обеспечения[16]. Это привело в беспокойство многих математиков, как, например, Рональда Ривеста (он сам является одним из держателей патента на алгоритм RSA), выразившего мнение, что исследования, основанные на базе этого алгоритма, должны бы быть свободными. Даже ещё до утверждения патента некоторые утверждали, что существовал неосуществлённый прототип[англ.][17].

Математики, специализирующиеся в методах вычислений, такие как Филип Гилл (Philip Gill) и другие, утверждали, что алгоритм Кармаркара эквивалентен проективному барьерному методу Ньютона с логарифмической барьерной функцией, если правильно выбрать параметры[18]. Однако аргумент Гилла имеет недостаток, поскольку метод, который он описывает, даже не считается «алгоритмом», поскольку требует выбора параметров, которые не обусловлены внутренней логикой метода и полностью полагаются на внешнее управление, особенно что касается алгоритма Кармаркара[19]. Более того, вклад Кармаркара далёк от очевидного в свете всех предшествующих работ, включая работы Фиако — МакКормика (Fiacco–McCormick), Гилла (Gill) и других, перечисленных Зальцманом (Saltzman)[19][20][21]. Патент обсуждался в сенате США, был одобрен как признание существенной оригинальности работы Кармаркара и был оформлен как патент США 4744026 «Методы и аппаратура для эффективного распределения ресурсов» в мае 1988. AT&T поставил систему KORBX[22] [23], базирующуюся на этом патенте, Пентагону[24][25], который использовал её для решения математических задач, которые до этого считались неразрешимыми.

Оппоненты программного патентирования позднее заявляли, что патенты разрушили положительный цикл взаимодействия, который характеризовал связь исследователей в линейном программировании и производством, и, в частности, изолировали самого Кармаркара от математических исследований в его области[26].

Действие патента истекло в апреле 2006 года, и алгоритм в настоящее время является всеобщим достоянием.

Примечания

[править | править код]
  1. Gilbert Strang. Karmarkar’s algorithm and its place in applied mathematics (англ.) // The Mathematical Intelligencer. — New York: Springer, 1987. — Vol. 9, iss. 2. — P. 4—10. — ISSN 0343-6993. — doi:10.1007/BF03025891.
  2. A new polynomial-time algorithm for linear programming. Дата обращения: 26 августа 2015. Архивировано 14 февраля 2019 года.
  3. A new polynomial-time algorithm for linear programming — Springer. Дата обращения: 29 сентября 2017. Архивировано 6 сентября 2017 года.
  4. Power Series Variants of Karmarkar-Type Algorithms — Karmarkar — 2013 — AT&T Technical Journal — Wiley Online Library. Дата обращения: 26 августа 2015. Архивировано 16 июля 2015 года.
  5. Karmarkar N. K., An InteriorPoint Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, p. 297308 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Архивная копия от 4 марта 2016 на Wayback Machine
  6. Karmarkar, N. K., Riemannian Geometry Underlying Interior Point Methods for Linear programming, AMS series on Contemporary Mathematics 114, p. 5175 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Архивная копия от 4 марта 2016 на Wayback Machine
  7. Karmarkar N. K., Lagarias, J. C., Slutsman, L., Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
  8. Архивированная копия. Дата обращения: 26 августа 2015. Архивировано из оригинала 4 марта 2016 года.
  9. Robert J. Vanderbei, Marc Meketon, Barry Freedman. A Modification of Karmarkar's Linear Programming Algorithm // Algorithmica. — 1986. — Т. 1. — С. 395—407. — doi:10.1007/BF01840454.
  10. Karmarkar, N. K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, p. 160181 (1991).
  11. Karmarkar, N. K. Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, p. 125140, Princeton University Press (1992).
  12. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).
  13. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).
  14. Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010.
  15. Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., Ramakrishnan K. G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).
  16. Gina Kolata. IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes (англ.) // The New York Times. — 1989-03-12.
  17. Various posts by Matthew Saltzman, Clemson University. Дата обращения: 26 августа 2015. Архивировано 23 сентября 2015 года.
  18. Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, Margaret H. Wright. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method // Mathematical Programming. — 1986. — Т. 36. — С. 183—209. — doi:10.1007/BF02592025.
  19. 1 2 Andrew Chin. On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens // Journal Of Intellectual Property Law. — 2009. — Т. 16. — С. 214—223.
  20. Mark A. Paley (1995). «The Karmarkar Patent: Why Congress Should „Open the Door“ to Algorithms as Patentable Subject Matter». 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. — Т. 42. — С. 39—56.
  22. Marc S. Meketon, Y. C. Cheng, D. J. Houck, J. M. Liu, L. Slutsman, Robert J. Vanderbei, P. Wang. The AT&T KORBX System // AT&T Technical Journal. — 1989. — Т. 68. — С. 7—19.
  23. Big A.T.&T. Computer for Complexities — NYTimes.com. Дата обращения: 29 сентября 2017. Архивировано 1 февраля 2018 года.
  24. Military Is First Announced Customer Of AT&T Software. Дата обращения: 26 августа 2015. Архивировано 6 сентября 2015 года.
  25. IEEE Xplore Abstract — Using KORBX for military airlift applications. Дата обращения: 26 августа 2015. Архивировано 13 ноября 2014 года.
  26. 今野浩: カーマーカー特許とソフトウェア – 数学は 特許に なるか (Konno Hiroshi: The Kamarkar Patent and Software – Has Mathematics Become Patentable?). — FFII. Архивировано 27 июня 2008 года.

Литература

[править | править код]