3. ノルム最小化問題#
3.1. 導入#
最適化問題で代表的なノルムの定義を挙げる． 記述のために \(m\) 次元ベクトルを \(\vec{z}\) とする．
(1)#\[\begin{split}\vec{z} :=
\begin{bmatrix}
z_1 \\
z_2 \\
\vdots \\
z_m
\end{bmatrix}\end{split}\]
\(\vec{z}\) に対してそれぞれノルムは次で与えられる．
\(1\)-ノルム (Manhattan ノルム)
(2)#\[\|\vec{z}\|_1 := \sum_{i=1}^m |z_i|\]
\(2\)-ノルム (Euclid ノルム)
(3)#\[\|\vec{z}\|_2 := \left(\sum_{i=1}^m z_i^2 \right)^{\frac{1}{2}}\]
\(\infty\)-ノルム (Tchebyshev ノルム)
(4)#\[\|\vec{z}\|_{\infty} := \max_{1\leq i\leq m} |z_i|\]
ここで \(1\)-ノルム，\(\infty\)-ノルムの最小化は LP で定式化可能だが， 一方で \(2\)-ノルムに関しては LP で表現できない．
3.2. LP による定式化 (\(1\)-ノルム最小化問題)#
\(1\)-ノルムの最小化問題とは \(1\)-ノルムを最小化する最適化問題であり 絶対値最小化問題 でもある．
(5)#\[\mathrm{Minimize\colon}~ \sum_{i=1}^m |z_i|\]
よってこれを LP として，表現する方法は 絶対値最小化問題 と同じであり， 以下のように定式化できる．
(6)#\[\begin{split}& \mathrm{Minimize\colon}~ \sum_{i=1}^m (v^+_i + v^-_i) \\
& \mathrm{Subject~to\colon}~ \\
& v^+_i - v^-_i = z_i,~ \forall i\in\{1,\ldots,m\}, \\
& v^{\pm}_i \geq 0,~ \forall i\in\{1,\ldots,m\}\end{split}\]
3.3. LPによる定式化 (\(\infty\)-ノルム最小化問題)#
\(\infty\)-ノルムの最小化問題とは \(\infty\)-ノルムを最小化する最適化問題であり 最大値最小化問題 でもある．
(7)#\[\mathrm{Minimize\colon}~ \|\vec{z}\|_{\infty} = \max_{1\leq i\leq m} |z_i|\]
よってこれを LP として，表現する方法は \(\mathrm{max}\) 関数の対象が絶対値であることを除いて 最大値最小化問題 と同じであり， 以下のように定式化できる．
(8)#\[\begin{split}& \mathrm{Minimize\colon}~ q \\
& \mathrm{Subject~to\colon}~ \\
& q \geq v^+_i + v^-_i,~ \forall i\in \{1,\ldots,m\} \\
& v^{\pm}_i \geq 0,~ \forall i\in \{1,\ldots,m\}\end{split}\]
ここで \(\mathrm{max}\) 関数の対象が絶対値であるから， 元の \(z_i\) とは次で関係付いている．
(9)#\[v^+_i - v^-_i = z_i,~ \forall i\in \{1,\ldots,m\}\]
関連
引用書式