分離問題 - 版の履歴

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

2008-11-13T06:57:41Z

Orsjwiki: "分離問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:53:49Z

"分離問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 04:59に122.17.2.240による

2007-07-17T04:59:29Z

2007年7月13日 (金) 16:39に222.225.128.209による

2007-07-13T16:39:02Z

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

2007-07-13T01:53:44Z

122.17.2.240: 新しいページ: '【ぶんりもんだい (separation problem)】凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$...'

2007-07-13T01:53:34Z

新しいページ: '【ぶんりもんだい (separation problem)】凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$...'

新規ページ

【ぶんりもんだい (separation problem)】

凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_*$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_* > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.

← 古い版		2008年11月13日 (木) 06:57時点における版
2行目:		2行目:

	凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_ > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.		凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_ > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.
		+
		+	[[Category:線形計画\|ぶんりもんだい]]

← 古い版		2007年7月17日 (火) 04:59時点における版
1行目:		1行目:
−	【ぶんりもんだい (separation problem)】	+	'''【ぶんりもんだい (separation problem)】'''

	凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_ > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.		凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_ > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.

← 古い版		2007年7月13日 (金) 16:39時点における版
1行目:		1行目:
	【ぶんりもんだい (separation problem)】		【ぶんりもんだい (separation problem)】

−	凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b~~$ $~~(\forall x \in P)$ かつ$a^{\rm T} x_ > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.	+	凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_ > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.

← 古い版		2007年7月13日 (金) 01:53時点における版
1行目:		1行目:
	【ぶんりもんだい (separation problem)】		【ぶんりもんだい (separation problem)】

−	凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_ > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.	+	凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_ > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.

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