* スラック変数 (slack variable) [#g6fd3a07]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

''スラック変数 (slack variable)'' は,数理計画法で定義された標準的な制約条件の形に適合させるために導入する変数.

例えば,線形計画問題では
\(A\mathbf{x}=\mathbf{b}, \mathbf{x}\ge0\)
が標準的な制約の形.

\(\mathbf{a_i}^\top\mathbf{x}\le b_i\)
のような制約があったとき,
\(\mathbf{a}_i^\top \mathbf{x} +\xi_i=b_i,\ \xi_i\ge0\)
のように書き換える.このとき,\(\xi_i\) がスラック変数.

線形計画問題の \(\mathbf{x}\) には,スラック変数が加わり
\[\mathbf{x}'=[x_1,\ldots,x_N,\xi_1,\ldots,\xi_L]^\top\]
のようになり,行列 A は,例えば次のようになる.
\[A'=\left(\begin{array}{cccccc}a_{11} & \cdots & a_{1N} & 1 & 0 \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{M1} & \cdots & a_{MN} & 0 & \cdots 0 & 1\end{array} \right)\]
※ 右側の部分は,スラック変数が導入されたところだけが1になる.スラック変数が不要な条件では全て 0.

[[SVM]]ではソフトマージンの導入時に用いられる.

一方,\(\mathbf{a_i}^\top\mathbf{x}\ge b_i\)
のような制約があったとき,
\(\mathbf{a}_i^\top \mathbf{x} -\eta_i=b_i,\ \eta_i\ge0\)
のように書き換える.このとき,\(\eta_i\) が''剰余変数 (surplus variable)''.

> -- しましま

** 関連項目 [#eabb7465]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[slack variable]]
#br
-[[剰余変数]]
-[[surplus variable]]
#br
-[[数理計画]]
-[[SVM]]
#br
-[[検索:スラック変数]]

** リンク集 [#g0878ce7]

//関連するWWW資源があればリンクしてください.

-[[Wikipedia:Slack_variable]]
-[[Wikipedia:Surplus_variable]]
-[[ORWiki:スラック変数]]

** 関連文献 [#z0ad90bd]

//この%項目%に関連する書籍や論文を紹介してください.

-[[Book/データマイニングの基礎]] 3.3.3節
-[[Book/最適化の手法]] 1.1節
-[[Book/パターン認識と学習の統計学(統計科学のフロンティア6)]] II部 3.1(c)節
-[[Book/Pattern Recognition and Machine Learning]] 7.1.1節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS