単体法と内点法

最適化法 (工系数学講座 17)

最適化法 (工系数学講座 17)

この2章、線形計画問題の章を読んでいるのですが、どうもよくわかりません。結局、どういう場合に単体法を使うとよくて、どういう場合に内点法を使うとよいのでしょうか?いや、そりゃ微妙なケースもあると思いますけど、「こういう場合は明らかに内点法の方がいい」という例を自分で考えてみても、その考えが正しいかどうか確信が持てないわけです。誰か分かる方がいらっしゃれば、教えていただければ幸いです。

非常にナイーブな発想をすると、単体法は頂点をジャンプしていく方式なので、頂点が非常に多い時、もっと極端にいえば、許容領域が1億角形だったりすると、不利になるような気がしますが、この発想は合っているのでしょうか。1億角形なんてそうそうないだろう、と一瞬思いましたが、本来、非線形な許容領域を線形で無理やり近似してやろうと思うと、出てきそうな気がします。極端なことを言えば、許容領域が円のとき、「円を1億角形で近似してLPで解く」という発想をしたら、1億角形でてきますよね。まぁ、頂点の数が増えても、xの次元が増えれば、少ないジャンプで最適解まで到達できそうな気がしますが。

ちなみに、この本は、最適化法の入門書でもありますが、同時に、内点法について、かなり詳しく書かれています。この本の2章で、線形計画を解くのに使っている内点法は、パス追跡法の一種らしいです。