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

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

半正定値条件の強さ

2009年03月25日 01時05分07秒 | Weblog
添付の図中にもあるのだが、変数の二次式 (例えば z z^T)を SDP の定式化に組み入れるためには Z - z z^T = O と置いてから Z - z z^T succeq O と緩和する。その後は Schur complement の仕組みを用いて図中のように Z, z, z_0(=1) に関する半正定値条件が完成する。いろいろと試してみたのだが、この仕組みだけだと条件が弱いせいなのか、Z と z z^T の値は近い値にはならない。問題によってはいろいろな制約式を追加することによって状況が改善するのだが、一般形での制約強化という方法を見付けるのは難しそうだ。
コメント
この記事をはてなブックマークに追加