カーマーカーのアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

カーマーカーのアルゴリズム: Karmarkar's algorithm)とは1984年ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法Karmarkar's method)とも呼ばれる。また、本アルゴリズムを発明とする特許米国日本で出願されたため、請求特許は時折カーマーカー特許Karmarkar's patent)とも呼称される。

本アルゴリズムは線形計画問題における、適度に効率が良い多項式時間アルゴリズムとしては初のものである。楕円体法英語版も多項式時間アルゴリズムであるが、実際の効率は良くない。

n変数Lをアルゴリズムの入力ビット数とした場合、カーマーカーのアルゴリズムは、桁数のオーダーO(L)に対し、O(n^{3.5} L)の操作数(operations)のオーダーを持つ。比較対照として、楕円体法の操作数はO(n^6 L)のオーダーを持つ。よってカーマーカーのアルゴリズムの実行時間(runtime、計算量)は、高速フーリエ変換ベースの乗算であるシェーンハーゲ・シュトラッセンのアルゴリズム英語版を使用した場合、以下のオーダーを持つ。

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

(記号"O"についてはランダウの記号を参照せよ)

カーマーカーのアルゴリズムは内点法の一種である。内点法は単体法とは異なり、想定解が実行可能集合[注釈 1]境界には存在せず、実行可能集合の内部を通り最適解optimal solution)に漸近する。それだけではなく、このアルゴリズムは、以前のアルゴリズムに比べ、有限小数を繰り返し利用することによる最適解への漸近処理を改善しており、かつ、有意なデータでもって最適解へ収束させる[1]

アルゴリズム[編集]

行列Aベクトルbに対し、以下の正準形式英語版線形計画問題を考える。

maximize cTx
subject to Ax ≤ b.

すなわち、

条件Ax ≤ b.を満たすとき、
cTxを最大化するベクトルxを求める。

このアルゴリズムはその時点での最適化実行可能方向feasible direction toward optimality)を決定し、因子γは0 < γ ≤ 1の範囲でスケールバックする。

カーマーカーのアルゴリズムはより複雑である。アフィン・スケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている[2]。このアルゴリズムは以下のように簡潔に示される。ただし、アフィン・スケーリング・アルゴリズムは実用上効率が良いが、多項式時間アルゴリズムではない。

Algorithm Affine-Scaling
  Input:  A, b, c, x^0, stopping criterion[注釈 2], \gamma.
   k \leftarrow 0 
  do while stopping criterion not satisfied
     v^k \leftarrow b-Ax^k
     D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)[注釈 3]
     h_x\leftarrow (A^TD_v^{-2}A)^{-1}c
     h_v\leftarrow -Ah_x
     if h_v \ge 0 then[注釈 4]
        return unbounded
     end if
     \alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}
     x^{k+1}\leftarrow x^k + \alpha h_x
     k\leftarrow k+1
  end do
  • "←"は「代入」を示す記号である。例えば、"αβ"はαβを代入することを示す。
  • "return"はアルゴリズムを停止させ、戻り値を出力する。


例題[編集]

以下の線形計画問題を考える。

maximize x_1 + x_2
subject to 2p x_1 + x_2 \leq p^2+1, p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0.

上記には、2つの変数x_1, x_2と、11の束縛変数pが存在する。英語版ウィキペディアには2変数をグラフ化したものがある。アルゴリズムを繰り返し実行する毎に赤い円が点描されることと、青い直線は束縛境界であることが示されている。

特許論争[編集]

カーマーカーはAT&Tに採用されたのち、彼がこのアルゴリズムを発見してからは、彼と雇用者のAT&Tは常にこの発明が実用上重要なものとなる、ということを信じて疑わなかった。1985年4月になるとすぐさまAT&Tは、カーマーカーのアルゴリズムを特許として出願し、ソフトウェア特許問題ついての従来からの論争に対し火に油を注いだ[3]ロナルド・リベストをはじめとする多くの数学者がこの事態の進展を不安視し(しかし、皮肉なことにロナルドはRSA暗号アルゴリズムの特許権保持者の一人である)、アルゴリズムはフリーであるべきとの考えに沿って研究を進めるとの意見を彼らの多くが述べていた。実際に特許が既に認可されたとしても、適用可能な先行技術英語版が存在するとも考えられていた[4]フィリップ・ギル(Philip Gill)などをはじめとする数値解析を専攻する数学者たちは、適切な媒介変数を選択することで、カーマーカーのアルゴリズムが対数障壁関数英語版射影ニュートン障壁法(projected Newton barrier method)と同値であることを証明した[5]。ギルが提示した手法は1960年代から非線形計画法に広く利用されている。また事実として、1968年に初版が出版されたある著名な書籍には、線形計画問題の解法としてこの手法が明示されていた[6]。しかしながら、数名が次のように述べている。彼らが主張する手法が「アルゴリズム」としてさえも見なされない限り、ギルの証明に誤りがある。なぜなら、その手法は内部的なアルゴリズムからは導けない媒介変数を選択する必要があることを示しているが、しかしそれは外部の補助に依存、すなわち実質的にはカーマーカーのアルゴリズムから導かれるものであるためである[7]。そのうえ、ザルツマン(Saltzman)により引用されている、フィアッコ=マコーミック(Fiacco-McCormick)、ギル、その他の人物による全ての先行作業を考慮してみると、カーマーカーが与えた貢献は明快なものとは程遠いと考えられる[7][8][9]。この発明は1988年5月、アメリカ合衆国特許第4,744,026号"Methods and apparatus for efficient resource allocation"(「最適資源割当のための方法および装置」)として結局認可された。本アルゴリズムは射影変換アフィン変換の組み合わせによる線形計画問題の解法であり[10]、米国の特許では双方のアルゴリズムそれぞれに特許が与えられている。日本では後者にのみ特許が出願公告(当時)され、その後特許が認められた。

  • 特許第2033073号「最適資源割当方法」
  • 特願昭61-501865
  • 特公昭62-502580
  • 特公平5-61672

しかしながら、AT&Tにとってこの特許の商用的価値は限られたものになった。彼らはKORBX[注釈 5]というシステムを製造した[11]。このシステムは、アライアント製のプロセッサ8つを搭載し、カーマーカーのアルゴリズムを使用するソフトウェアを組み合わせて線形計画問題を解くという専用システムであり、1台890万ドルもの値段が付けられていた。しかし、売れたのは2台だけだった[4][注釈 6]。日本においては、1997年(平成9年)今野浩らにより本特許の無効審判請求がなされた(事件番号:平成9年審判第2452号事件)が、特許庁審判官は、「本件発明が、ハードウェア資源を用いて最適割当てのための演算処理を当該アルゴリズムを利用し結果を得るものであると認める。本件発明はアルゴリズムそのものではなく、また計算機を単に利用しただけのものでもない。」とし、原告の訴えを無効とする審決を下した[12]

本審決後、原告は審決取消を求め東京高等裁判所出訴した(事件番号:平成11年(行ケ)第25号 審決取消請求事件)。この訴えに対する判決[13]において、被告のルーセント・テクノロジー(カーマーカーが所属したAT&Tテクノロジーの承継企業)が2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録を行っていたことが明らかになった。以下判決文より引用すると、

弁論の全趣旨によれば、被告は、本件特許権をその請求項1ないし6のすべてについて放棄し、平成12年12月11日付けで、特許庁に対し、放棄による特許権抹消の登録を申請し、その後間もなく、これに基づき本件特許権の登録は抹消されたことが認められる。被告は、本件特許権が放棄されたことにより,本件訴訟における原告らの訴えの利益は消滅した、と主張する。

このことにより、原告の訴えは利益が消滅したため、本件は却下されている。結果として該当特許自身が「発明」の要件を満たしていたかの結論は出ていない。

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

ソフトウェア特許に反対する者は、線形計画法の研究者と産業界とのつながりを以前から特徴付けている、両者の相互交流の正のサイクルを特許が駄目にしてしまうと強く主張している。そして、特許のせいで、他ならぬカーマーカー自身が線形計画法を共に研究する数学者の輪から孤立してしまった、と主張している[14]

脚注[編集]

参考文献[編集]

[ヘルプ]

注釈[編集]

  1. ^ "feasible set"。または"feasible region"(「実行可能領域」)などとも呼ばれる。"feasible"は「許容」、「制約」などとも訳される。候補解英語版を参照。
  2. ^ 停止条件。アルゴリズムの通り、while文は停止条件を満たすとループを抜ける。
  3. ^ 行列の対角成分を代入。
  4. ^ 条件を満たす場合は、戻り値"unbounded"を返す。
  5. ^ マシュー・ザルツマン(Matthew Saltzman)はこの文字列には何の意味もないと述べている。一方今野浩は『カーマーカー特許とソフトウェア』(ISBN 978-4121012784)上で、これは"Karmarkar OR box"を略して名付けたのではないかと述べている。ORはオペレーションズ・リサーチの略。
  6. ^ 『カーマーカー特許とソフトウェア』(ISBN 978-4121012784)によると購入したのはデルタ航空ペンタゴンだった。

出典[編集]

  1. ^ Gilbert Strang英語版 (1987-06-01). “Karmarkar’s algorithm and its place in applied mathematics”. The Mathematical Intelligencer英語版 (New York: Springer) 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR883185 '''883185'''. 
  2. ^ Robert J. Vanderbei英語版; Meketon, Marc, Freedman, Barry (1986). “A Modification of Karmarkar's Linear Programming Algorithm”. Algorithmica 1: 395–407. doi:10.1007/BF01840454. 
  3. ^ Kolata, Gina (1989年3月12日). “IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes”. The New York Times. http://www.nytimes.com/1989/03/12/weekinreview/ideas-trends-mathematicians-are-troubled-by-claims-on-their-recipes.html 
  4. ^ a b Various posts by Matthew Saltzman”. Clemson University. 2011年5月24日閲覧。
  5. ^ Gill, Philip E.; Murray, Walter, Saunders, Michael A., Tomlin, J. A. and Wright, Margaret H. (1986). “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method”. Mathematical Programming 36 (2): 183–209. doi:10.1007/BF02592025. http://www.springerlink.com/content/2781h35w87600923/. 
  6. ^ Anthony V. Fiacco; Garth P. McCormick (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques.. New York: Wiley. ISBN 978-0-471-25810-0.  1990年SIAM英語版により再版されている(ISBN 978-0-89871-254-4)。
  7. ^ a b Andrew Chin (2009). “On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens”. Journal Of Intellectual Property Law 16: 214 - 223. http://andrewchin.com/chin/scholarship/abstraction-equivalence.pdf. 
  8. ^ Mark A. Paley (1995). "The Karmarkar Patent: Why Congress Should “Open the Door” to Algorithms as Patentable Subject Matter". 22 COMPUTER L. REP. 7
  9. ^ Margaret H. Wright (2004). “The Interior-Point Revolution in Optimization: History, Recent Developments, and Lasting Consequences”. Bulletins of the American Mathematical Society 42: 39 - 56. http://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01040-7/S0273-0979-04-01040-7.pdf. 
  10. ^ カーマーカー特許”. ORWiki (2007年7月19日). 2011年5月25日閲覧。
  11. ^ Marc S. Meketon; Y.C. Cheng, D.J. Houck, J.M.Liu, L. Slutsman, Robert J. Vanderbei英語版, and P. Wang (1989). “The AT&T KORBX System”. AT&T Technical Journal 68: 7–19. 
  12. ^ カーマーカー法特許無効審判審決”. t4tomita.lolipop.jp. 2011年5月25日閲覧。
  13. ^ 平成11年(行ケ)第25号 審決取消請求事件 平成14年2月26日口頭弁論終結 判決 (PDF)”. 最高裁判所. 2011年5月25日閲覧。
  14. ^ 今野浩(Konno Hiroshi). “カーマーカー特許とソフトウェア -- 数学は 特許に なるか (The Kamarkar Patent and Software -- Has Mathematics Become Patentable?)”. FFII英語版. 2011年5月25日閲覧。

関連項目[編集]

外部リンク[編集]