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\)-ノルム
(2)#\[\|\vec{z}\|_1 := \sum_{i=1}^m |z[i]|\]
\(2\)-ノルム
(3)#\[\|\vec{z}\|_2 := \left(\sum_{i=1}^m z[i]^2 \right)^{\frac{1}{2}}\]
\(\infty\)-ノルム
(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\}\]
関連
引用書式