アフィンスケーリング法

アフィンスケーリング法

アフィンスケーリング法は、数理最適化の分野における線形計画問題を解決するための効果的なアルゴリズムです。この手法は、内点法の一形式とされ、最初に1967年にソ連の数学者I.I.ディキンによって提唱されました。その後、1980年代にアメリカで再発見され、注目を集めることとなりました。

歴史的背景

アフィンスケーリング法は、1967年にロシアの学術誌「Doklady Akademii Nauk SSSR」において発表されました。ディキンによるこの発見は、線形計画に対する初の実用的な多項式時間アルゴリズムとして評価されていました。しかし、1974年に収束性が証明されるまでは、それに対する関心はそれほど高くありませんでした。その後、1984年にカーマーカー法が発表されると、アフィンスケーリング法への注目も高まり、新たな研究が進められることになりました。

カーマーカー法の登場により、アフィンスケーリングに関する研究は活発化しました。当初はDiakinのアイデアが独立に再発見されたとされましたが、最終的にはこれらの手法がディキンによる研究をベースにしていることが明らかになりました。特に、Barnesやヴァンダーベイのチームが提示したアイデアが重要視され、収束性の証明にも至ったことで理解が深まりました。

アルゴリズムの構造

アフィンスケーリング法は大きく2つの段階に分かれています。
1. 最初の段階では、実行可能な点を見つけることを目指します。
2. 次の段階では、実行可能領域の内部を通ることにより、実際の最適解を求めます。

このアルゴリズムは、線形計画問題を解く際に、内部点を生成するための反復的な手法であり、1サイクル内で問題をスケーリングし、適切なアフィン変換を適用します。これにより、既存の反復点が境界近くにあったとしても、適切なステップ数を確保することが可能になります。

具体的には、以下のような手順で進行します：まず、初期解を設定し、許容する誤差とステップサイズを決定します。その後、双対変数を計算し、被約費用ベクトルを求めます。これに基づいて、現在の解が近似最適解か、または問題が非有界であるのかを判定します。次いで、各ステップで元の問題を更新していきます。

収束性に関する分析

アフィンスケーリング法の実装は比較的簡単ですが、その収束特性の分析は難解とされています。特に、ステップサイズが収束性に大きな影響を与えることが知られています。ステップサイズが2/3以下の際に収束する一方、0.995を超えると最適値から逸脱する可能性があるため、注意が必要です。また、他の変種に関しても、収束の特性や挙動が異なることが確認されています。

参考文献

• - Ilan Adler, Renato D. C. Monteiro (1991). “Limiting behavior of the affine scaling continuous trajectories for linear programming problems”. Mathematical Programming 50 (1–3): 29–51.
• - Romesh Saigal (1996). “A simple proof of a primal affine scaling method”. Annals of Operations Research 62: 303–324.
• - Paul Tseng, Zhi-Quan Luo (1992). “On the convergence of the affine-scaling algorithm”. Mathematical Programming 56 (1–3): 301–319.

このように、アフィンスケーリング法は数学や最適化の分野において、その活用の幅が広く、理論的にも実践的にも重要な位置を占めています。今後もこの手法を基にしたさらなる研究が期待されます。

もう一度検索