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

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

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

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

Алгоритм Рассмотрим задачу линейного программирования в матричной форме: максимизировать cTx при ограничениях Ax ⩽ b.

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

Алгоритм Кармаркара весьма сложен. Заинтересованные читатели могут найти информацию по ссылкам 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 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 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).. Упрощённая версия, носящая название «Метод аффинного масштабирования», анализируемая в других статьях, может быть описана кратко следующим образом. Заметьте, что метод аффинного масштабирования, когда используется для задач малых размеров, не является алгоритмом полиномиального времени. Для задач большого размера и сложных задач следует придерживаться исходного подхода. Кармаркар также расширил методологиюKarmarkar, N. K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, p. 160181 (1991).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).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).Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992). решения задач с целыми ограничениями и невыпуклых задачKarmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010..

Вход: A, b, c, , Критерий остановки, .

do while критерий остановки не выполняется

if then return неограниченное решение end if

end do

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

Пример

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

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

Дебаты о патентовании — Можно ли патентовать математику? Во время, когда Наренда Кармаркар предложил свой алгоритм, он работал в AT&T. После внедрения алгоритма для оптимизации телефонной сети AT&TSinha 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). там осознали, что он может иметь практическую важность. В апреле 1985 года AT&T быстро подала заявку на патент алгоритма Кармаркара, и это событие подлило масла в разгорающиеся дебаты вокруг патентования программного обеспечения. Это привело в беспокойство многих математиков, как, например, Рональда Ривеста (он сам является одним из держателей патента на алгоритм RSA), выразившего мнение, что исследования, основанные на базе этого алгоритма, должны бы быть свободными. Даже ещё до утверждения патента некоторые утверждали, что существовал неосуществлённый .

Математики, специализирующиеся в методах вычислений, такие как Филип Гилл (Philip Gill) и другие, утверждали, что алгоритм Кармаркара эквивалентен проективному барьерному методу Ньютона с логарифмической барьерной функцией, если правильно выбрать параметры. Однако аргумент Гилла имеет недостаток, поскольку метод, который он описывает, даже не считается «алгоритмом», поскольку требует выбора параметров, которые не обусловлены внутренней логикой метода и полностью полагаются на внешнее управление, особенно что касается алгоритма Кармаркара. Более того, вклад Кармаркара далёк от очевидного в свете всех предшествующих работ, включая работы Фиако — МакКормика (Fiacco–McCormick), Гилла (Gill) и других, перечисленных Зальцманом (Saltzman)Mark A. Paley (1995). «The Karmarkar Patent: Why Congress Should „Open the Door“ to Algorithms as Patentable Subject Matter». 22 COMPUTER L. REP. 7.. Патент обсуждался в сенате США, был одобрен как признание существенной оригинальности работы Кармаркара и был оформлен как патент США 4744026 «Методы и аппаратура для эффективного распределения ресурсов» в мае 1988. AT&T поставил систему KORBX , базирующуюся на этом патенте, Пентагону, который использовал её для решения математических задач, которые до этого считались неразрешимыми.

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

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

Примечания

Литература Ilan Adler, Narendra Karmarkar, Mauricio G.C. Resende and Geraldo Veiga (1989). «An Implementation of Karmarkar’s Algorithm for Linear Programming». Mathematical Programming, Vol 44, p. 297—335. Narendra Karmarkar (1984). «A New Polynomial Time Algorithm for Linear Programming», Combinatorica, Vol 4, nr. 4, p. 373—395.

Категория:Алгоритмы и методы оптимизации Категория:Патенты и программное обеспечение Категория:Линейное программирование