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

カルマルカーのアルゴリズムは、1984年にナレンドラ・カルマルカーによって線形計画問題を解くために考案されたアルゴリズムです。これは、これらの問題を多項式時間で解くことができる、最初の比較的効率的なアルゴリズムでした。楕円体法も多項式時間で解くことができますが、実際には非効率的であることが証明されています。

と表記する${\displaystyle n}$変数の数、m は不等式制約の数、そして${\displaystyle L}$カルマルカーのアルゴリズムに必要な入力ビット数${\displaystyle O(m^{1.5}n^{2}L)}$オペレーション${\displaystyle O(L)}$桁数と比較して、${\displaystyle O(n^{3}(n+m)L)}$楕円体アルゴリズムでは、このような操作が必要です。^{[ 1 ]}「正方形」問題では、mが O( n ) の場合、カルマルカーのアルゴリズムでは、${\displaystyle O(n^{3.5}L)}$オペレーション${\displaystyle O(L)}$桁数と比較して、${\displaystyle O(n^{4}L)}$楕円体アルゴリズムの場合、このような操作が行われます。したがって、カルマルカーのアルゴリズムの実行時間は $${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}$$FFTベースの乗算 を使用します（ビッグオー記法を参照）。

カルマルカーのアルゴリズムは内点法のクラスに属します。解の現在の推定値は、シンプレックス法のように実行可能集合の境界をたどるのではなく、実行可能領域の内部を移動し、反復ごとに最適解の近似を一定の割合で改善し、有理データを持つ最適解に収束します。^{[ 2 ]}

行列形式の線形計画問題を考えてみましょう。

カルマルカーのアルゴリズムは、最適性に向かう次の実行可能な方向を決定し、0 < γ ≤ 1の係数で縮小します。これは多くの文献で説明されています。^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}カルマルカーはまた、整数制約のある問題や非凸問題を解くためにこの方法を拡張しました。 ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ]}

アルゴリズムアフィンスケーリング

入力: A、b、c、${\displaystyle x^{0}}$停止基準、γ。

${\displaystyle k\leftarrow 0}$停止条件が満たされていない間実行する${\displaystyle v^{k}\leftarrow b-Ax^{k}}$${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$${\displaystyle h_{v}\leftarrow -Ah_{x}}$もし${\displaystyle h_{v}\geq 0}$その後、 無制限の 終了を返します。${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$${\displaystyle k\leftarrow k+1}$end do

線形計画法を考える $${\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}$$ つまり、変数は2つあります。${\displaystyle x_{1},x_{2}}$そして、さまざまな値に関連する 11 の制約${\displaystyle p}$この図は、アルゴリズムの各反復処理を赤い丸印で示しています。制約条件は青い線で示されています。

アルゴリズムを発明した当時、カルマルカーはIBMのカリフォルニア州サンノゼ研究所で博士研究員として働いていた。1983年8月11日、彼はスタンフォード大学でアルゴリズムを説明するセミナーを行ったが、その時点では所属機関はまだIBMと記載されていた。1983年の秋までにカルマルカーはAT&Tで働き始め、1984年4月30日から5月2日に開催されたACM理論計算機科学シンポジウム（STOC）に論文を提出し、所属機関をAT&Tベル研究所と記載した。 ^{[ 16 ]}アルゴリズムをAT&Tの電話ネットワークの最適化に適用した後、^{[ 17 ]}彼らは彼の発明が実用上重要なものになり得ることに気づいた。1985年4月、AT&Tはすぐに彼のアルゴリズムの特許を申請した。

この特許は、ソフトウェア特許の問題に関する継続的な論争にさらに火種を投じることになった。^{[ 18 ]} これにより、多くの数学者が不安を感じ、例えばロナルド・リベスト（ RSAアルゴリズムの特許権者の1人）は、アルゴリズムは自由であるべきだという前提で研究が進められているという意見を表明した。特許が実際に付与される前から、適用可能な先行技術が存在する可能性があると議論されていた。 ^{[ 19 ]}フィリップ・ギルをはじめとする数値解析を専門とする数学者たちは、パラメータを適切に選択すれば、カルマルカーのアルゴリズムは対数バリア関数を用いた射影ニュートンバリア法と同等であると主張した。 ^{[ 20 ]} 法学者のアンドリュー・チンは、ギルの主張は欠陥があると主張している。彼らが説明する方法は「アルゴリズム」を構成しないからである。なぜなら、その方法は、方法の内部ロジックから導かれるのではなく、本質的にはカルマルカーのアルゴリズムからの外部ガイダンスに依存するパラメータの選択を必要とするからである。^{[ 21 ]}さらに、カルマルカーの貢献は、フィアッコ＝マコーミック、ギル、ソルトマンが引用した他の研究者を含むすべての先行研究に照らして、決して自明ではないと考えられている。^{[ 21 ] [ 22 ] [ 23 ]} カルマルカーの研究の本質的な独創性が認められ、 1988年5月に米国特許第4,744,028号「効率的な資源配分の方法および装置」として特許が付与された。

AT&Tは、カルマルカーのアルゴリズムを実行するために特別にベクトルマルチプロセッサコンピュータシステムを設計し、その結果得られたハードウェアとソフトウェアの組み合わせをKORBXと名付けました^{[ 24 ]}。そして、このシステムを890万米ドルで販売しました^{[ 25 ] [ 26 ]。}最初の顧客はペンタゴンでした^{[ 27 ] [ 28 ]}。

ソフトウェア特許の反対者はさらに、特許が線形計画法の研究者と産業界との関係を特徴づけていた肯定的な相互作用サイクルを破壊し、特にカルマルカー自身をその分野の数学研究者のネットワークから孤立させたと主張している。^{[ 29 ]}

特許自体は2006年4月に失効しており、このアルゴリズムは現在パブリックドメインとなっている。

米国最高裁判所は、Gottschalk v. Benson事件^{[ 30 ]}において、数学は特許の対象とならないとの判決を下した。同事件では、まずコンピュータ アルゴリズムが特許の対象となり得るか否かが検討され、特許制度はアイデアや同様の抽象概念を保護しないため、特許の対象とはならないとの判決が下された。Diamond v. Diehr 事件^{[ 31 ]}において、最高裁判所は、「数学的公式そのものは、特許法の保護を受けるものではなく、この原則は、公式の使用を特定の技術環境に限定しようとすることで回避することはできない」と述べている。^{[ 32 ]} Mayo Collaborative Services v. Prometheus Labs., Inc. 事件[ ^{33 ]において}、最高裁判所はさらに、「数学的原理を物理的な機械、すなわちコンピュータに実装するだけでは、その原理の特許可能な応用とはならない」と説明している。^{[ 34 ]}

カルマルカーのアルゴリズムは、湾岸戦争中の兵站計画に米陸軍によって使用された。^{[ 1 ]}

• Adler, Ilan ; Karmarkar, Narendra; Resende, Mauricio GC ; Veiga, Geraldo (1989). "線形計画法のためのKarmarkarアルゴリズムの実装". Mathematical Programming . 44 ( 1– 3): 297– 335. doi : 10.1007/bf01587095 . S2CID 12851754 . 
• Narendra Karmarkar (1984). "線形計画法のための新しい多項式時間アルゴリズム", Combinatorica、第4 巻、第4号、 373 ～ 395ページ。