2. 等式制約の不等式制約への分解#
2.1. 導入#
非線形計画問題 を安定させるための定式化技法として， 等式制約を不等式制約へと分解する方法がある． これは数学的には自明な書き換えであるが，求解アルゴリズム側では非自明な情報として扱われることを狙った書き換えである．
2.2. 等式制約に同値な不等式制約#
一つの等式制約は，二つの不等式制約に変換することができる．
具体的には，以下の等式制約があるとする．
(1)#\[f(x) = a\]
このとき，制約式は以下のように変換できる．
(2)#\[\begin{split}f(x) &\geq a, \\
f(x) &\leq a\end{split}\]
2.3. 例題#
非線形計画問題では，そのアルゴリズムの特性上， 等式制約を不等式制約として書き直すと，求解が安定する場合がある．
例えば，以下のような問題があるとする．
(3)#\[\begin{split}& \mathrm{Minimize\colon}~ -2x_1 - x_2 \\
& \mathrm{subject~to\colon}~ \\
& x_1 - x_2 = 3, \\
& -x_1 + x_2 = -1\end{split}\]
このような問題は以下のように変換できる．
(4)#\[\begin{split}& \mathrm{Minimize\colon}~ -2x_1 - x_2 \\
& \mathrm{subject~to\colon}~ \\
& x_1 - x_2 \geq 3, \\
& x_1 - x_2 \leq 3, \\
& -x_1 + x_2 \geq -1, \\
& -x_1 + x_2 \leq -1\end{split}\]
このように変換した方が，アルゴリズムによっては安定する場合がある．
関連
用語集
引用書式