Алгоритм Кармаркара: История и Значение в Линейном Программировании
Karmarkar's algorithm
Алгоритм Кармаркара: эффективное решение задач линейного программирования за полиномиальное время. Преимущества перед методом эллипсоидов и сложность вычислений.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм Кармаркара — это алгоритм, предложенный Нарендрой Кармаркаром в 1984 году для решения задач линейного программирования. Он стал первым достаточно эффективным алгоритмом, решающим эти задачи за полиномиальное время. Эллипсоидный метод также является полиномиальным, но на практике оказался неэффективным. Обозначим число переменных как *n*, число неравенств как *m*, а число битов входных данных алгоритма как *L*. Алгоритм Кармаркара требует *O(n<sup>2</sup>L log n)* операций с *L*-битовыми числами, в то время как эллипсоидному алгоритму требуется *O(n<sup>6</sup>L log n)* таких операций. В "квадратных" задачах, когда *m* находится в *O(n)*, алгоритм Кармаркара требует *O(n<sup>3</sup>L log n)* операций с *L*-битовыми числами, в то время как эллипсоидному алгоритму требуется *O(n<sup>6</sup>L log n)* таких операций. Таким образом, время работы алгоритма Кармаркара составляет
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice. Denoting by the number of variables, m the number of inequality constraints, and the number of bits of input to the algorithm, Karmarkar's algorithm requires operations on digit numbers, as compared to such operations for the ellipsoid algorithm. In "square" problems, when m is in O(n), Karmarkar's algorithm requires operations on digit numbers, as compared to such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus
при использовании умножения на основе БПФ (см. нотацию «Большое О»). Алгоритм Кармаркара относится к классу методов внутренней точки: текущее приближение решения не следует по границе допустимой области, как в симплекс-методе, а перемещается внутри допустимой области, улучшая приближение оптимального решения на определенную долю с каждой итерацией и сходясь к оптимальному решению при рациональных данных.
using FFT based multiplication (see Big O notation). Karmarkar's algorithm falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration and converging to an optimal solution with rational data.
Спор о патентах
В то время, когда он изобрел алгоритм, Кармаркар работал в IBM в качестве постдокторанта в Исследовательской лаборатории IBM в Сан-Хосе, Калифорния. 11 августа 1983 года он выступил с семинаром в Стэнфордском университете, представляя алгоритм, при этом его принадлежность по-прежнему указывалась как IBM. Осенью 1983 года Кармаркар начал работать в AT&T и представил свою работу на Симпозиуме ACM по теории вычислений (STOC, проходившем с 30 апреля по 2 мая 1984 года), указав AT&T Bell Laboratories в качестве своей организации. После применения алгоритма для оптимизации телефонной сети AT&T, они осознали, что его изобретение может иметь практическую ценность. В апреле 1985 года AT&T незамедлительно подала заявку на патент на его алгоритм. Патент стал дополнительным аргументом в продолжающихся спорах о патентовании программного обеспечения. Это вызвало обеспокоенность у многих математиков, таких как Рональд Ривест (сам являющийся одним из владельцев патента на алгоритм RSA), который выразил мнение, что исследования должны основываться на принципе свободы алгоритмов. Еще до выдачи патента, высказывались предположения о существовании предшествующего уровня техники. Математики, специализирующиеся на численном анализе, включая Филипа Гилла и других, утверждали, что алгоритм Кармаркара эквивалентен методу Ньютона с барьером и логарифмической функцией барьера, при соответствующем выборе параметров. Юрист Эндрю Чин считает, что аргумент Гилла был несостоятелен, поскольку описанный ими метод не является "алгоритмом", так как требует выбора параметров, не вытекающих из внутренней логики метода, а зависящих от внешнего управления, по сути, от алгоритма Кармаркара. Более того, вклад Кармаркара считается весьма неочевидным в свете всех предшествующих работ, включая работы Фиакко-Маккормика, Гилла и других, упомянутых Солтцманом. Патент обсуждался в Сенате США и был выдан в мае 1988 года в знак признания существенной оригинальности работы Кармаркара под названием: "Методы и аппаратура для эффективного распределения ресурсов". AT&T разработала векторную мультипроцессорную компьютерную систему специально для запуска алгоритма Кармаркара, назвав полученную комбинацию аппаратного и программного обеспечения KORBX, и продавала эту систему по цене 8,9 миллиона долларов США. Первым клиентом стал Пентагон. Противники патентов на программное обеспечение утверждали, что патенты разрушили положительные циклы взаимодействия, которые ранее характеризовали отношения между исследователями в области линейного программирования и промышленностью, и, в частности, изолировали самого Кармаркара от сети математических исследователей в его области. Срок действия патента истек в апреле 2006 года, и в настоящее время алгоритм находится в общественном достоянии. Верховный суд США постановил в деле Gottschalk v. Benson, что математику нельзя патентовать. В этом деле суд впервые рассмотрел вопрос о возможности патентования компьютерных алгоритмов и постановил, что это невозможно, поскольку патентная система не защищает идеи и подобные абстракции. В деле Diamond v. Diehr Верховный суд заявил: "Математическая формула сама по себе не подлежит защите наших патентных законов, и этот принцип нельзя обойти, пытаясь ограничить использование формулы определенной технологической средой". В деле Mayo Collaborative Services v. Prometheus Labs., Inc. Верховный суд далее пояснил, что "простое применение математического принципа на физической машине, а именно на компьютере, не является патентоспособным применением этого принципа".
At the time he invented the algorithm, Karmarkar was employed by IBM as a postdoctoral fellow in the IBM San Jose Research Laboratory in California. On August 11, 1983 he gave a seminar at Stanford University explaining the algorithm, with his affiliation still listed as IBM. By the fall of 1983 Karmarkar started to work at AT&T and submitted his paper to the 1984 ACM Symposium on Theory of Computing (STOC, held April 30 May 2, 1984) stating AT&T Bell Laboratories as his affiliation. After applying the algorithm to optimizing AT&T's telephone network, they realized that his invention could be of practical importance. In April 1985, AT&T promptly applied for a patent on his algorithm. The patent became more fuel for the ongoing controversy over the issue of software patents. This left many mathematicians uneasy, such as Ronald Rivest (himself one of the holders of the patent on the RSA algorithm), who expressed the opinion that research proceeded on the basis that algorithms should be free. Even before the patent was actually granted, it was argued that there might have been prior art that was applicable. Mathematicians who specialized in numerical analysis, including Philip Gill and others, claimed that Karmarkar's algorithm is equivalent to a projected Newton barrier method with a logarithmic barrier function, if the parameters are chosen suitably. Legal scholar Andrew Chin opines that Gill's argument was flawed, insofar as the method they describe does not constitute an "algorithm", since it requires choices of parameters that don't follow from the internal logic of the method, but rely on external guidance, essentially from Karmarkar's algorithm. Furthermore, Karmarkar's contributions are considered far from obvious in light of all prior work, including Fiacco McCormick, Gill and others cited by Saltzman. The patent was debated in the U. S. Senate and granted in recognition of the essential originality of Karmarkar's work, as : "Methods and apparatus for efficient resource allocation" in May 1988. AT&T designed a vector multi processor computer system specifically to run Karmarkar's algorithm, calling the resulting combination of hardware and software KORBX, and marketed this system at a price of US$8.9 million. Its first customer was the Pentagon. Opponents of software patents have further argued that the patents ruined the positive interaction cycles that previously characterized the relationship between researchers in linear programming and industry, and specifically it isolated Karmarkar himself from the network of mathematical researchers in his field. The patent itself expired in April 2006, and the algorithm is presently in the public domain. The United States Supreme Court has held that mathematics cannot be patented in Gottschalk v. Benson, In that case, the Court first addressed whether computer algorithms could be patented and it held that they could not because the patent system does not protect ideas and similar abstractions. In Diamond v. Diehr, the Supreme Court stated, "A mathematical formula as such is not accorded the protection of our patent laws, and this principle cannot be circumvented by attempting to limit the use of the formula to a particular technological environment. In Mayo Collaborative Services v. Prometheus Labs., Inc., the Supreme Court explained further that "simply implementing a mathematical principle on a physical machine, namely a computer, [i]s not a patentable application of that principle."
Приложения
Алгоритм Кармаркара использовался армией США для логистического планирования во время войны в Персидском заливе.
Karmarkar's algorithm was used by the US Army for logistic planning during the Gulf war.