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

提供: miniwiki
2018/8/19/ (日) 17:19時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

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

カーマーカーのアルゴリズムは、線形計画問題に対する初の多項式時間アルゴリズムである。楕円体法English版も多項式時間アルゴリズムであるが、実用上の効率は良くない。

カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解を実行可能領域境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解optimal solution)に収束する。[1]

アルゴリズム

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

maximize cTx
subject to Axb.

すなわち、

条件 Axb の下で、
cTx を最大にするベクトル x を求める。

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

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

テンプレート:Algorithm-begin

  Input:  A, b, c, [math]x^0[/math], stopping criterion[注釈 1], [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][注釈 2]
     [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[注釈 3]
        return unbounded
     end if
     [math]\alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i \lt  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

例題

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

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] がある。英語版ウィキペディアには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、計算量)は、高速フーリエ変換に基づく乗算であるシェーンハーゲ・シュトラッセンのアルゴリズムEnglish版を使用した場合、以下のオーダーをもつ。

[math]O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)[/math]

(記号"O"についてはランダウの記号を参照のこと。)

特許論争

カーマーカーはAT&Tに採用されたのち、彼がこのアルゴリズムを発見してからは、彼と雇用者のAT&Tはこの発明が実用上重要なものとなる、ということを信じて疑わなかった。1985年4月になると、AT&Tは、カーマーカーのアルゴリズムを特許として出願し、ソフトウェア特許問題についての従来からの論争に対し火に油を注いだ[3]ロナルド・リベストをはじめとする多くの数学者がこの事態の進展を不安視し(しかし、皮肉なことにロナルドはRSA暗号アルゴリズムの特許権保持者の一人である)、アルゴリズムはフリーであるべきとの考えに沿って研究を進めるとの意見を彼らの多くが述べていた。実際に特許が既に認可されたとしても、適用可能な先行技術English版が存在するとも考えられていた[4]フィリップ・ギル (Philip Gill) などをはじめとする数値解析を専攻する数学者たちは、適切な媒介変数を選択することで、カーマーカーのアルゴリズムが対数障壁関数English版射影ニュートン障壁法 (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[注釈 4]というシステムを製造した[11]。このシステムは、アライアント製のプロセッサ8つを搭載し、カーマーカーのアルゴリズムを使用するソフトウェアを組み合わせて線形計画問題を解くという専用システムであり、1台890万ドルもの値段が付けられていた。しかし、売れたのは2台だけだった[4][注釈 5]。日本においては、1997年(平成9年)今野浩らにより本特許の無効審判請求がなされた(事件番号:平成9年審判第2452号事件)が、特許庁審判官は、「本件発明が、ハードウェア資源を用いて最適割当てのための演算処理を当該アルゴリズムを利用し結果を得るものであると認める。本件発明はアルゴリズムそのものではなく、また計算機を単に利用しただけのものでもない。」とし、原告の訴えを無効とする審決を下した[12]

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

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

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

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

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

脚注

参考文献

注釈

  1. 停止条件。アルゴリズムのとおり、while文は停止条件を満たすとループを抜ける。
  2. 行列の対角成分を代入。
  3. 条件を満たす場合は、戻り値"unbounded"を返す。
  4. マシュー・ザルツマン(Matthew Saltzman)はこの文字列には何の意味もないと述べている。一方、今野浩は『カーマーカー特許とソフトウェア』(ISBN 978-4121012784)上で、これは"Karmarkar OR box"を略して名付けたのではないかと述べている。ORはオペレーションズ・リサーチの略。
  5. 『カーマーカー特許とソフトウェア』(ISBN 978-4121012784)によると購入したのはデルタ航空ペンタゴンだった。

出典

  1. Gilbert StrangEnglish版 (1987-06-01). “Karmarkar’s algorithm and its place in applied mathematics”. The Mathematical IntelligencerEnglish版 (New York: Springer) 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 883185 '''883185'''. 
  2. Robert J. VanderbeiEnglish版; 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. 4.0 4.1 Various posts by Matthew Saltzman”. Clemson University. . 2011閲覧.
  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年SIAMEnglish版により再版されている(ISBN 978-0-89871-254-4)。
  7. 7.0 7.1 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閲覧.
  11. Marc S. Meketon; Y.C. Cheng, D.J. Houck, J.M.Liu, L. Slutsman, Robert J. VanderbeiEnglish版, and P. Wang (1989). “The AT&T KORBX System”. AT&T Technical Journal 68: 7–19. 
  12. カーマーカー法特許無効審判審決”. t4tomita.lolipop.jp. . 2011閲覧.
  13. 平成11年(行ケ)第25号 審決取消請求事件 平成14年2月26日口頭弁論終結 判決 (PDF)”. 最高裁判所. . 2011閲覧.
  14. 今野浩(Konno Hiroshi). “カーマーカー特許とソフトウェア -- 数学は 特許に なるか (The Kamarkar Patent and Software -- Has Mathematics Become Patentable?)”. FFIIEnglish版. . 2011閲覧.

関連項目

外部リンク

テンプレート:アルゴリズム テンプレート:最適化アルゴリズム