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

Алгоритм Кармаркара — алгоритм для розв'язування задач лінійного програмування, який 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). Патент обговорювано в сенаті США, схвалено як визнання суттєвої оригінальності роботи Кармаркара та у травні 1988 року оформлено як патент США 4744026 «Методи та апаратура для ефективного розподілу ресурсів». 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.