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

редактировать

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

Обозначая количество переменных и количество битов на входе в алгоритм, алгоритм Кармаркара требует операций с цифровыми числами по сравнению с такими операциями для алгоритма эллипсоида. Таким образом, время выполнения алгоритма Кармаркара п {\ displaystyle n} L {\ displaystyle L} О ( п 3.5 L ) {\ Displaystyle О (п ^ {3.5} L)} О ( L ) {\ Displaystyle O (L)} О ( п 6 L ) {\ Displaystyle О (п ^ {6} L)}

О ( п 3.5 L 2 бревно L бревно бревно L ) {\ Displaystyle О (п ^ {3.5} L ^ {2} \ CDOT \ журнал L \ CDOT \ журнал \ журнал L)}

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

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

СОДЕРЖАНИЕ

  • 1 Алгоритм
  • 2 Пример
  • 3 Патентный спор: можно ли запатентовать математику?
  • 4 ссылки

Алгоритм

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

максимизировать c Tx
при условии Ax ≤ b.

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

Algorithm Affine-Scaling

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

Input: A, b, c,      x  0 {\displaystyle x^{0}}, stopping criterion, γ.
    k  0 {\displaystyle k\leftarrow 0} do while stopping criterion not satisfied      v  k  b  A  x  k {\displaystyle v^{k}\leftarrow b-Ax^{k}}      D  v  diag  (  v  1  k ,  ,  v  m  k ) {\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots,v_{m}^{k})}      h  x  (  A  T  D  v   2 A  )   1 c {\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}      h  v   A  h  x {\displaystyle h_{v}\leftarrow -Ah_{x}} if      h  v  0 {\displaystyle h_{v}\geq 0} then return unbounded end if     α  γ  min {   v  i  k  / (  h  v  )  i    |   (  h  v  )  i lt; 0 ,  i = 1 ,  , m } {\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}lt;0,\,i=1,\ldots,m\}}      x  k + 1   x  k + α  h  x {\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}     k  k + 1 {\displaystyle k\leftarrow k+1} end do
  • «←» обозначает присвоение. Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента.
  • « return » завершает алгоритм и выводит следующее значение.

Пример

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

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

максимизировать Икс 1 + Икс 2 при условии 2 п Икс 1 + Икс 2 п 2 + 1 , п знак равно 0,0 , 0,1 , 0,2 , , 0,9 , 1.0. {\ displaystyle {\ begin {array} {lrclr} {\ text {maximize}} amp; x_ {1} + x_ {2} \\ {\ text {subject to}} amp; 2px_ {1} + x_ {2} amp; \ leq amp; p ^ {2} + 1, amp; p = 0.0,0.1,0.2, \ ldots, 0.9,1.0. \ end {array}}}

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

Патентный спор: можно ли запатентовать математику?

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

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

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

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

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

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

использованная литература

Последняя правка сделана 2023-04-16 11:17:16
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте