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

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

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

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

アルゴリズム

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

maximize c^Tx

subject to Ax≤ b.

すなわち、

条件 Ax≤ bの下で、

c^Tx を最大にするベクトル xを求める。

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

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

Algorithm Affine-Scaling

  Input:  A, b, c, $x^{0}$, stopping criterion, $\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})$
     $h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c$
     $h_{v}\leftarrow -Ah_{x}$
     if $h_{v}\geq 0$ then
        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}$$x_{1}+x_{2}$
subject to $2px_{1}+x_{2}\leq p^{2}+1,\quad p=0.0,0.1,0.2,\ldots ,0.9,1.0.$$2px_{1}+x_{2}\leq p^{2}+1,\quad p=0.0,0.1,0.2,\ldots ,0.9,1.0.$
上記には、2つの変数 $x_{1},x_{2}$$x_{1},x_{2}$と、11の束縛変数 $p$$p$がある。本節の例解図には、アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。

計算量

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

$O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)$$O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)$
︵記号"O"についてはランダウの記号を参照のこと。︶

特許論争

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

●特許第2033073号﹁最適資源割当方法﹂

●特願昭61-501865

●特公昭62-502580

●特公平5-61672

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

日本の特許異議申立、無効審判等については「日本の特許制度」を参照

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

弁論の全趣旨によれば、被告は、本件特許権をその請求項1ないし6のすべてについて放棄し、平成12年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)カーマーカ特許
• その他の「アルゴリズム特許」
  • アメリカ合衆国特許第 4,646,256号 "Computer and method for the discrete bracewell transform"
• 特許として認められなかったアルゴリズムの例。別人による全く別種の発明であり、本特許係争終結後に出願された。しかし、カーマーカー特許とは異なり、解法の説明に終始しているとの判決が下されている。
  • 東京高裁平成16年（行ケ）第188号 審決取消請求事件