カーマーカーのアルゴリズム（）とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法（英: Karmarkar's method）とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。
カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。楕円体法も多項式時間アルゴリズムであるが、実用上の効率は良くない。
カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解を実行可能領域の境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解（optimal solution）に収束する。
アルゴリズム 行列 、ベクトル に対し、以下のな線形計画問題を考える。 maximize cTx subject to Ax ≤ b. すなわち、 条件 Ax ≤ b の下で、 cTx を最大にするベクトル x を求める。
このアルゴリズムはその時点での最適化実行可能方向 (feasible direction toward optimality) を求め、0 < γ ≤ 1 の範囲で縮小する。
カーマーカーのアルゴリズムは複雑である。アフィンスケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている。このアルゴリズムは以下のように簡潔に示される。ただし、アフィンスケーリング法は実用上効率が良いが、多項式時間アルゴリズムは保証されていない。
Input: A, b, c, , stopping criterion停止条件。アルゴリズムのとおり、while文は停止条件を満たすとループを抜ける。, .
do while stopping criterion not satisfied
行列の対角成分を代入。
if then条件を満たす場合は、戻り値"unbounded"を返す。 return unbounded end if
end do
例題
以下の線形計画問題を考える。 maximize subject to
上記には、2つの変数 と、11の束縛変数 がある。本節の例解図には、アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。
計算量 を変数の個数、 をアルゴリズムの入力ビット数としたとき、カーマーカーのアルゴリズムは、桁数のオーダー に対し、操作数 (operations) のオーダー をもつ。比較として、楕円体法の操作数は のオーダーをもつ。カーマーカーのアルゴリズムの実行時間（runtime、計算量）は、高速フーリエ変換に基づく乗算であるシェーンハーゲ・シュトラッセンのアルゴリズムで使用した場合、以下のオーダーをもつ。
（記号"O"についてはランダウの記号を参照のこと。）
特許論争 カーマーカーはAT&Tに採用されたのち、彼がこのアルゴリズムを発見してからは、彼と雇用者のAT&Tはこの発明が実用上重要なものとなる、ということを信じて疑わなかった。1985年4月になると、AT&Tは、カーマーカーのアルゴリズムを特許として出願し、ソフトウェア特許問題についての従来からの論争に対し火に油を注いだ。ロナルド・リベストをはじめとする多くの数学者がこの事態の進展を不安視し（しかし、皮肉なことにロナルドはRSA暗号アルゴリズムの特許権保持者の一人である）、アルゴリズムはフリーであるべきとの考えに沿って研究を進めるとの意見を彼らの多くが述べていた。実際に特許が既に許可されたとしても、適用可能なが存在するとも考えられていた。フィリップ・ギル (Philip Gill) などをはじめとする数値解析を専攻する数学者たちは、適切な媒介変数を選択することで、カーマーカーのアルゴリズムが対数障壁関数の射影ニュートン障壁法 (projected Newton barrier method) と同値であることを証明した。ギルが提示した手法は1960年代から非線形計画法に広く利用されている。また事実として、1968年に初版が出版されたある著名な書籍には、線形計画問題の解法としてこの手法が明示されていた 1990年、SIAMにより再版されている（）。。しかし、数名が次のように述べている。彼らが主張する手法が「アルゴリズム」としてさえも見なされない限り、ギルの証明に誤りがある。なぜなら、その手法は内部的なアルゴリズムからは導けない媒介変数を選択する必要があることを示しているが、それは外部の補助に依存、すなわち実質的にはカーマーカーのアルゴリズムから導かれるものだからである。そのうえ、ザルツマン (Saltzman) が引用している、フィアッコ＝マコーミック (Fiacco-McCormick)、ギル、その他の人物による全ての先行作業を考慮してみると、カーマーカーが与えた貢献は明快なものとは程遠いと考えられるMark A. Paley (1995). "The Karmarkar Patent: Why Congress Should “Open the Door” to Algorithms as Patentable Subject Matter". 22 COMPUTER L. REP. 7。この発明は1988年5月、"Methods and apparatus for efficient resource allocation"（最適資源割当のための方法および装置）として結局許可された。このアルゴリズムは射影変換とアフィン変換の組合せによる線形計画問題の解法であり、米国の特許では双方のアルゴリズムそれぞれに特許が与えられている。日本では後者だけが出願公告（当時）され、その後特許が認められた。 特許第2033073号「最適資源割当方法」 特願昭61-501865 特公昭62-502580 特公平5-61672 しかし、AT&Tにとってこの特許の商用的価値は限られたものになった。彼らはKORBXマシュー・ザルツマン（Matthew Saltzman）はこの文字列には何の意味もないと述べている。一方、今野浩は『カーマーカー特許とソフトウェア』（）上で、これは"Karmarkar OR box"を略して名付けたのではないかと述べている。ORはオペレーションズ・リサーチの略。というシステムを製造した。このシステムは、アライアント製のプロセッサ8つを搭載し、カーマーカーのアルゴリズムを使用するソフトウェアを組み合わせて線形計画問題を解くという専用システムであり、1台890万ドルもの値段が付けられていた。しかし、売れたのは2台だけだった『カーマーカー特許とソフトウェア』（）によると購入したのはデルタ航空とペンタゴンだった。。日本においては、1997年（平成9年）今野浩らにより本特許の無効審判請求がなされた（事件番号:平成9年審判第2452号事件）が、特許庁審判官は、「本件発明が、ハードウェア資源を用いて最適割当てのための演算処理を当該アルゴリズムを利用し結果を得るものであると認める。本件発明はアルゴリズムそのものではなく、また計算機を単に利用しただけのものでもない。」とし、原告の請求を認めない旨の審決を下した。
本審決後、原告は審決等取消訴訟を求め東京高等裁判所に出訴した（事件番号:平成11年（行ケ）第25号 審決取消請求事件）。この訴えに対する判決において、被告のルーセント・テクノロジー（カーマーカーが所属したAT&Tテクノロジーの承継企業）が2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録を行っていたことが明らかになった。以下判決文より引用すると、
このように、特許権の放棄により原告の訴えの利益が消滅したとして、本件を却下した。結果として該当特許自身が「発明」の要件を満たしていたか（特許適格性）は判示されていない。
米国では、特許保護期間が2006年4月に満了し、本特許は現在では完全にパブリックドメイン下におかれている。
ソフトウェア特許に反対する者は、線形計画法の研究者と産業界とのつながりを以前から特徴付けている、両者の相互交流の正のサイクルを特許が駄目にしてしまうと強く主張している。そして、特許のせいで、他ならぬカーマーカー自身が線形計画法を共に研究する数学者の輪から孤立してしまった、と主張している。
脚注
注釈
出典
参考文献 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.
関連項目 線形計画法 シンプレックス法 内点法 ナレンドラ・カーマーカー ソフトウェア特許 今野浩
外部リンク ORWikiより 内点法 カーマーカー法 CiNiiより、カーマーカーのアルゴリズムを利用した論文 コード生成法を用いたアフィンカーマーカー法のインプリメンテーション(LP新解法) 対称な双対問題のペア上でのカーマーカー法(<特集>線形計画法の最近の発展) スパース処理技法を用いたカーマーカー法による大規模線形計画問題の解法 (最適化<特集>) カーマーカー特許 アルゴリズムと特許 : その1. カーマーカー特許 ビジネスモデル特許の事例 (4)カーマーカ特許 その他の「アルゴリズム特許」 "Computer and method for the discrete bracewell transform" 特許として認められなかったアルゴリズムの例。別人による全く別種の発明であり、本特許係争終結後に出願された。しかし、カーマーカー特許とは異なり、解法の説明に終始しているとの判決が下されている。 東京高裁平成16年（行ケ）第188号 審決取消請求事件