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

Алгоритм Кармаркара — алгоритм для розв'язування задач лінійного програмування, який 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)}$

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

Алгоритм Кармаркара належить класу методів внутрішньої точки — поточний допустимий розв'язок не пересувається межею області допустимих розв'язків, як у симплекс-методі, а рухається по внутрішніх точках області допустимих значень, покращуючи з кожною ітерацією апроксимацію оптимального розв'язку певним дробом і приводячи до оптимального розв'язку з раціональними даними[1].

Алгоритм

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

максимізувати c^Tx

при обмеженнях Ax ⩽ b.

Алгоритм визначає черговий допустимий напрямок у бік оптимального розв'язку і відступає на множник 0 < γ ⩽ 1.

Алгоритм Кармаркара дуже складний. Зацікавлені читачі можуть знайти інформацію за посиланнями[2][3][4][5][6]. Спрощену версія, що має назву «Метод афінного масштабування», аналізовану в інших статтях[7], можна описати коротко так (зверніть увагу, що метод афінного масштабування, коли використовується для задач малих розмірів, не є алгоритмом поліноміального часу. Для задач великого розміру та складних задач слід дотримуватись початкового підходу):

Вхід: A, b, c, ${\displaystyle x^{0}}$, критерій зупинки, ${\displaystyle \gamma }$ .

${\displaystyle k\leftarrow 0}$
 do while критерій зупинки не виконується
   ${\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}}$
   if ${\displaystyle h_{v}\geqslant 0}$ then
    return необмежений розв'язок
   end if
   ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\mid (h_{v})_{i}<0,\,i=1,\ldots ,m\}}$
   ${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$
   ${\displaystyle k\leftarrow k+1}$
 end do

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

Кармаркар також розширив методологію[8][9][10][11] розв'язування задач і цілими обмеженнями та неопуклих задач[12].

Приклад

Приклад розв'язку

Нехай дано задачу лінійного програмування:

максимізувати ${\displaystyle x_{1}+x_{2}}$

за умов ${\displaystyle 2px_{1}+x_{2}\leqslant p^{2}+1,\ p=0{,}0,\,0{,}1,\,0{,}2,\,\ldots ,0{,}9,\,1{,}0.}$

Тобто, є дві змінні ${\displaystyle x_{1},x_{2}}$ та 11 обмежень, що відповідають різним значенням ${\displaystyle p}$. Малюнок показує кожну ітерацію алгоритму як червону точку. Обмеження зображено синіми прямими.

Дебати про патентування Чи можна патентувати математику?

Коли Наренда Кармаркар запропонував свій алгоритм, він працював у AT&T. Після впровадження алгоритму для оптимізації телефонної мережі AT&T[13] там усвідомили, що він може мати практичну важливість. У квітні 1985 року AT&T швидко подала заявку на патент алгоритму Кармаркара, і ця подія пожвавила дебати навколо патентування програмного забезпечення[14]. Це занепокоїло багатьох математиків, як, наприклад, Рональда Рівеста (він сам є одним із власників патенту на алгоритм RSA), який висловив думку, що дослідження, засновані на базі цього алгоритму, мають бути вільними. Навіть ще до затвердження патенту дехто стверджували, що існував нездійснений прототип[15].

Математики, що спеціалізуються на чисельних методах, такі як Філіп Гілл (Philip Gill) та інші, стверджували, що алгоритм Кармаркара еквівалентний проєктивному бар'єрному методу Ньютона з логарифмічною бар'єрною функцією, якщо правильно вибрати параметри[16]. Однак аргумент Гілла має недолік, оскільки метод, який він описує, навіть не вважають алгоритмом, оскільки вимагає вибору параметрів, які не обумовлені внутрішньою логікою методу і повністю покладаються на зовнішнє керування, особливо щодо алгоритму Кармаркара[17]. Більш того, внесок Кармаркара далекий від очевидного у світлі всіх попередніх робіт, включно з працями Фіако — МакКорміка (Fiacco — McCormick), Гілла (Gill) та інших, перерахованими Зальцманом (Saltzman)[17][18][19]. Патент обговорювано в сенаті США, схвалено як визнання суттєвої оригінальності роботи Кармаркара та у травні 1988 року оформлено як патент США 4744026 «Методи та апаратура для ефективного розподілу ресурсів». AT&T поставила систему KORBX[20][21], що базується на цьому патенті, Пентагону[22][23], який використовував її для розв'язання математичних задач, які до цього вважали нерозв'язними.

Опоненти програмного патентування пізніше заявляли, що патенти зруйнували позитивний цикл взаємодії, притаманний зв'язку дослідників у лінійному програмуванні з виробництвом, і, зокрема, ізолювали самого Кармаркара від математичних досліджень у його галузі[24].

Дія патенту закінчилася у квітні 2006 року, і алгоритм нині є загальним надбанням.

Примітки

1. Gilbert Strang. Karmarkar’s algorithm and its place in applied mathematics // The Mathematical Intelligencer. — New York : Springer, 1987. — Vol. 9, iss. 2 (27 December). — P. 4—10. — ISSN 0343-6993. — DOI:10.1007/BF03025891.
2. A new polynomial-time algorithm for linear programming. Архів оригіналу за 14 лютого 2019. Процитовано 26 серпня 2015.
3. A new polynomial-time algorithm for linear programming — Springer. Архів оригіналу за 6 вересня 2017. Процитовано 29 вересня 2017.
4. Power Series Variants of Karmarkar-Type Algorithms — Karmarkar — 2013 — AT&T Technical Journal — Wiley Online Library. Архів оригіналу за 16 липня 2015. Процитовано 26 серпня 2015.
5. Karmarkar N. K., Lagarias, J. C., Slutsman, L., Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
6. Архивированная копия (PDF). Архів оригіналу (PDF) за 4 березня 2016. Процитовано 26 серпня 2015. [Архівовано 2016-03-04 у Wayback Machine.]
7. Robert J. Vanderbei, Marc Meketon, Barry Freedman. A Modification of Karmarkar's Linear Programming Algorithm // Algorithmica. — 1986. — Т. 1 (27 грудня). — С. 395—407. — DOI:10.1007/BF01840454.
8. Karmarkar, N. K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, p. 160181 (1991).
9. Karmarkar, N. K. Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, p. 125140, Princeton University Press (1992).
10. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).
11. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).
12. Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010.
13. Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., Ramakrishnan K. G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).
14. Gina Kolata. IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes // The New York Times. — 1989. — 12 March.
15. Various posts by Matthew Saltzman, Clemson University. Архів оригіналу за 23 вересня 2015. Процитовано 26 серпня 2015.
16. Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, Margaret H. Wright. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method // Mathematical Programming. — 1986. — Т. 36, вип. 2 (27 грудня). — С. 183—209. — DOI:10.1007/BF02592025.
17. Andrew Chin. On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens // Journal Of Intellectual Property Law. — 2009. — Т. 16 (27 грудня). — С. 214—223.
18. Mark A. Paley (1995). «The Karmarkar Patent: Why Congress Should „Open the Door“ to Algorithms as Patentable Subject Matter». 22 COMPUTER L. REP. 7.
19. Margaret H. Wright. The Interior-Point Revolution in Optimization: History, Recent Developments, and Lasting Consequences // Bulletins of the American Mathematical Society. — 2004. — Т. 42 (27 грудня). — С. 39—56.
20. Marc S. Meketon, Y. C. Cheng, D. J. Houck, J. M. Liu, L. Slutsman, Robert J. Vanderbei, P. Wang. The AT&T KORBX System // AT&T Technical Journal. — 1989. — Т. 68 (27 грудня). — С. 7—19.
21. Big A.T.&T. Computer for Complexities — NYTimes.com. Архів оригіналу за 1 лютого 2018. Процитовано 29 вересня 2017.
22. Military Is First Announced Customer Of AT&T Software. Архів оригіналу за 6 вересня 2015. Процитовано 26 серпня 2015.
23. IEEE Xplore Abstract — Using KORBX for military airlift applications. Архів оригіналу за 13 листопада 2014. Процитовано 26 серпня 2015.
24. 今野浩: カーマーカー特許とソフトウェア – 数学は 特許に なるか (Konno Hiroshi: The Kamarkar Patent and Software – Has Mathematics Become Patentable?). — FFII. Архівовано з джерела 27 червня 2008. Процитовано 2008-06-27. [Архівовано 2008-06-27 у Wayback Machine.]

Література

• 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.