最大kノルムの双対表現
最大kノルム$|\!|\!|x|\!|\!|_{k}$とは
$\left(x_1,x_2,\cdots,x_n\right)$の要素の絶対値を降順で並べ替えたものを$\left(x_{(1)},x_{(2)},\cdots,x_{(n)}\right)$とする。つまり、$|x_{(1)}|\geq|x_{(2)}|\geq\cdots\geq|x_{(n)}|$である。
設計者が$k\in\{1,2,\cdots,n\}$で定めた時、最大kノルムが定まる。
$$ |\!|\!|x|\!|\!|_k:=|x_{(1)}|+|x_{(2)}|+\cdots+|x_{(k)}| $$
最大kノルム$|\!|\!|x|\!|\!|_{k}$の双対表現
線形計画の主問題と双対問題は同値である。
線形計画の主問題
\begin{aligned}
\min_{x} \quad & c^Tx\\
\textrm{s.t.} \quad & Ax= b\\
&x\geq 0
\end{aligned}
線形計画の双対問題
\begin{aligned}
\min_{y} \quad & b^Ty\\
\textrm{s.t.} \quad & A^Ty\leq c
\end{aligned}
最大kノルム$|\!|\!|x|\!|\!|_{k}$の双対表現は下式で表される。
$$ |\!|\!|x|\!|\!|_k:=\min_{c\in\mathbb{R}}\{kc+\sum_{i=1}^{n}\max\{|x_i|-c,0\}\} $$
$$ \min_{c\in\mathbb{R}}\{kc+\sum_{i=1}^{n}\max\{|x_i|-c,0\}\}\\ $$
$\max$を線形不等式で分解すれば
\begin{aligned} \min_{z,c} \quad & kc+1^Tz\\ \textrm{s.t.} \quad & z\geq|x|-c1\\ &z\geq0 \\ \end{aligned}
線形計画の標準形に変形すれば
\begin{aligned} \max_{z,c} \quad & -(1^T,k) \begin{pmatrix} z \\ c \end{pmatrix}\\ \textrm{s.t.} \quad & -\begin{pmatrix} I & 1 \\ I & 0 \end{pmatrix} \begin{pmatrix} z \\ c \end{pmatrix} \leq -\begin{pmatrix} |x| \\ 0 \end{pmatrix}\\ \end{aligned}
定理1より
\begin{aligned} \min_{q} \quad & -\begin{pmatrix} |x| \\ 0 \end{pmatrix}^T q\\ \textrm{s.t.} \quad & -\begin{pmatrix} I^T & I^T \\ 1^T & 0^T \end{pmatrix} q = -\begin{pmatrix} 1 \\ k \end{pmatrix}\\ &q\geq 0 \end{aligned}
単位行列$I$の転置$I^T=I$であるので,
\begin{aligned} \max_{q} \quad & \begin{pmatrix} |x| \\ 0 \end{pmatrix}^T q\\ \textrm{s.t.} \quad & -\begin{pmatrix} I & I \\ 1^T & 0^T \end{pmatrix} q = -\begin{pmatrix} 1 \\ k \end{pmatrix}\\ &q\geq 0 \end{aligned}
要素ごとに展開すれば,
\begin{aligned}
\max_{q} \quad & |x_1|q_1+|x_2|q_2+\cdots+|x_n|q_n\\
\textrm{s.t.} \quad
& q_1+q_2+\cdots+q_n=k\\
& q_1+q_{n+1}=1\\
&\vdots\\
& q_n+q_{n+n}=1\\
&q\geq 0
\end{aligned}
$q_i\leq 1$であることがわかったので、
\begin{aligned} \max_{q} \quad & |x_1|q_1+|x_2|q_2+\cdots+|x_n|q_n\\ \textrm{s.t.} \quad & q_1+q_2+\cdots+q_n=k\\ &0\leq q\leq 1 \end{aligned}
貪欲法の要領で床関数$\lfloor*\rfloor$を用いて変形すれば、
$$
|x_{(1)}|+|x_{(2)}|+\cdots+|x_{(\lfloor k\rfloor)}|
+\left(k-\lfloor k\rfloor\right)|x_{(\lfloor k\rfloor + 1)}|
$$
最大kノルムに一致することがわかった。