카르마카르의 알고리즘

카르마카르의 알고리즘은 나렌드라 카르마카르가 1984년 선형 프로그래밍 문제 해결을 위해 도입한 알고리즘입니다. 이러한 문제를 다항식 시간에 해결하는 최초의 합리적 효율적인 알고리즘이었습니다. 타원체 방법도 다항식 시간이지만 실제로는 비효율적인 것으로 판명되었습니다.

변수 수를$$ $n{\displaystyle }$ ${\displaystyle n},$ 비등식 제약 수를 m, 알고리즘에 대한 입력 비트$$ $수$를 L$${\$displaystyle$ L$}$로 표시하면 Karmarkar의 알고리즘은 $O{\displaystyle (L)}$ ${\displaystyle O(m$$^{1.5}n^{2}L)}$개의$$$$ 작업이 필요합니다. $타원체{\displaystyle }$ 알고리즘에 대한 O${\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}n}$+ ${\displaystyle m}$) L${\displaystyle }$) ${\displaystyle O(n^{3}(n$+ $m)$ L$)}$와 비교하여.^[1] "사각" 문제에서 m이 O(n)일 때 카르마카르의 알고리즘은 $O{\displaystyle (n^{}}$ 3${\displaystyle {\mathrm{.}}^{}}$ L$){\displaystyle$ O$(n^{3.$5)를 요구합니다.타원체 알고리즘에 대한${\displaystyle }$O(${\displaystyle {}^{}}$ 4${\displaystyle }$L)$${\$displaystyle$O($n^{4}L)}$와 $비교$하여${\displaystyle }$O(${\displaystyle L)}${\$displaystyle$O($L)}$자리$$ 숫자에 $대한{\displaystyle }$$}L)}$ 연산$$. 따라서 카르마카 알고리즘의 실행 시간은

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

FFT 기반 곱셈을 사용합니다(Big O 표기법 참조).

Karmarkar의 알고리즘은 내부점 방법의 클래스에 속합니다: 해에 대한 현재 추측은 단순 방법처럼 실현 가능한 집합의 경계를 따르지 않고 실현 가능한 영역의 내부를 통해 이동합니다. 반복할 때마다 정분수에 의해 최적해의 근사치를 개선하고 합리적인 데이터를 가진 최적해로 수렴합니다.^[2]

알고리즘이.

행렬 형태의 선형 프로그래밍 문제를 생각해 보십시오.

Karmarkar의 알고리즘은 최적성을 향한 다음 실현 가능한 방향을 결정하고 0 < γ ≤ 1로 축소합니다. 여러 출처에 설명되어 있습니다.^{[3][4][5][6][7][8]} Karmarkar는 또한 정수 제약과 비볼록 문제를 해결하기 위해 방법을^{[9][10][11][12]} 확장했습니다.^[13]

알고리즘 아핀-스케일링 

입력: A, b, c, $x$ ${\displaystyle 0^{}}$ ${\displaystyle$ x$^{0$ 중지 기준, γ. 

${\displaystyle k}$ ← ${\displaystyle 0}$$displaystyle$ k$\leftarrow$ 0$}$이(가) 중지하는 동안 기준이 충족되지 않음 ${\displaystyle v}$ k ← b - Ax k {\displaystyle v^{k}\leftarrow b-Ax^{k}}${\displaystyle }$Dv ← d${\displaystyle i}$ag ⁡(v$$1k, …, vm 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}\geq 0}$ then return unbounded     end if ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\, \,\,(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 

예

선형 프로그램을 고려합니다.

${\displaystyle {\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}}}$

즉, $변수{\displaystyle }$ ${\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 2 ${\$ 및$$ p ${\displaystyle p}$의 다양한 값과 관련된 11개의 제약 조건이 있습니다$.$ 이 그림은 알고리즘의 각 반복을 빨간색 원 포인트로 보여줍니다. 제약 조건은 파란색 선으로 표시됩니다.

특허논란

그가 알고리즘을 발명했을 때, Carmarkar는 IBM에 의해 캘리포니아에 있는 IBM 산호세 연구소의 박사후 연구원으로 고용되었습니다. 1983년 8월 11일, 그는 스탠포드 대학교에서 알고리즘에 대해 설명하는 세미나를 열었고, 그의 소속은 여전히 IBM으로 등록되어 있습니다. 1983년 가을, Carmarkar는 AT&T에서 일하기 시작했고 1984년 ACM 컴퓨팅 이론 심포지엄(STOC, 1984년 4월 30일 - 5월 2일 개최)에 AT&T Bell Laboratories를 소속사로 명시한 논문을 제출했습니다.^[16] AT&T의 전화망을 최적화하는 데 알고리즘을 적용한 후,^[17] 그들은 그의 발명이 실용적으로 중요할 수 있다는 것을 깨달았습니다. 1985년 4월, AT&T는 즉시 그의 알고리즘에 대한 특허를 신청했습니다.

이 특허는 소프트웨어 특허 문제로 계속되는 논란에 더욱 기름을 부었습니다.^[18] 이로 인해 Ronald Rivest(그 자신이 RSA 알고리즘에 관한 특허 보유자 중 한 명)와 같이 많은 수학자들이 불안에 빠졌습니다. 그는 알고리즘이 자유로워야 한다는 근거로 연구가 진행되었다는 의견을 나타냈습니다. 실제로 특허가 부여되기 전부터 적용 가능한 선행기술이 있었을 수 있다는 주장이 제기됐습니다.^[19] 필립 길 등 수치해석을 전문으로 하는 수학자들은 변수를 적절히 선택하면 카르마카르의 알고리즘이 로그 장벽 함수를 갖는 투영된 뉴턴 장벽 방법과 동일하다고 주장했습니다.^[20] 법학자 Andrew Chin은 그들이 설명하는 방법이 "알고리즘"을 구성하지 않는 한 길의 주장은 결함이 있다고 생각합니다. 왜냐하면 방법의 내부 논리에서 따르지 않고 본질적으로 카르마카의 알고리즘에서 외부 지침에 의존하는 매개변수의 선택이 필요하기 때문입니다.^[21] 게다가, Karmarkar의 공헌은 Piaco-McCormick, Gill 및 Saltzman이 인용한 다른 모든 이전 연구에 비추어 명백한 것과는 거리가 먼 것으로 여겨집니다.^[21][22][23] 이 특허는 1988년 5월 미국 특허 4,744,028: "효율적인 자원 할당을 위한 방법 및 장치"로서 카르마카의 연구의 본질적인 독창성을 인정받아 미국 상원에서^{[citation needed]} 논의되고 승인되었습니다.

AT&T는 하드웨어와 소프트웨어의 조합을 KORBX라고 부르는 Karmarkar의 알고리즘을 실행하기 위해 특별히 벡터 멀티프로세서 컴퓨터 시스템을 설계했고,^[24] 이 시스템을 890만 달러의 가격으로 판매했습니다.^[25][26] 그 첫 번째 고객은 국방부였습니다.^[27][28]

소프트웨어 특허에 반대하는 사람들은 또한 이 특허가 이전에 선형 프로그래밍과 산업 연구자들 사이의 관계를 특징짓는 긍정적인 상호 작용 주기를 망쳤다고 주장했으며 특히 카르마카르 자신을 그의 분야의 수학 연구자 네트워크로부터 고립시켰습니다.^[29]

특허 자체는 2006년 4월에 만료되었고 알고리즘은 현재 공개 영역에 있습니다.

미국 대법원은 Gottschalk v. Benson에서 수학은 특허를 받을 수 없다고 판결했습니다.^[30] 그 경우 법원은 먼저 컴퓨터 알고리즘이 특허를 받을 수 있는지 여부를 다루었고 특허 시스템이 아이디어와 유사한 추상성을 보호하지 못하기 때문에 특허를 받을 수 없다고 판결했습니다. Diamond v. Diehr에서 ^[31]대법원은 "이와 같은 수학적 공식은 우리 특허법의 보호를 부여받지 않으며, 공식의 사용을 특정 기술 환경으로 제한하려고 시도함으로써 이 원칙을 피할 수 없습니다.^[32] Mayo Collaborative Services 대 Prometeus Labs,^[33] Inc.에서 대법원은 "단순히 물리적 기계, 즉 컴퓨터에 수학적 원리를 구현하는 것은 그 원리의 특허 가능한 적용이 아닙니다"^[34]라고 설명했습니다.

적용들

걸프전 당시 미군은 카르마카르의 알고리즘을 로지스틱스 계획에 사용했습니다.^[1]

참고문헌

• Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio G.C.; Veiga, Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming. 44 (1–3): 297–335. doi:10.1007/bf01587095. S2CID 12851754.
• Narendra Karmarkar (1984). "선형 프로그래밍을 위한 새로운 다항 시간 알고리즘", Combinatorica, Vol 4, nr. 4, p. 373–395.