単体法と内点法
- 作者: 田村明久,村松正和
- 出版社/メーカー: 共立出版
- 発売日: 2002/04/01
- メディア: 単行本
- 購入: 2人 クリック: 27回
- この商品を含むブログ (8件) を見る
非常にナイーブな発想をすると、単体法は頂点をジャンプしていく方式なので、頂点が非常に多い時、もっと極端にいえば、許容領域が1億角形だったりすると、不利になるような気がしますが、この発想は合っているのでしょうか。1億角形なんてそうそうないだろう、と一瞬思いましたが、本来、非線形な許容領域を線形で無理やり近似してやろうと思うと、出てきそうな気がします。極端なことを言えば、許容領域が円のとき、「円を1億角形で近似してLPで解く」という発想をしたら、1億角形でてきますよね。まぁ、頂点の数が増えても、xの次元が増えれば、少ないジャンプで最適解まで到達できそうな気がしますが。
ちなみに、この本は、最適化法の入門書でもありますが、同時に、内点法について、かなり詳しく書かれています。この本の2章で、線形計画を解くのに使っている内点法は、パス追跡法の一種らしいです。