カーマーカーのアルゴリズム (英 : Karmarkar's algorithm )とは1984年 、ナレンドラ・カーマーカー により発見された線形計画問題 の解法である。このアルゴリズム は、しばしば、カーマーカー法 (英 : Karmarkar's method)とも呼ばれる。また、このアルゴリズムを発明 とする特許 が米国 や日本 で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。
カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間 アルゴリズムで初めての実用的なものである。楕円体法 (英語版 ) も多項式時間アルゴリズムであるが、実用上の効率は良くない。
カーマーカーのアルゴリズムは内点法 の一種である。内点法は、候補解を実行可能領域 の境界 に沿って更新する単体法 とは異なり、実行可能領域の内部 を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解 (optimal solution )に収束 する[ 1] 。
アルゴリズム
行列
A
{\displaystyle A}
、ベクトル
b
{\displaystyle b}
に対し、以下の正準形式 (英語版 ) な線形計画問題 を考える。
maximize c T x
subject to Ax ≤ b .
すなわち、
条件 Ax ≤ b の下で、
c T x を最大にするベクトル x を求める。
このアルゴリズムはその時点での最適化実行可能方向 (feasible direction toward optimality) を求め、0 < γ ≤ 1 の範囲で縮小する。
カーマーカーのアルゴリズムは複雑である。アフィン ・スケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている[ 2] 。このアルゴリズムは以下のように簡潔に示される。ただし、アフィン・スケーリング・アルゴリズムは実用上効率が良いが、多項式時間アルゴリズムではない。
Input: A, b, c,
x
0
{\displaystyle x^{0}}
, stopping criterion [ 注釈 1] ,
γ γ -->
{\displaystyle \gamma }
.
k
← ← -->
0
{\displaystyle k\leftarrow 0}
do while stopping criterion not satisfied
v
k
← ← -->
b
− − -->
A
x
k
{\displaystyle v^{k}\leftarrow b-Ax^{k}}
D
v
← ← -->
diag
-->
(
v
1
k
,
… … -->
,
v
m
k
)
{\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}
[ 注釈 2]
h
x
← ← -->
(
A
T
D
v
− − -->
2
A
)
− − -->
1
c
{\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}
h
v
← ← -->
− − -->
A
h
x
{\displaystyle h_{v}\leftarrow -Ah_{x}}
if
h
v
≥ ≥ -->
0
{\displaystyle h_{v}\geq 0}
then [ 注釈 3]
return unbounded
end if
α α -->
← ← -->
γ γ -->
⋅ ⋅ -->
min
{
− − -->
v
i
k
/
(
h
v
)
i
|
(
h
v
)
i
<
0
,
i
=
1
,
… … -->
,
m
}
{\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}
x
k
+
1
← ← -->
x
k
+
α α -->
h
x
{\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}
k
← ← -->
k
+
1
{\displaystyle k\leftarrow k+1}
end do
"←"は「代入 」を示す記号である。例えば、"α ← β "はα にβ を代入することを示す。
"return "はアルゴリズム を停止させ、戻り値を出力する。
例題
例解
以下の線形計画問題を考える。
maximize
x
1
+
x
2
{\displaystyle x_{1}+x_{2}}
subject to
2
p
x
1
+
x
2
≤ ≤ -->
p
2
+
1
,
p
=
0.0
,
0.1
,
0.2
,
… … -->
,
0.9
,
1.0.
{\displaystyle 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
{\displaystyle x_{1},x_{2}}
と、11の束縛変数
p
{\displaystyle p}
がある。本節の例解図には、アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。
計算量
n
{\displaystyle n}
を変数 の個数、
L
{\displaystyle L}
をアルゴリズムの入力ビット 数としたとき、カーマーカーのアルゴリズムは、桁数のオーダー
O
(
L
)
{\displaystyle O(L)}
に対し、操作数 (operations) のオーダー
O
(
n
3.5
L
)
{\displaystyle O(n^{3.5}L)}
をもつ。比較として、楕円体法の操作数は
O
(
n
6
L
)
{\displaystyle O(n^{6}L)}
のオーダーをもつ。カーマーカーのアルゴリズムの実行時間(runtime、計算量 )は、高速フーリエ変換 に基づく乗算 であるシェーンハーゲ・シュトラッセンのアルゴリズム で使用した場合、以下のオーダーをもつ。
O
(
n
3.5
L
2
⋅ ⋅ -->
log
-->
L
⋅ ⋅ -->
log
-->
log
-->
L
)
{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}
(記号"O"についてはランダウの記号 を参照のこと。)
特許論争
カーマーカーは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 [ 注釈 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] 。
脚注
参考文献
注釈
出典
^
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 . MR 883185 .
^
Robert J. Vanderbei (英語版 ) ; Meketon, Marc, Freedman, Barry (1986). “A Modification of Karmarkar's Linear Programming Algorithm”. Algorithmica 1 : 395–407. doi :10.1007/BF01840454 .
^
Kolata, Gina (1989年3月12日). “IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes” . The New York Times . https://www.nytimes.com/1989/03/12/weekinreview/ideas-trends-mathematicians-are-troubled-by-claims-on-their-recipes.html
^ a b
“Various posts by Matthew Saltzman ”. Clemson University . 2011年5月24日 閲覧。
^
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/ .
^
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 )。
^ 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 .
^
Mark A. Paley (1995). "The Karmarkar Patent: Why Congress Should “Open the Door” to Algorithms as Patentable Subject Matter". 22 COMPUTER L. REP. 7
^
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 .
^
“カーマーカー特許 ”. ORWiki (2007年7月19日). 2011年5月25日 閲覧。
^
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.
^
“カーマーカー法特許無効審判審決 ”. t4tomita.lolipop.jp. 2011年5月25日 閲覧。
^
“平成11年(行ケ)第25号 審決取消請求事件 平成14年2月26日口頭弁論終結 判決 ” (PDF ). 最高裁判所 . 2022年5月20日 閲覧。
^
今野浩 (Konno Hiroshi). “カーマーカー特許とソフトウェア -- 数学は 特許に なるか (The Kamarkar Patent and Software -- Has Mathematics Become Patentable?) ”. FFII (英語版 ) . 2011年5月25日 閲覧。
関連項目
外部リンク
ORWiki より
CiNii より、カーマーカーのアルゴリズムを利用した論文
カーマーカー特許
その他の「アルゴリズム特許」
特許として認められなかったアルゴリズムの例。別人による全く別種の発明であり、本特許係争終結後に出願された。しかし、カーマーカー特許とは異なり、解法の説明に終始しているとの判決が下されている。