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

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

Обозначая $n$ количество переменных, m количество ограничений-неравенств и $L$ количество бит на входе в алгоритм, алгоритм Кармаркара требует $O(m^{1.5}n^{2}L)$ операции по $O(L)$-значные числа по сравнению с $O(n^{3}(n+m)L)$ такие операции для алгоритма эллипсоида. В «квадратных» задачах, когда m находится в O( n ), алгоритм Кармаркара требует $O(n^{3.5}L)$ операции по $O(L)$-значные числа по сравнению с $O(n^{4}L)$ такие операции для алгоритма эллипсоида. Таким образом, время выполнения алгоритма Кармаркара равно

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

используя умножение на основе БПФ (см. обозначение Big O ).

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

Алгоритм

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

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

Алгоритм Кармаркара определяет следующее возможное направление к оптимальности и уменьшает его в коэффициент 0 < γ ≤ 1 . Оно описано во многих источниках. Кармаркар также расширил метод решать задачи с целочисленными ограничениями и невыпуклые задачи.

Algorithm Affine-Scaling

Поскольку реальный алгоритм довольно сложен, исследователи искали более интуитивную его версию и в 1985 году разработали аффинное масштабирование , версию алгоритма Кармаркара, которая использует аффинные преобразования там, где Кармаркар использовал проективные преобразования, только чтобы четыре года спустя осознать, что они заново открыли алгоритм, опубликованный советским математиком И.И. Дикиным в 1967 году. Метод аффинного масштабирования можно кратко описать следующим образом. Хотя этот алгоритм применим к задачам небольшого масштаба, он не является алгоритмом с полиномиальным временем.

Input:  A, b, c, $x^{0}$, stopping criterion, γ.

$k\leftarrow 0$
do while stopping criterion not satisfied
    $v^{k}\leftarrow b-Ax^{k}$
    $D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})$
    $h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c$
    $h_{v}\leftarrow -Ah_{x}$
    if $h_{v}\geq 0$ then
        return unbounded
    end if
    $\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}$
    $x^{k+1}\leftarrow x^{k}+\alpha h_{x}$
    $k\leftarrow k+1$
end do

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

Пример

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

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

${\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 переменные $x_{1},x_{2}$ и 11 ограничений, связанных с различными значениями $p$. На этом рисунке каждая итерация алгоритма показана точками красного круга. Ограничения показаны синими линиями.

Патентные споры

В то время, когда Кармаркар изобрел алгоритм, он работал в IBM в качестве постдокторанта в исследовательской лаборатории IBM в Сан-Хосе в Калифорнии. 11 августа 1983 года он провел семинар в Стэнфордском университете, объясняя алгоритм, при этом его филиал по-прежнему значился как IBM. К осени 1983 года Кармаркар начал работать в AT&T и представил свою статью на симпозиуме ACM по теории вычислений 1984 года (STOC, состоявшийся 30 апреля - 2 мая 1984 года), указав, что AT&T Bell Laboratories является его филиалом. После применения алгоритма для оптимизации телефонной сети AT&T, они поняли, что его изобретение может иметь практическое значение. В апреле 1985 года AT&T незамедлительно подала заявку на патент на его алгоритм.

Этот патент стал еще одним поводом для продолжающихся споров по поводу патентов на программное обеспечение . Это вызвало беспокойство у многих математиков, таких как Рональд Ривест (сам один из обладателей патента на алгоритм RSA ), который выразил мнение, что исследования проводятся на основе того, что алгоритмы должны быть свободными. Еще до того, как патент был фактически выдан, утверждалось, что, возможно, существовал предшествующий уровень техники , который был бы применим. Математики, специализирующиеся на численном анализе , в том числе Филип Гилл и другие, утверждали, что алгоритм Кармаркара эквивалентен проектируемому барьерному методу Ньютона с логарифмической барьерной функцией , если параметры выбраны соответствующим образом. Ученый-правовед Эндрю Чин полагает, что аргумент Гилла ошибочен, поскольку описываемый ими метод не представляет собой «алгоритм», поскольку он требует выбора параметров, которые не следуют из внутренней логики метода, а полагаются на внешнее руководство. по существу из алгоритма Кармаркара. Более того, вклад Кармаркара считается далеко не очевидным в свете всех предыдущих работ, включая работы Фиакко-Маккормика, Гилла и других, на которые цитирует Зальцман. Патент обсуждался в Сенате США. и выдан в знак признания существенной оригинальности работы Кармаркара в виде патента США 4 744 028 : «Методы и устройства для эффективного распределения ресурсов» в мае 1988 года.

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

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

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

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

Приложения

Алгоритм Кармаркара использовался армией США для логистического планирования во время войны в Персидском заливе .

Ссылки

• Адлер, Илан; Кармаркар, Нарендра; Ресенде, Маурисио Г.К .; Вейга, Джеральдо (1989). «Реализация алгоритма Кармаркара для линейного программирования». Математическое программирование . 44 (1–3): 297–335. дои : 10.1007/bf01587095 . S2CID   12851754 .
• Нарендра Кармаркар (1984). « Новый алгоритм полиномиального времени для линейного программирования », Combinatorica , Vol 4 , nr. 4, с. 373–395.