カーマーカーのアルゴリズムのソースを表示

'''カーマーカーのアルゴリズム'''（{{lang-en-short|Karmarkar's algorithm}}）とは[[1984年]]、[[ナレンドラ・カーマーカー]]により発見された[[線形計画問題]]の解法である。この[[アルゴリズム]]は、しばしば、'''カーマーカー法'''（[[英語|英]]: Karmarkar's method）とも呼ばれる。また、このアルゴリズムを[[発明]]とする[[特許]]が[[アメリカ合衆国|米国]]や[[日本]]で出願され、請求特許は時折'''カーマーカー特許''' (Karmarkar's patent) とも呼称される。

カーマーカーのアルゴリズムは、線形計画問題に対する初の[[多項式時間]]アルゴリズムである。{{仮リンク|楕円体法|en|ellipsoid method}}も多項式時間アルゴリズムであるが、実用上の効率は良くない。

カーマーカーのアルゴリズムは[[内点法]]の一種である。内点法は、候補解を[[実行可能領域]]の[[境界 (位相空間論)|境界]]に沿って更新する[[シンプレックス法|単体法]]とは異なり、実行可能領域の[[内部 (位相空間論)|内部]]を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで[[最適化問題|最適解]]（[[:en:Optimization problem|optimal solution]]）に[[収束]]する。<ref name="Strang">
{{cite journal
| author = {{仮リンク|ギルバート・ストラング|label=Gilbert Strang|en|Gilbert Strang}}
| title = Karmarkar’s algorithm and its place in applied mathematics
| journal = {{仮リンク|The Mathematical Intelligencer|en|The Mathematical Intelligencer}}
| date = 1987-06-01
| publisher = [[シュプリンガー・サイエンス・アンド・ビジネス・メディア|Springer]]
| location = [[ニューヨーク|New York]]
| issn = 0343-6993
| pages = 4–10
| volume = 9
| number = 2
| doi = 10.1007/BF03025891
| mr = '''883185'''
| ref = harv
}}</ref>

== アルゴリズム ==
[[行列]] <math>A</math>、[[ベクトル空間|ベクトル]] <math>b</math> に対し、以下の{{仮リンク|正準形式|en|Canonical form}}な[[線形計画問題]]を考える。
: maximize ''c''<sup>''T''</sup>''x''
: subject to ''Ax'' ≤ ''b''.
すなわち、
: 条件 ''Ax'' ≤ ''b'' の下で、
: ''c''<sup>''T''</sup>''x'' を最大にするベクトル ''x'' を求める。

このアルゴリズムはその時点での最適化実行可能方向 (feasible direction toward optimality) を求め、0 < γ ≤ 1 の範囲で縮小する。

カーマーカーのアルゴリズムは複雑である。[[アフィン空間|アフィン]]・スケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている<ref>
{{cite journal
| doi = 10.1007/BF01840454
| author = {{仮リンク|ロバート・J・ヴァンダーベイ|label=Robert J. Vanderbei|en|Robert J. Vanderbei}}
| coauthors = Meketon, Marc, Freedman, Barry
| year = 1986
| title =  A Modification of Karmarkar's Linear Programming Algorithm
| journal = Algorithmica
| volume = 1
| pages = 395–407
}}</ref>。このアルゴリズムは以下のように簡潔に示される。ただし、アフィン・スケーリング・アルゴリズムは実用上効率が良いが、多項式時間アルゴリズムではない。

{{algorithm-begin|name=Affine-Scaling}}
   Input:  A, b, c, <math>x^0</math>, ''stopping criterion''<ref group="注釈">[[停止条件 （数学）|停止条件]]。アルゴリズムのとおり、while文は停止条件を満たすとループを抜ける。</ref>, <math>\gamma</math>.

   <math> k \leftarrow 0 </math>
   '''do while''' ''stopping criterion'' '''not satisfied'''
      <math>v^k \leftarrow b-Ax^k</math>
      <math>D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)</math><ref group="注釈">行列の[[主対角線|対角成分]]を代入。</ref>
      <math>h_x\leftarrow (A^TD_v^{-2}A)^{-1}c</math>
      <math>h_v\leftarrow -Ah_x</math>
      '''if''' <math>h_v \ge 0</math> '''then'''<ref group="注釈">条件を満たす場合は、戻り値"unbounded"を返す。</ref>
         '''return''' unbounded
      '''end if'''
      <math>\alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}</math>
      <math>x^{k+1}\leftarrow x^k + \alpha h_x</math>
      <math>k\leftarrow k+1</math>
   '''end do'''
{{algorithm-end}}
== 例題 ==
<!--[[File:karmarkar.png|thumb|200px|right|例解]]-->
以下の線形計画問題を考える。
: maximize <math>x_1 + x_2</math>
: subject to <math>2p x_1 + x_2 \leq p^2+1, \quad p=0.0, 0.1, 0.2, \ldots, 0.9, 1.0.</math>

上記には、2つの変数 <math>x_1, x_2</math> と、11の[[束縛変数]] <math>p</math> がある。[[:en:File:Karmarkar.png|英語版ウィキペディア]]には2変数を[[グラフ (関数)|グラフ]]化したものがある。アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。

== 計算量 ==
<math>n</math> を[[変数 (数学)|変数]]の個数、<math>L</math> をアルゴリズムの入力[[ビット]]数としたとき、カーマーカーのアルゴリズムは、桁数の[[オーダー (物理学)|オーダー]] <math>O(L)</math> に対し、操作数 (operations) のオーダー <math>O(n^{3.5} L)</math> をもつ。比較として、楕円体法の操作数は <math>O(n^6 L)</math> のオーダーをもつ。よって、カーマーカーのアルゴリズムの実行時間（runtime、[[計算量]]）は、[[高速フーリエ変換]]に基づく[[乗法|乗算]]である{{仮リンク|シェーンハーゲ・シュトラッセンのアルゴリズム|en|Schönhage–Strassen algorithm}}を使用した場合、以下のオーダーをもつ。
:<math>O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)</math>
（記号"O"については[[ランダウの記号]]を参照のこと。）

== 特許論争 ==
カーマーカーは[[AT&T]]に採用されたのち、彼がこのアルゴリズムを発見してからは、彼と雇用者のAT&Tはこの発明が実用上重要なものとなる、ということを信じて疑わなかった。[[1985年]]4月になると、AT&Tは、カーマーカーのアルゴリズムを[[特許]]として出願し、[[ソフトウェア特許]]問題についての従来からの論争に対し火に油を注いだ<ref name="kolata">
{{cite news
| first = Gina
| last = Kolata
| title = IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes
| url = http://www.nytimes.com/1989/03/12/weekinreview/ideas-trends-mathematicians-are-troubled-by-claims-on-their-recipes.html
| work = [[ニューヨーク・タイムズ|The New York Times]]
| date = 1989-03-12
}}</ref>。[[ロナルド・リベスト]]をはじめとする多くの数学者がこの事態の進展を不安視し（しかし、皮肉なことにロナルドは[[RSA暗号]]アルゴリズムの特許権保持者の一人である）、アルゴリズムは[[自由|フリー]]であるべきとの考えに沿って研究を進めるとの意見を彼らの多くが述べていた。実際に特許が既に認可されたとしても、適用可能な{{仮リンク|先行技術|en|prior art}}が存在するとも考えられていた<ref name="saltzman">
{{cite web
| url = http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850c-s96/www/interiorpoint.txt
| title = Various posts by Matthew Saltzman
| publisher = [[クレムゾン大学|Clemson University]]
| accessdate = 2011-05-24
}}</ref>。[[フィリップ・ギル]] (Philip Gill) などをはじめとする[[数値解析]]を専攻する数学者たちは、適切な媒介変数を選択することで、カーマーカーのアルゴリズムが[[対数]]{{仮リンク|障壁関数|en|barrier function<!-- [[:ja:バリア関数]] とリンク -->|FIXME=1}}の[[射影ニュートン障壁法]] (projected Newton barrier method) と[[同値]]であることを証明した<ref>
{{cite journal
| last = Gill
| first = Philip E.
| coauthors = Murray, Walter, Saunders, Michael A., Tomlin, J. A. and Wright, Margaret H.
| year = 1986
| title =  On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
| journal = Mathematical Programming
| volume = 36
| issue = 2
| pages = 183–209
| url = http://www.springerlink.com/content/2781h35w87600923/
| doi = 10.1007/BF02592025
}}</ref>。ギルが提示した手法は[[1960年代]]から[[非線形計画法]]に広く利用されている。また事実として、[[1968年]]に初版が出版されたある著名な書籍には、線形計画問題の解法としてこの手法が明示されていた<ref>
{{cite book
| author = [[アンソニー・V・フィアッコ|Anthony V. Fiacco]]
| coauthors = [[ガース・P・マコーミック|Garth P. McCormick]]
| year = 1968
| title = Nonlinear Programming: Sequential Unconstrained Minimization Techniques.
| publisher = Wiley
| location = New York
| isbn = 978-0-471-25810-0
}} [[1990年]]、{{仮リンク|Society for Industrial and Applied Mathematics|label=SIAM|en|Society for Industrial and Applied Mathematics}}により再版されている（ISBN 978-0-89871-254-4）。
</ref>。しかし、数名が次のように述べている。彼らが主張する手法が「アルゴリズム」としてさえも見なされない限り、ギルの証明に誤りがある。なぜなら、その手法は内部的なアルゴリズムからは導けない媒介変数を選択する必要があることを示しているが、それは外部の補助に依存、すなわち実質的にはカーマーカーのアルゴリズムから導かれるものだからである<ref name="chin">
{{cite journal
| author = Andrew Chin
| year = 2009
| title = On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens
| journal = Journal Of Intellectual Property Law
| volume = 16
| pages = 214 - 223
| url = http://andrewchin.com/chin/scholarship/abstraction-equivalence.pdf
}}</ref>。そのうえ、ザルツマン (Saltzman) が引用している、フィアッコ＝マコーミック (Fiacco-McCormick)、ギル、その他の人物による全ての先行作業を考慮してみると、カーマーカーが与えた貢献は明快なものとは程遠いと考えられる<ref name="chin"/><ref name="paley">
Mark A. Paley (1995). "The Karmarkar Patent: Why Congress Should “Open the Door” to Algorithms as Patentable Subject Matter". 22 COMPUTER L. REP. 7
</ref><ref name="wright">
{{cite journal
| author = Margaret H. Wright
| year = 2004
| title = The Interior-Point Revolution in Optimization: History, Recent Developments, and Lasting Consequences
| journal = Bulletins of the American Mathematical Society
| volume = 42
| pages = 39 - 56
| url = http://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01040-7/S0273-0979-04-01040-7.pdf
}}</ref>。この発明は[[1988年]]5月、{{US patent|4744026}}"Methods and apparatus for efficient resource allocation"（最適資源割当のための方法および装置）として結局認可された。このアルゴリズムは[[射影空間|射影変換]]と[[アフィン変換]]の組合せによる[[線形計画問題]]の解法であり<ref>
{{cite web
| url = http://www.orsj.or.jp/~wiki/wiki/index.php/カーマーカー特許
| title = カーマーカー特許
| date = 2007-07-19
| publisher = [[ORWiki]]
| accessdate = 2011-05-25
}}</ref>、米国の特許では双方のアルゴリズムそれぞれに特許が与えられている。日本では後者だけに特許が出願公告（当時）され、その後特許が認められた。
* 特許第2033073号「最適資源割当方法」
* 特願昭61-501865
* 特公昭62-502580
* 特公平5-61672
しかし、AT&Tにとってこの特許の商用的価値は限られたものになった。彼らは[[KORBX]]<ref group="注釈">
マシュー・ザルツマン（Matthew Saltzman）はこの文字列には何の意味もないと述べている。一方、[[今野浩]]は『カーマーカー特許とソフトウェア』（ISBN 978-4121012784）上で、これは"'''K'''armarkar '''OR''' '''b'''o'''x'''"を略して名付けたのではないかと述べている。ORは[[オペレーションズ・リサーチ]]の略。
</ref>というシステムを製造した<ref>
{{cite journal
| author = Marc S. Meketon
| coauthors = Y.C. Cheng, D.J. Houck, J.M.Liu, L. Slutsman, {{仮リンク|ロバート・J・ヴァンダーベイ|label=Robert J. Vanderbei|en|Robert J. Vanderbei}}, and P. Wang
| year = 1989
| title =  The AT&T KORBX System
| journal = AT&T Technical Journal
| volume = 68
| pages = 7–19
}}</ref>。このシステムは、[[アライアント・コンピュータ|アライアント]]製のプロセッサ8つを搭載し、カーマーカーのアルゴリズムを使用するソフトウェアを組み合わせて線形計画問題を解くという専用システムであり、1台890万[[アメリカ合衆国ドル|ドル]]もの値段が付けられていた。しかし、売れたのは2台だけだった<ref name="saltzman" /><ref group="注釈">
『カーマーカー特許とソフトウェア』（ISBN 978-4121012784）によると購入したのは[[デルタ航空]]と[[アメリカ国防総省|ペンタゴン]]だった。
</ref>。日本においては、[[1997年]]（平成9年）[[今野浩]]らにより本特許の[[無効審判]]請求がなされた（事件番号:平成9年審判第2452号事件）が、[[特許庁]][[審判官 (特許庁)|審判官]]は、「本件発明が、[[計算資源|ハードウェア資源]]を用いて最適割当てのための演算処理を当該[[アルゴリズム]]を利用し結果を得るものであると認める。本件発明はアルゴリズムそのものではなく、また計算機を単に利用しただけのものでもない。」とし、原告の訴えを無効とする[[審決]]を下した<ref>
{{cite web
| url = http://t4tomita.lolipop.jp/ip/kmk.html
| title = カーマーカー法特許無効審判審決
| publisher = t4tomita.lolipop.jp
| accessdate = 2011-05-25
}}</ref>。

{{Main2|日本の特許異議申立、無効審判等については「[[日本の特許制度]]」を}}

本審決後、原告は[[審決等取消訴訟|審決取消]]を求め[[東京高等裁判所]]に[[訴訟|出訴]]した（[[事件記録符号|事件番号]]:平成11年（行ケ）第25号 審決取消請求事件）。この訴えに対する[[判決]]<ref>
{{cite web
| url = http://www.courts.go.jp/hanrei/pdf/3896EB5F29F64F0849256BE200353BC2.pdf
| title = 平成11年（行ケ）第25号 審決取消請求事件 平成14年2月26日口頭弁論終結 判決
| format = [[Portable Document Format|PDF]]
| publisher = [[最高裁判所 (日本)|最高裁判所]]
| accessdate = 2011-05-25
}}</ref>において、被告の[[ルーセント・テクノロジー]]（カーマーカーが所属したAT&Tテクノロジーの承継企業）が[[2000年]]12月11日付けで[[特許庁]]に当該特許の放棄による特許権抹消の登録を行っていたことが明らかになった。以下判決文より引用すると、
{{quote|弁論の全趣旨によれば、被告は、本件特許権をその請求項1ないし6のすべてについて放棄し、平成12年12月11日付けで、特許庁に対し、放棄による特許権抹消の登録を申請し、その後間もなく、これに基づき本件特許権の登録は抹消されたことが認められる。被告は、本件特許権が放棄されたことにより，本件訴訟における原告らの訴えの利益は消滅した、と主張する。}}
これによって原告の訴えは利益が消滅したので、本件は[[却下]]されている。結果として該当特許自身が「発明」の要件を満たしていたかの結論は出ていない。

米国では、特許保護期間が[[2006年]]4月に満了し、本特許は現在では完全に[[パブリックドメイン]]下におかれている。

ソフトウェア特許に反対する者は、線形計画法の研究者と産業界とのつながりを以前から特徴付けている、両者の相互交流の正のサイクルを特許が駄目にしてしまうと強く主張している。そして、特許のせいで、他ならぬカーマーカー自身が線形計画法を共に研究する数学者の輪から孤立してしまった、と主張している<ref>
{{cite web
| url = http://eupat.ffii.org/papers/konno95/
| title = カーマーカー特許とソフトウェア -- 数学は 特許に なるか (The Kamarkar Patent and Software -- Has Mathematics Become Patentable?)
| author = [[今野浩]]（Konno Hiroshi）
| publisher = {{仮リンク|Foundation for a Free Information Infrastructure|label=FFII|en|Foundation for a Free Information Infrastructure}}
| accessdate = 2011-05-25
}}</ref>。

== 脚注 ==
=== 参考文献 ===
* 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.&nbsp;297&ndash;335.
* Narendra Karmarkar (1984). "[http://www.amath.washington.edu/~narc/win08/papers/karmarkar.pdf A New Polynomial Time Algorithm for Linear Programming]", ''[[:en:Combinatorica|Combinatorica]]'', Vol '''4''', nr. 4, p.&nbsp;373&ndash;395.
{{脚注ヘルプ}}
=== 注釈 ===
{{Reflist|group="注釈"}}
=== 出典 ===
{{Reflist|2}}

== 関連項目 ==
* [[線形計画法]]
* [[シンプレックス法]]
* [[内点法]]
* [[ナレンドラ・カーマーカー]]
* [[ソフトウェア特許]]
* [[今野浩]]

== 外部リンク ==
* [[ORWiki]]より
** [http://www.orsj.or.jp/~wiki/wiki/index.php/内点法 内点法]
** [http://www.orsj.or.jp/~wiki/wiki/index.php/カーマーカー法 カーマーカー法]
* [[CiNii]]より、カーマーカーのアルゴリズムを利用した論文
** [http://ci.nii.ac.jp/naid/110003477117 コード生成法を用いたアフィンカーマーカー法のインプリメンテーション(LP新解法)]
** [http://ci.nii.ac.jp/naid/110001187401 対称な双対問題のペア上でのカーマーカー法(<特集>線形計画法の最近の発展)]
** [http://ci.nii.ac.jp/naid/40002524186 スパース処理技法を用いたカーマーカー法による大規模線形計画問題の解法 (最適化<特集>)]
* カーマーカー特許
** [http://ci.nii.ac.jp/naid/110001187851 アルゴリズムと特許 : その1. カーマーカー特許]
** [http://www.furutani.co.jp/office/ronbun/BS/BS4.html ビジネスモデル特許の事例 (4)カーマーカ特許]
* その他の「アルゴリズム特許」
** {{US patent|4646256}} "Computer and method for the discrete bracewell transform"
* 特許として認められなかったアルゴリズムの例。別人による全く別種の発明であり、本特許係争終結後に出願された。しかし、カーマーカー特許とは異なり、解法の説明に終始しているとの判決が下されている。
** [http://www.itohpat.co.jp/ip/japancase/H161221.html 東京高裁平成16年（行ケ）第188号 審決取消請求事件]
<!--{{Optimization algorithms|convex}}-->

{{アルゴリズム}}
{{最適化アルゴリズム}}
{{Applied-math-stub}}
{{computer-stub}}
{{law-stub}}

{{DEFAULTSORT:かまかのあるこりすむ}}
[[Category:数学に関する記事]]
[[Category:最適化アルゴリズム]]
[[Category:オペレーションズリサーチ]]
[[Category:日本の特許法]]
[[Category:裁判例]]
[[Category:アメリカ合衆国の特許法]]
[[Category:エポニム]]