「半正定値計画緩和」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【はんせいていちけいかくかんわ (semidefinite programming relaxation)】 組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和す...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (4人の利用者による、間の4版が非表示) | |||
| 1行目: | 1行目: | ||
| − | + | '''【 はんせいていちけいかくかんわ (semidefinite programming relaxation) 】''' | |
| − | + | [[組合せ最適化問題]]または非凸2次計画問題を[[半正定値計画]]で緩和すること． | |
| + | 典型的な例としては， | ||
| + | 問題<math>\mathop{\mbox{min.}} x^{\top}Qx\ \mbox{s.t.}\ x \in \{-1, 1\}^n</math> | ||
| + | （<math>Q</math>は<math>n\times n</math>行列）を | ||
| + | <math>\mathop{\mbox{min.}}\ \mbox{trace}(QX)\ \mbox{s.t.}\ X=xx^{\top},\ x\in\{-1, 1\}^n</math>と表現し， | ||
| + | この制約を<math>X</math>が実対称半正定値の行列で， | ||
| + | 対角成分が<math>1</math>以下というより緩い制約に置き換える． | ||
| + | 置き換えた後の問題は半正定値計画となる． | ||
| + | 半正定値緩和は理論的にも有力な下界を与えることが知られている． | ||
| + | |||
| + | [[Category:線形計画|はんせいていちけいかくかんわ]] | ||
