半正定値計画緩和 - 版の履歴

2008年11月13日 (木) 04:44にAlbeit-Kunによる

2008-11-13T04:44:49Z

2007年9月19日 (水) 13:22にSaruによる

2007-09-19T13:22:03Z

Orsjwiki: "半正定値計画緩和" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:34:22Z

"半正定値計画緩和" を保護しました。 [edit=sysop:move=sysop]

2007年7月13日 (金) 03:51に211.9.146.171による

2007-07-13T03:51:23Z

2007年7月13日 (金) 01:32に122.17.2.240による

2007-07-13T01:32:06Z

122.17.2.240: 新しいページ: '【はんせいていちけいかくかんわ (semidefinite programming relaxation)】組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和す...'

2007-07-12T15:46:10Z

新しいページ: '【はんせいていちけいかくかんわ (semidefinite programming relaxation)】組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和す...'

新規ページ

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

組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和すること.典型的な例としては, 問題 $\mathop{\mbox{min.}} x^{\top}Qx\ \mbox{s.t.}\ x \in \{-1, 1\}^n$($Q$ は $n\times n$ 行列)を $ \mathop{\mbox{min.}}\ \mbox{trace}(QX)\ \mbox{s.t.}\ X=xx^{\top},\ x\in\{-1, 1\}^n$ と表現し, この制約を $X$ が実対称半正定値の行列で,対角成分が$1$以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.

← 古い版		2008年11月13日 (木) 04:44時点における版
10行目:		10行目:
	置き換えた後の問題は半正定値計画となる．		置き換えた後の問題は半正定値計画となる．
	半正定値緩和は理論的にも有力な下界を与えることが知られている．		半正定値緩和は理論的にも有力な下界を与えることが知られている．
		+
		+	[[Category:線形計画\|はんせいていちけいかくかんわ]]

← 古い版		2007年9月19日 (水) 13:22時点における版
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>以下というより緩い制約に置き換える．
		+	置き換えた後の問題は半正定値計画となる．
		+	半正定値緩和は理論的にも有力な下界を与えることが知られている．

← 古い版		2007年7月13日 (金) 03:51時点における版
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>以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.

← 古い版		2007年7月13日 (金) 01:32時点における版
1行目:		1行目:
−	【はんせいていちけいかくかんわ (semidefinite programming relaxation)】	+	'''【はんせいていちけいかくかんわ (semidefinite programming relaxation)】'''

−	組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和すること.典型的な例としては, 問題 $\mathop{\mbox{min.}} x^{\top}Qx\ \mbox{s.t.}\ x \in \{-1, 1\}^n$($Q$ は $n\times n$ 行列)を $ \mathop{\mbox{min.}}\ \mbox{trace}(QX)\ \mbox{s.t.}\ X=xx^{\top},\ x\in\{-1, 1\}^n$ と表現し, この制約を $X$ が実対称半正定値の行列で,対角成分が$1$以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.	+	組合せ最適化問題または非凸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>$以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.

← 古い版	2007年7月20日 (金) 01:34時点における版
(相違点なし)