スラック変数

スラック変数#

  • 読み: すらっくへんすう

  • 英名: Slack Variable

最適化問題において,不等式制約を等式制約に変換するために導入する変数のことをスラック変数と呼ぶ.具体的には,ある最適化問題の不等式制約が関数 \(g \colon \mathbb{R}^n \to \mathbb{R}\) と定数 \(b \in \mathbb{R}\) によって

(69)#\[g \left( x \right) \le b \left(x \in \mathbb{R}^n \right)\]

の形で記述されているとき,この不等式制約はスラック変数 \(y \in \mathbb{R} \left( y \ge 0 \right)\) を導入することで

(70)#\[g \left( x \right) + y = b, y \ge 0 \left(x \in \mathbb{R}^n, y \in \mathbb{R} \right)\]

のように,等式制約と非負制約の形に変換することができる.

スラック変数の典型的な使用例としては,不等式制約を含む線形計画問題を以下のような標準形と呼ばれる形式に変換することが挙げられる(\(A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R}^n\)).

(71)#\[\begin{split}\begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax = b \\ & x \ge 0 \end{array}\end{split}\]