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

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

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

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

1. アルゴリズム
---------

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

maximize //c////T////x// subject to //Ax// ≤ //b//.すなわち、

条件 //Ax// ≤ //b// の下で、 //c////T////x// を最大にするベクトル //x// を求める。このアルゴリズムはその時点での最適化実行可能方向  を求め、0 < γ ≤ 1 の範囲で縮小する。

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

Input: A, b, c, , //stopping criterion//, .

do while //stopping criterion// not satisfiedif thenreturn unboundedend ifend do

2. 例題
-----

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

maximize subject to 上記には、2つの変数 と、11の束縛変数 がある。本節の例解図には、アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。

3. 計算量
------

を変数の個数、 をアルゴリズムの入力ビット数としたとき、カーマーカーのアルゴリズムは、桁数のオーダー に対し、操作数  のオーダー をもつ。比較として、楕円体法の操作数は のオーダーをもつ。カーマーカーのアルゴリズムの実行時間は、高速フーリエ変換に基づく乗算であるシェーンハーゲ・シュトラッセンのアルゴリズムで使用した場合、以下のオーダーをもつ。

4. 特許論争
-------

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

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

本審決後、原告は審決等取消訴訟を求め東京高等裁判所に出訴した。この訴えに対する判決において、被告のルーセント・テクノロジーが2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録を行っていたことが明らかになった。以下判決文より引用すると、 これによって原告の訴えの利益が消滅したので、本件は却下されている。結果として該当特許自身が「発明」の要件を満たしていたかは判示されていない。

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

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

5. 脚注
-----

5.1. 参考文献
---------

Ilan Adler, Narendra Karmarkar, Mauricio G.C. Resende and Geraldo Veiga . "An Implementation of Karmarkar's Algorithm for Linear Programming". //Mathematical Programming//, Vol 44, p.   297–335.
Narendra Karmarkar . "[1]", //Combinatorica//, Vol 4, nr. 4, p.   373–395.

5.2. 注釈
-------

5.3. 出典
-------

6. 関連項目
-------

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

7. 外部リンク
--------

ORWikiより
[2]
[3]
CiNiiより、カーマーカーのアルゴリズムを利用した論文
[4]
[5]
[6]
カーマーカー特許
[7]
[8]
その他の「アルゴリズム特許」
4646256}} "Computer and method for the discrete bracewell transform"
特許として認められなかったアルゴリズムの例。別人による全く別種の発明であり、本特許係争終結後に出願された。しかし、カーマーカー特許とは異なり、解法の説明に終始しているとの判決が下されている。
[9]