分離問題のソースを表示
←
分離問題
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、以下のグループに属する利用者のみが実行できます:
登録利用者
。
このページは編集や他の操作ができないように保護されています。
このページのソースの閲覧やコピーができます。
【ぶんりもんだい (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}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.
分離問題
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
最近の更新
おまかせ表示
ヘルプ
ORWikiへのお問い合わせ
OR学会HP
OR学会アーカイブ集
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報