相良信子,山川栄樹
線形計画問題に対する
射影変換法とアフィン変換法
Abstract:本稿では、文献 ”S.-C. Fang and S. Puthenpura, Linear Optimization and Extensions: Theory and Algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1993.” の第 5 章および第6章に記述されている、線形計画問題に対するカーマーの射影変換法とアフィン変換法について紹介した。特に、最後に述べた主双対内点法は、線形計画問題にとどまらず、2次計画問題、さらには、一般の非線形計画問題に対しても拡張され、多くの研究者によってその大域的収束性や局所的な収束率が研究されている。また、大規模な問題に対する数値実験を通して、実用的にも非常に有効な方法として注目を集めている。本稿が、内点法に興味をおもちの方、あるいは、内点法を用いて計算をしてみようと思っておられる方の参考になれば幸いである。