最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

非線形計画と SOCP, SDP

2006年06月09日 04時18分18秒 | Weblog
LANCELOT (非線形計画用のソフトウェア)で SOCP (二次錐計画問題)を解いてみると内点法ベースの SeDuMi で解くよりも相当速い。前者は Fortran で組まれていて相当チューニングされているらしいが、後者は MATLAB 上で動作するので多少割り引いて考える必要があるかもしれないが、それでも実行時間が一桁違ったりするので有意差があると見ていいだろう。実は SDP(半正定値計画問題)でも内点法よりも非線形計画のアルゴリズムを採用している PENNONの方が解くのが速い場合が多い。
しかしニュートン法のような非線形計画法のアルゴリズムで SDP を解くと大きくて複雑な問題では精度が良くない。しかし SOCP は SDP よりは単純な構造をしているので、LANCELOT などでも十分な精度が出るようだ。実験が少ないのでわからないが、SOCP は内点法よりも非線形計画の手法で解いた方が良いという可能性は大いにあるだろう。
コメント
この記事をはてなブックマークに追加