Алгоритм Кармаркара - это алгоритм, представленный Нарендрой Кармаркаром в 1984 году для решения задач линейного программирования . Это был первый достаточно эффективный алгоритм, решающий эти проблемы за полиномиальное время . Метод эллипсоидов также является полиномиальным по времени, но на практике оказался неэффективным.
Обозначение как количество переменных и в качестве количества битов на входе в алгоритм алгоритм Кармаркара требует операции на цифры числа, по сравнению с такие операции для алгоритма эллипсоида. Таким образом, время выполнения алгоритма Кармаркара
с использованием умножения на основе БПФ (см. нотацию Big O ).
Алгоритм Кармаркара относится к классу методов внутренней точки : текущее предположение для решения не следует за границей допустимого множества, как в симплекс-методе , но оно перемещается через внутреннюю часть допустимой области, улучшая приближение оптимального решения. на определенную долю с каждой итерацией и сходится к оптимальному решению с рациональными данными. [1]
Алгоритм
Рассмотрим задачу линейного программирования в матричной форме:
максимизировать c T x | |
при условии | Ax ≤ b . |
Алгоритм Кармаркара определяет следующее возможное направление к оптимальности и уменьшает коэффициент 0 <γ ≤ 1 . Это описано в ряде источников. [2] [3] [4] [5] [6] [7] Кармаркар также расширил метод [8] [9] [10] [11] для решения задач с целочисленными ограничениями и невыпуклых задач. [12]
Алгоритм аффинного масштабирования
Поскольку реальный алгоритм довольно сложен, исследователи искали его более интуитивную версию, и в 1985 году разработали аффинное масштабирование , версию алгоритма Кармаркара, которая использует аффинные преобразования, где Кармаркар использовал проективные , только чтобы через четыре года понять, что они открыли заново. алгоритм, опубликованный советским математиком И.И. Дикиным в 1967 году. [13] Метод аффинного масштабирования можно кратко описать следующим образом. [14] Алгоритм аффинного масштабирования, хотя и применим к мелкомасштабным задачам, не является алгоритмом с полиномиальным временем. [ необходима цитата ]
Ввод: A, b, c, , критерий остановки , γ .
делать при остановке критерий не выполняется если затем вернуть неограниченный конец, если конец делать
- «←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
- « return » завершает алгоритм и выводит следующее значение.
Пример
Рассмотрим линейную программу
То есть есть 2 переменные и 11 ограничений, связанных с различными значениями . На этом рисунке каждая итерация алгоритма показана в виде красных кружков. Ограничения показаны синими линиями.
Патентный спор: можно ли запатентовать математику?
В то время, когда он изобрел алгоритм, Кармаркар работал в IBM в качестве постдокторанта в исследовательской лаборатории IBM в Сан-Хосе в Калифорнии. 11 августа 1983 года он провел семинар в Стэнфордском университете, где объяснил алгоритм, и его организация все еще числилась IBM. К осени 1983 года Кармаркар начал работать в AT&T и представил свой доклад на симпозиуме ACM по теории вычислений 1984 года (STOC, проводившийся 30 апреля - 2 мая 1984 года), указав в AT&T Bell Laboratories как на свою организацию. [15] После применения алгоритма для оптимизации телефонной сети AT&T, [16] они поняли, что его изобретение может иметь практическое значение. В апреле 1985 года AT&T незамедлительно подала заявку на патент на алгоритм Кармаркара.
Патент стал еще большей причиной продолжающихся споров по вопросу о патентах на программы . [17] Это вызвало беспокойство у многих математиков, таких как Рональд Ривест (сам один из обладателей патента на алгоритм RSA ), который выразил мнение, что исследования проводятся на основе того, что алгоритмы должны быть бесплатными. Еще до того, как патент был фактически выдан, утверждалось, что мог существовать известный уровень техники, который был применим. [18] Математики, специализирующиеся на численном анализе , в том числе Филип Гилл и другие, утверждали, что алгоритм Кармаркара эквивалентен методу прогнозируемого барьера Ньютона с логарифмической барьерной функцией , если параметры выбраны подходящим образом. [19] Юрист Эндрю Чин полагает, что аргумент Гилла ошибочен, поскольку метод, который они описывают, не представляет собой «алгоритм», поскольку он требует выбора параметров, которые не следуют из внутренней логики метода, но полагаются на внешнее руководство, по сути, из алгоритма Кармаркара. [20] Кроме того, вклад Кармаркара считается далеко не очевидным в свете всей предыдущей работы, включая Фиакко-Маккормик, Гилла и других, которых цитирует Зальцман. [20] [21] [22] Патент обсуждался в Сенате США [ необходима цитата ] и выдан в знак признания существенной оригинальности работы Кармаркара, как патент США 4744028 : «Методы и устройство для эффективного распределения ресурсов» в мае 1988 г. .
AT&T разработала векторную многопроцессорную компьютерную систему специально для выполнения алгоритма Кармаркара, назвав полученную комбинацию аппаратного и программного обеспечения KORBX [23], и продала эту систему по цене 8,9 миллиона долларов США. [24] [25] Первым заказчиком был Пентагон . [26] [27]
Противники патентов на программное обеспечение также утверждали, что патенты разрушили циклы позитивного взаимодействия, которые ранее характеризовали отношения между исследователями линейного программирования и промышленностью, и, в частности, изолировали самого Кармаркара от сети математических исследователей в его области. [28]
Срок действия самого патента истек в апреле 2006 года, и в настоящее время алгоритм находится в открытом доступе .
Верховный суд США постановил , что математика не может быть запатентован в Gottschalk ст. Бенсон , [29] В этом случае, суд первой обратился , может ли быть запатентованы компьютерные алгоритмы и считали , что они не могли , потому что патентная система не защищает идеи и подобные абстракции. В Алмазной v. Diehr , [30] Верховный суд заявил, что «математическая формула , как таковой, не наделяется защитой наших патентных законов, и этот принцип не может быть обойден, пытаясь ограничить использование формулы для конкретной технологической среды . [31] в Mayo Collaborative Services против Прометея Labs., Inc. , [32] Верховный суд разъяснил далее , что «просто реализует математический принцип на физической машине, а именно компьютер, [я] S не патентоспособное применение этот принцип ». [33]
Рекомендации
- Адлер, Илан; Кармаркар, Нарендра; Ресенде, Маурисио Г.К .; Вейга, Геральдо (1989). «Реализация алгоритма Кармаркара для линейного программирования». Математическое программирование . 44 (1–3): 297–335. DOI : 10.1007 / bf01587095 .
- Нарендра Кармаркар (1984). « Новый алгоритм полиномиального времени для линейного программирования », Combinatorica , Vol 4 , nr. 4, стр. 373–395.
- ^ Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». Математический интеллигент . 9 (2): 4–10. DOI : 10.1007 / BF03025891 . ISSN 0343-6993 . Руководство по ремонту 0883185 .
- ^ http://dl.acm.org/citation.cfm?id=808695
- ^ Кармаркар, Н. (1984). «Новый алгоритм полиномиального времени для линейного программирования». Combinatorica . 4 (4): 373–395. DOI : 10.1007 / BF02579150 .
- ^ Кармаркар, Нарендра К. (1989). "Варианты степенных рядов алгоритмов типа Кармаркара". Технический журнал AT&T . 68 (3): 20–36. DOI : 10.1002 / j.1538-7305.1989.tb00316.x .
- ^ Кармаркар, Нарендра (1990). «Подход внутренней точки к NP-полным задачам. I». Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988) . Современная математика. 114 . Провиденс, Род-Айленд: Американское математическое общество. С. 297–308. DOI : 10.1090 / conm / 114/1097880 . Руководство по ремонту 1097880 .
- ^ Кармаркар, Нарендра (1990). "Риманова геометрия, лежащая в основе методов внутренней точки для линейного программирования". Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988) . Современная математика. 114 . Провиденс, Род-Айленд: Американское математическое общество. С. 51–75. DOI : 10.1090 / conm / 114/1097865 . Руководство по ремонту 1097865 .
- ^ Кармаркара NK, Lagarias, JC, Slutsman Л., Ван, П., Power Series Варианты KarmarkarType алгоритма, AT & T технический журнал 68, № 3, май / июнь (1989).
- ^ Кармаркар, Н.К., Методы внутренней точки в оптимизации, Труды Второй Международной конференции по промышленной и прикладной математике, SIAM, стр. 160181 (1991)
- ^ Кармаркар, Н.К. и Камат, А.П., Непрерывный подход к получению верхних границ в задачах квадратичной максимизации с целочисленными ограничениями, Последние достижения в глобальной оптимизации, стр. 125140, Princeton University Press (1992).
- ^ 26. Кармаркар, Н.К., Такур, С.А., Подход внутренней точки к проблеме тензорной оптимизации с применением к верхним границам в задачах целочисленной квадратичной оптимизации, Труды Второй конференции по целочисленному программированию и комбинаторной оптимизации (май 1992 г.).
- ^ 27. Камат А., Кармаркар Н.К. Непрерывный метод вычисления границ в задачах целочисленной квадратичной оптимизации, Журнал глобальной оптимизации (1992).
- ^ Кармаркар, Н.К., Помимо выпуклости: новые перспективы в вычислительной оптимизации. Конспект лекций Springer по информатике LNCS 6457, декабрь 2010 г.
- ^ Vanderbei, RJ; Лагариас, JC (1990). «Результат сходимости И. И. Дикина для алгоритма аффинного масштабирования». Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988) . Современная математика. 114 . Провиденс, Род-Айленд: Американское математическое общество. С. 109–119. DOI : 10.1090 / conm / 114/1097868 . Руководство по ремонту 1097868 .
- ^ Роберт Дж. Вандербей ; Мекетон, Марк; Фридман, Барри (1986). «Модификация алгоритма линейного программирования Кармаркара» (PDF) . Алгоритмика . 1 (1–4): 395–407. DOI : 10.1007 / BF01840454 .
- ^ Алгоритм Кармаркара , IBM Research , получено 1 июня 2016 г.
- ↑ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A., and Ramakrishnan KG, Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS '86, Tarpon Springs, Florida (июнь 1986).
- ^ Колата, Джина (1989-03-12). «ИДЕИ И ТЕНДЕНЦИИ; математики обеспокоены утверждениями о своих рецептах» . Нью-Йорк Таймс .
- ^ Различные сообщения Мэтью Зальцмана, Университет Клемсона
- ^ Гилл, Филип Э .; Мюррей, Уолтер; Сондерс, Майкл А .; Tomlin, JA; Райт, Маргарет Х. (1986). «О проектируемых барьерных методах Ньютона для линейного программирования и эквивалентности проективному методу Кармаркара». Математическое программирование . 36 (2): 183–209. DOI : 10.1007 / BF02592025 .
- ^ а б Эндрю Чин (2009). «Об абстракции и эквивалентности в патентной доктрине программного обеспечения: ответ Бессену, Мейреру и Клеменсу» (PDF) . Журнал права интеллектуальной собственности . 16 : 214–223.
- Перейти ↑ Mark A. Paley (1995). «Патент Кармаркара: почему Конгресс должен« открыть дверь »алгоритмам как патентоспособной теме». 22 Компьютер L. Rep. 7
- ^ Маргарет Х. Райт (2004). «Внутренняя революция в оптимизации: история, последние события и долгосрочные последствия» (PDF) . Бюллетень Американского математического общества . 42 : 39–56. DOI : 10.1090 / S0273-0979-04-01040-7 .
- ^ Марк С. Мекетон; YC Cheng; DJ Houck; JMLiu; Л. Слуцман; Роберт Дж. Вандербей ; П. Ван (1989). «Система AT&T KORBX». Технический журнал AT&T . 68 (3): 7–19. DOI : 10.1002 / j.1538-7305.1989.tb00315.x .
- ^ Левенштейн, Роджер (15 августа 1988 г.). «Средство для решения проблем AT&T, основанное на находке знатока математики, за 8,9 миллиона долларов» (PDF) . Wall Street Journal .
- ^ Марков, Джон (13 августа 1988 г.). "Big AT&T. Компьютер для сложностей" .
- ^ «Военные - первый заказчик программного обеспечения AT&T» . AP News . Проверено 11 июня 2019 .
- ^ Кеннингтон, Дж. Л. (1989). «Использование KORBX для военных воздушных перевозок». Труды 28-й конференции IEEE по решениям и контролю . С. 1603–1605. DOI : 10.1109 / CDC.1989.70419 .
- ^ «野 浩: カ ー マ ー カ ー 特許 フ ト ウ ェ ア - 数学 は 特許 に な る か (Конно Хироши: Патент Камаркара и программное обеспечение - стала ли математика патентоспособной?)» . FFII . Архивировано из оригинала на 2008-06-27 . Проверено 27 июня 2008 .
- ^ 409 США 63 (1972). Дело касалось алгоритма преобразования двоичных десятичных чисел в чисто двоичные.
- ^ 450 США 175 (1981).
- ^ 450 US at 191. См. Также Parker v. Flook , 437 US 584, 585 (1978) («открытие новой полезной математической формулы не может быть запатентовано»).
- ^ 566 США __, 132 S. Ct. 1289 (2012).
- ^ Accord Alice Corp. против CLS Bank Int'l , 573 США __, 134 S. Ct. 2347 (2014).