スラック変数 (slack variable)

スラック変数 (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)

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:21 (2494d)