3. ノルム最小化問題#
3.1. 説明#
最適化問題で代表的なノルムの定義を挙げる． 記述のために \(m\) 次元ベクトルを \(\mathbf{z}\) とする．
(3.20)#\[\begin{split}\mathbf{z} :=
\begin{bmatrix}
z[1] \\
z[2] \\
\vdots \\
z[m]
\end{bmatrix}\end{split}\]
\(\mathbf{z}\) に対してそれぞれノルムは次で与えられる．
\(1\)-ノルム
(3.21)#\[\|\mathbf{z}\|_1 := \sum_{i=1}^m |z[i]|\]
\(2\)-ノルム
(3.22)#\[\|\mathbf{z}\|_2 := \left(\sum_{i=1}^m z[i]^2 \right)^{\frac{1}{2}}\]
\(\infty\)-ノルム
(3.23)#\[\|\mathbf{z}\|_{\infty} := \max_{1\leq i\leq m} |z[i]|\]
ここで \(1\)-ノルム，\(\infty\)-ノルムの最小化は LP で定式化可能だが， 一方で \(2\)-ノルムに関しては LP で表現できない．
3.1.1. LP による定式化 (\(1\)-ノルム最小化問題)#
\(1\)-ノルムの最小化問題とは \(1\)-ノルムを最小化する最適化問題であり 絶対値最小化問題 でもある．
(3.24)#\[\mathrm{Minimize:}~ \sum_{i=1}^m |z[i]|\]
よってこれを LP として，表現する方法は 絶対値最小化問題 と同じであり， 以下のように定式化できる．
(3.25)#\[\begin{split}& \mathrm{Minimize:}~ \sum_{i=1}^m (v^+[i] + v^-[i]) \\
& \mathrm{subject~to:}~ \\
& 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.1.2. LPによる定式化 (\(\infty\)-ノルム最小化問題)#
\(\infty\)-ノルムの最小化問題とは \(\infty\)-ノルムを最小化する最適化問題であり 最大値最小化問題 でもある．
(3.26)#\[\mathrm{Minimize:}~ \|\mathbf{z}\|_{\infty} = \max_{1\leq i\leq m} |z[i]|\]
よってこれを LP として，表現する方法は \(\mathrm{max}\) 関数の対象が絶対値であることを除いて 最大値最小化問題 と同じであり， 以下のように定式化できる．
(3.27)#\[\begin{split}& \mathrm{Minimize:}~ q \\
& \mathrm{subject~to:}~ \\
& 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]\) とは次で関係付いている．
(3.28)#\[v^+[i] - v^-[i] = z[i],~ \forall i\in \{1,\ldots,m\}\]