最適化理論とカーマーカー特許と歴史

この記事は 数学 Advent Calendar 2016 - Qiita の6日目の記事です。

大学生の頃、ORを専攻していたため最適化理論について登壇した経験があります。

• 最適化問題を「線形計画法と整数計画法」で解く─プログラマのための数学勉強会5｜CodeIQ MAGAZINE

時々は最適化理論のことを書いて、最適化理論をアピールしようかと思います。

単体法について

最適化理論についての概要を知りたい場合は先ほどのリンクにあるスライドや動画を参照することをオススメします。 さて、線形計画問題の解法の一つに Dantzig 教授によって提案された単体法（シンプレックス法）という有限回で最適解に到達するということが保証されたアルゴリズムが有名です。 有限回で最適解に到達するのが保証されている理由は、最適解が端点に現れることを利用しているためです。

単体法の問題点

有限回で最適解に到達することが保証されているのですが、制約式の本数が増えることによって計算時間が指数関数的に膨大になる可能性があります。

カーマーカー法について

単体法に対して、1984年にカーマーカー法の発表によって注目されるようになった内点法は大規模な線形計画問題をより効率的に解くことが期待されています。この内点法は制約領域の内部を通って最適解に近づく方法であり、その計算時間が多項式オーダーに留まることが理論的に保証されています。

カーマーカー特許の概要

このカーマーカー法は優れているのですが、カーマーカーはカーマーカー特許として線形計画法の解法に関する特許を取得しています。このカーマーカー特許はアルゴリズム特許の代表例で、カーマーカーと米国のＡＴ＆Ｔ社がその特許を取得し、当時は「アルゴリズムが特許となり得るのか」といった社会問題となって物議を醸したことでOR界隈では有名になっています。

カーマーカー法の歴史

年	出来事	詳細
1985	カーマーカー特許申請（米）	カーマーカーとＡＴ＆Ｔが数学理論（数式）の特許を申請。アメリカは先発明主義のため顕在化せず。
1986	カーマーカー特許申請（日）	カーマーカー氏とＡＴ＆Ｔが日本に特許申請。
1988	カーマーカー特許申請認可（米）	数学理論（数式）が始めて特許認定される。
1989	ＡＴ＆ＴがＫＯＲＢＸを発売	アフィン変換法を用いたソフトを890万ドルで発売。
1990	ＸＭＰがＯＢ１を発売	内点法を用いたソフトを5万ドルで発売。ＡＴ＆ＴがＸＭＰに対し、ＯＢ１はカーマーカー特許に抵触すると警告し、売上５％の特許使用料を支払うことで和解。
1991	カーマーカー特許申請拒絶（日）	カーマーカー特許は計算手法そのものであるという理由で拒絶。これに対し、ＡＴ＆Ｔは審判請求。
1993	カーマーカー関連特許申請公告（日）	1991年の請求により逆転審判。これに対し、異議申立てが出される。
1998	カーマーカー関連特許無効審判請求	無効審判の請求は成り立たないとの審決。は不成立との審決（日）
1999	カーマーカー関連特許無効審判請求	審判請求人が審決の取り消しを求める裁判を提起。不成立審決の取り消し要求裁判（日）

おわりに

数学やアルゴリズムは研究が積み重なることによって、改良されていく分野なのですが、特許として囲まれてしまうとその発展が閉ざされるのではないかと若干不安になります。

リソース

もっと詳しく知りたい方はこちらの書籍を参考にしてみてください。

今野浩，カーマーカー特許とソフトウエア，中公新書

カーマーカー特許とソフトウェア―数学は特許になるか (中公新書)

伊庭 斉志，システム工学の基礎―システムのモデル化と制御，数理工学社

システム工学の基礎―システムのモデル化と制御 (新・情報 通信システム工学)