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

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

Если $n$ — число переменных, и $L$ — число битов входных данных, алгоритм Кармаркара требует $O(n^{3{,}5}L)$ операций над числами с $O(L)$ знаками, в то время как метод эллипсоидов требует $O(n^{6}L)$ таких операций. Время работы алгоритма Кармаркара равно

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

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

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

Алгоритм

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

максимизировать c^Tx

при ограничениях Ax ⩽ b.

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

Алгоритм Кармаркара весьма сложен. Заинтересованные читатели могут найти информацию по ссылкам. Упрощённая версия, носящая название «Метод аффинного масштабирования», анализируемая в других статьях, может быть описана кратко следующим образом. Заметьте, что метод аффинного масштабирования, когда используется для задач малых размеров, не является алгоритмом полиномиального времени. Для задач большого размера и сложных задач следует придерживаться исходного подхода. Кармаркар также расширил методологию решения задач с целыми ограничениями и невыпуклых задач.

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

  $k\leftarrow 0$
  do while критерий остановки не выполняется
     $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}\geqslant 0$ then
        return неограниченное решение
     end if
     $\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\mid (h_{v})_{i}<0,\,i=1,\ldots ,m\}$
     $x^{k+1}\leftarrow x^{k}+\alpha h_{x}$
     $k\leftarrow k+1$
  end do

Здесь

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

Пример

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

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

максимизировать $x_{1}+x_{2}$

при условиях $2px_{1}+x_{2}\leqslant p^{2}+1,\ p=0{,}0,\,0{,}1,\,0{,}2,\,\ldots ,0{,}9,\,1{,}0.$

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

Дебаты о патентовании — Можно ли патентовать математику?

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

Математики, специализирующиеся в методах вычислений, такие как Филип Гилл (Philip Gill) и другие, утверждали, что алгоритм Кармаркара эквивалентен проективному барьерному методу Ньютона с логарифмической барьерной функцией, если правильно выбрать параметры. Однако аргумент Гилла имеет недостаток, поскольку метод, который он описывает, даже не считается «алгоритмом», поскольку требует выбора параметров, которые не обусловлены внутренней логикой метода и полностью полагаются на внешнее управление, особенно что касается алгоритма Кармаркара. Более того, вклад Кармаркара далёк от очевидного в свете всех предшествующих работ, включая работы Фиако — МакКормика (Fiacco–McCormick), Гилла (Gill) и других, перечисленных Зальцманом (Saltzman). Патент обсуждался в сенате США, был одобрен как признание существенной оригинальности работы Кармаркара и был оформлен как патент США 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.