Алгоритм Кармаркарса - Karmarkars algorithm

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

Обозначение ${\displaystyle n}$ как количество переменных и ${\displaystyle L}$ в качестве количества битов на входе в алгоритм алгоритм Кармаркара требует ${\displaystyle O(n^{3.5}L)}$ операции на ${\displaystyle O(L)}$ цифры числа, по сравнению с ${\displaystyle O(n^{6}L)}$ такие операции для алгоритма эллипсоида. Таким образом, время выполнения алгоритма Кармаркара

${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}$

с помощью Умножение на основе БПФ (видеть Обозначение Big O ).

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

Алгоритм

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

максимизировать c^ТИкс
при условии	Топор ≤ б.

Алгоритм Кармаркара определяет следующее возможное направление к оптимальности и сокращается в несколько раз. 0 <γ ≤ 1. Это описано в ряде источников.^{[2][3][4][5][6][7]} Кармаркар также расширил метод^{[8][9][10][11]} для решения задач с целочисленными ограничениями и невыпуклых задач.^[12]

Алгоритм Аффинное масштабирование

Поскольку реальный алгоритм довольно сложен, исследователи искали его более интуитивную версию, и в 1985 году разработали аффинное масштабирование, версия алгоритма Кармаркара, использующая аффинные преобразования где Кармаркар использовал проективный только для того, чтобы через четыре года понять, что они заново открыли алгоритм, опубликованный Советский математик И. И. Дикин в 1967 г.^[13] Кратко метод аффинного масштабирования можно описать следующим образом.^[14] Алгоритм аффинного масштабирования, хотя и применим к мелкомасштабным задачам, не является алгоритмом с полиномиальным временем.^{[нужна цитата ]}

Ввод: A, b, c, ${\displaystyle x^{0}}$, критерий остановки, γ.

${\displaystyle k\leftarrow 0}$делать пока критерий остановки не удовлетворены    ${\displaystyle v^{k}\leftarrow b-Ax^{k}}$    ${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$    ${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$    ${\displaystyle h_{v}\leftarrow -Ah_{x}}$    если ${\displaystyle h_{v}\geq 0}$ тогда        возвращаться неограниченный конец, если    ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$    ${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$    ${\displaystyle k\leftarrow k+1}$конец делать

• «←» означает назначение. Например, "самый большой ← элемент"означает, что стоимость самый большой изменяет стоимость элемент.
• "возвращаться"завершает алгоритм и выводит следующее значение.

Пример

Пример решения

Рассмотрим линейную программу

${\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}$

То есть есть 2 переменные ${\displaystyle x_{1},x_{2}}$ и 11 ограничений, связанных с различными значениями ${\displaystyle p}$. На этом рисунке каждая итерация алгоритма показана в виде красных кружков. Ограничения показаны синими линиями.

Патентный спор: можно ли запатентовать математику?

Когда он изобрел алгоритм, Кармаркар работал на 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] Это беспокоило многих математиков, таких как Рональд Ривест (сам один из обладателей патента на ЮАР Алгоритм), который выразил мнение, что исследования проводились исходя из того, что алгоритмы должны быть бесплатными. Еще до того, как патент был фактически выдан, утверждалось, что могло быть предшествующий уровень техники это было применимо.^[18] Математики, специализирующиеся на числовой анализ, включая Филип Гилл и другие, утверждали, что алгоритм Кармаркара эквивалентен прогнозируемый метод барьера Ньютона с логарифмической барьерная функция, если параметры выбраны соответствующим образом.^[19] Юрист Эндрю Чин полагает, что аргумент Гилла ошибочен, поскольку метод, который они описывают, не представляет собой «алгоритм», поскольку он требует выбора параметров, которые не следуют из внутренней логики метода, а полагаются на внешнее руководство. по существу из алгоритма Кармаркара.^[20] Более того, вклад Кармаркара считается далеко не очевидным в свете всей предыдущей работы, включая Фиакко-Маккормик, Гилла и других, которых цитирует Зальцман.^[20][21][22] Патент обсуждался в Сенате США.^{[нужна цитата ]} и предоставлен в знак признания существенной оригинальности работы Кармаркара, поскольку Патент США 4744028: «Методы и аппараты для эффективного распределения ресурсов» в мае 1988 г.

AT&T разработала вектор мультипроцессор компьютерная система специально для запуска алгоритма Кармаркара, называя полученную комбинацию аппаратного и программного обеспечения KORBX,^[23] и продал эту систему по цене 8,9 млн долларов США.^[24][25] Первым его заказчиком был Пентагон.^[26][27]

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

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

В Верховный суд США утверждал, что математику нельзя запатентовать в Готтшалк против Бенсона,^[29] В этом деле Суд сначала рассмотрел вопрос о том, можно ли запатентовать компьютерные алгоритмы, и постановил, что это невозможно, поскольку патентная система не защищает идеи и аналогичные абстракции. В Даймонд против Дьера,^[30] Верховный суд заявил: «Математическая формула как таковая не находится под защитой наших патентных законов, и этот принцип нельзя обойти, пытаясь ограничить использование формулы определенной технологической средой.^[31] В Mayo Collaborative Services против Prometheus Labs., Inc.,^[32] Верховный суд далее пояснил, что «простая реализация математического принципа на физической машине, а именно на компьютере, [я] не является патентоспособным применением этого принципа».^[33]

Рекомендации

• Адлер, Илан; Кармаркар, Нарендра; Resende, Mauricio G.C .; Вейга, Джеральдо (1989). «Реализация алгоритма Кармаркара для линейного программирования». Математическое программирование. 44 (1–3): 297–335. Дои:10.1007 / bf01587095.
• Нарендра Кармаркар (1984). "Новый алгоритм полиномиального времени для линейного программирования ", Комбинаторика, Об. 4, № 4, стр. 373–395.

1. Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». Математический интеллект. 9 (2): 4–10. Дои:10.1007 / BF03025891. ISSN  0343-6993. МИСТЕР  0883185.
2. http://dl.acm.org/citation.cfm?id=808695
3. Кармаркар, Н. (1984). «Новый алгоритм полиномиального времени для линейного программирования». Комбинаторика. 4 (4): 373–395. Дои:10.1007 / BF02579150.
4. Кармаркар, Нарендра К. (1989). "Варианты степенных рядов алгоритмов типа Кармаркара". Технический журнал AT&T. 68 (3): 20–36. Дои:10.1002 / j.1538-7305.1989.tb00316.x.
5. Кармаркар, Нарендра (1990). «Подход внутренней точки к NP-полным задачам. I». Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988). Современная математика. 114. Провиденс, Род-Айленд: Американское математическое общество. С. 297–308. Дои:10.1090 / conm / 114/1097880. МИСТЕР  1097880.
6. Кармаркар, Нарендра (1990). "Риманова геометрия, лежащая в основе методов внутренней точки для линейного программирования". Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988). Современная математика. 114. Провиденс, Род-Айленд: Американское математическое общество. С. 51–75. Дои:10.1090 / conm / 114/1097865. МИСТЕР  1097865.
7. Кармаркар Н. К., Лагариас Дж. К., Слуцман Л. и Ван П., Варианты степенных рядов алгоритма KarmarkarType, Технический журнал AT&T 68, № 3, май / июнь (1989).
8. Кармаркар, Н.К., Методы внутренней точки в оптимизации, Труды Второй Международной конференции по промышленной и прикладной математике, SIAM, стр. 160181 (1991)
9. Кармаркар, Н. К., Камат, А. П., Непрерывный подход к получению верхних границ в задачах квадратичной максимизации с целочисленными ограничениями, Последние достижения в глобальной оптимизации, стр. 125140, Princeton University Press (1992).
10. 26. Кармаркар Н. К., Такур С. А. Подход внутренних точек к задаче тензорной оптимизации с применением к верхним границам в задачах целочисленной квадратичной оптимизации, Труды Второй конференции по целочисленному программированию и комбинаторной оптимизации (май 1992 г.).
11. 27. Камат А., Кармаркар Н. К. Непрерывный метод вычисления границ в задачах целочисленной квадратичной оптимизации, Журнал глобальной оптимизации (1992).
12. Кармаркар Н. К. Помимо выпуклости: новые перспективы вычислительной оптимизации. Конспект лекций Springer по информатике LNCS 6457, декабрь 2010 г.
13. Vanderbei, R.J .; Лагариас, Дж. К. (1990). «Результат сходимости И. И. Дикина для алгоритма аффинного масштабирования». Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988). Современная математика. 114. Провиденс, Род-Айленд: Американское математическое общество. С. 109–119. Дои:10,1090 / conm / 114/1097868. МИСТЕР  1097868.
14. Роберт Дж. Вандербей; Meketon, Marc; Фридман, Барри (1986). «Модификация алгоритма линейного программирования Кармаркара» (PDF). Алгоритмика. 1 (1–4): 395–407. Дои:10.1007 / BF01840454.
15. Алгоритм Кармаркара, IBM Research, получено 2016-06-01
16. Синха Л.П., Фридман Б.А., Кармаркар Н.К., Путча А. и Рамакришнан К.Г., Планирование сети за рубежом, Труды третьего международного симпозиума по планированию сети, NETWORKS '86, Тарпон-Спрингс, Флорида (июнь 1986 г.).
17. Колата, Джина (1989-03-12). «ИДЕИ И ТЕНДЕНЦИИ; математиков беспокоят претензии к своим рецептам». Нью-Йорк Таймс.
18. Различные сообщения Мэтью Зальцмана, Университет Клемсона
19. Гилл, Филип Э .; Мюррей, Уолтер; Сондерс, Майкл А .; Tomlin, J. A .; Райт, Маргарет Х. (1986). «О проектируемых барьерных методах Ньютона для линейного программирования и эквивалентности проективному методу Кармаркара». Математическое программирование. 36 (2): 183–209. Дои:10.1007 / BF02592025.
20. Эндрю Чин (2009). «Об абстракции и эквивалентности в патентной доктрине программного обеспечения: ответ Бессену, Мейреру и Клеменсу» (PDF). Журнал права интеллектуальной собственности. 16: 214–223.
21. Марк А. Пейли (1995). «Патент Кармаркара: почему Конгресс должен« открыть дверь »алгоритмам как патентоспособным объектам». 22 Компьютер L. Rep. 7
22. Маргарет Х. Райт (2004). «Революция внутренних точек в оптимизации: история, последние события и долгосрочные последствия» (PDF). Бюллетень Американского математического общества. 42: 39–56. Дои:10.1090 / S0273-0979-04-01040-7.
23. Марк С. Мекетон; Y.C. Ченг; Д.Дж. Хаук; J.M.Liu; Л. Слуцман; Роберт Дж. Вандербей; П. Ван (1989). «Система AT&T KORBX». Технический журнал AT&T. 68 (3): 7–19. Дои:10.1002 / j.1538-7305.1989.tb00315.x.
24. Левенштейн, Роджер (15 августа 1988 г.). «Инструмент для решения проблем AT&T, основанный на находке знатока математики, за 8,9 миллиона долларов» (PDF). Wall Street Journal.
25. Марков, Джон (13 августа 1988 г.). "Big A.T.&T. Компьютер для сложностей".
26. «Военные - первый заказчик программного обеспечения AT&T». AP Новости. Получено 2019-06-11.
27. Кеннингтон, Дж. Л. (1989). «Использование KORBX для военных воздушных перевозок». Материалы 28-й конференции IEEE по решениям и контролю. С. 1603–1605. Дои:10.1109 / CDC.1989.70419.
28. «今 野 浩: カ ー マ ー カ ー 特許 フ ト ウ ェ ア - 数学 は 特許 に な る か (Конно Хироши: Патент Камаркара и программное обеспечение - стала ли математика патентоспособной?)». FFII. Архивировано из оригинал на 2008-06-27. Получено 2008-06-27.
29. 409 U.S. 63 (1972). Дело касалось алгоритма преобразования десятичных чисел в двоичном коде в чисто двоичные.
30. 450 U.S. 175 (1981).
31. 450 U.S. at 191. См. Также Паркер против Флука, 437 U.S. 584, 585 (1978) («открытие новой полезной математической формулы не может быть запатентовано»).
32. 566 U.S. __, 132 S. Ct. 1289 (2012).
33. Согласие Alice Corp. против CLS Bank Int’l, 573 U.S. __, 134 S. Ct. 2347 (2014).