4. 絶対値最小化問題#
4.1. 説明#
絶対値最小化問題とは次のように目的関数に絶対値関数が含まれ， これを最小化する非線形な問題である．
(4.10)#\[\begin{split}& \mathrm{Minimize:}~ \sum_{j\in J} c[j]\cdot |x[j]| \\
& \mathrm{subject~to:}~ \\
& \sum_{j\in J} a[i,j]\cdot x[j] = b[i],~ \forall i\in I\end{split}\]
但し目的関数の線形結合の重みはすべて非負，つまり \(\forall j\in J\) に対して，\(c[j] \geq 0\) とする．
4.1.1. LPによる定式化#
絶対値最小化問題は絶対値関数のために非線形な問題となっているが， 以下のように定式化することで，絶対値最小化問題と等価な LP で表現できることを説明する． このためにまず 自由変数の非負変数への分解 のテクニックを用いて，非線形な絶対値関数を線形に書き換える．
(4.11)#\[\begin{split}x[j] &= x^+[j] - x^-[j], \\
x^{\pm}[j] &\geq 0, \\
x^+[j]\cdot x^-[j] &= 0, \\
|x[j]| &= x^+[j] + x^-[j]\end{split}\]
\(|x[j]|\) が \(2\) つの非負変数の和として，線形な定式化に帰着できている． ここで \(x^+[j]\cdot x^-[j] = 0\) は非線形な制約であるため， これも線形な定式化に帰着させなければならない． その方法は 自由変数の非負変数への分解 にあるとおり， \(x^+[j]\cdot x^-[j] = 0\) に等価な線形な制約条件を書くか， 目的関数で配慮させる二つの方法がある．
本問題では \(c[j]\) が非負であるという仮定から， 目的関数によって解決できる．
以上から絶対値最小化問題は次の LP に帰着させることができる．
(4.12)#\[\begin{split}& \mathrm{Minimize:}~ \sum_{j\in J} c[j]\cdot (x^+[j] + x^-[j]) \\
& \mathrm{subject~to:}~ \\
& \sum_{j\in J} a[i,j]\cdot (x^+[j] - x^-[j]) = b[j],~ \forall i\in I, \\
& x^{\pm}[j] \geq 0,~ \forall j\in J\end{split}\]