「半正定値計画緩和」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(3人の利用者による、間の3版が非表示)
1行目: 1行目:
−
'''【はんせいていちけいかくかんわ (semidefinite programming relaxation)】'''
+
'''【 はんせいていちけいかくかんわ (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>$以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.
+
[[組合せ最適化問題]]または非凸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:線形計画|はんせいていちけいかくかんわ]]

2008年11月13日 (木) 13:44時点における最新版

【 はんせいていちけいかくかんわ (semidefinite programming relaxation) 】

組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和すること． 典型的な例としては， 問題 （は行列）を と表現し， この制約をが実対称半正定値の行列で， 対角成分が以下というより緩い制約に置き換える． 置き換えた後の問題は半正定値計画となる． 半正定値緩和は理論的にも有力な下界を与えることが知られている．

「https://orsj-ml.org/orwiki/wiki/index.php?title=半正定値計画緩和&oldid=10863」から取得