最大kノルムの双対表現

$$\underset{c\in \mathbb{R}}{min}\{kc+\sum _{i=1}^{n}max\{|x_i|-c,0\}\}$$

$max$を線形不等式で分解すれば

$$\begin{array}{rl}\underset{z,c}{min}& kc+1^{T}z\\ \text{s.t.}& z\ge |x|-c1\\ & z\ge 0\end{array}$$

線形計画の標準形に変形すれば

$$\begin{array}{rl}\underset{z,c}{max}& -(1^T,k)\left(\begin{array}{c}z\\ c\end{array}\right)\\ \text{s.t.}& -\left(\begin{array}{cc}I& 1\\ I& 0\end{array}\right)\left(\begin{array}{c}z\\ c\end{array}\right)\le -\left(\begin{array}{c}|x|\\ 0\end{array}\right)\end{array}$$

定理1より

$$\begin{array}{rl}\underset{q}{min}& -{\left(\begin{array}{c}|x|\\ 0\end{array}\right)}^{T}q\\ \text{s.t.}& -\left(\begin{array}{cc}{I}^T& I^T\\ 1^T& 0^T\end{array}\right)q=-\left(\begin{array}{c}1\\ k\end{array}\right)\\ & q\ge 0\end{array}$$

単位行列$I$の転置$I^T=I$であるので,

$$\begin{array}{rl}\underset{q}{max}& {\left(\begin{array}{c}|x|\\ 0\end{array}\right)}^{T}q\\ \text{s.t.}& -\left(\begin{array}{cc}I& I\\ 1^T& 0^T\end{array}\right)q=-\left(\begin{array}{c}1\\ k\end{array}\right)\\ & q\ge 0\end{array}$$

要素ごとに展開すれば,
$$\begin{array}{rl}\underset{q}{max}& |x_1|q_1+|x_2|q_2+\cdots +|x_n|q_n\\ \text{s.t.}& q_1+q_2+\cdots +q_n=k\\ & q_1+q_{n+1}=1\\ & ⋮\\ & q_n+q_{n+n}=1\\ & q\ge 0\end{array}$$

$q_i\le 1$であることがわかったので、

$$\begin{array}{rl}\underset{q}{max}& |x_1|q_1+|x_2|q_2+\cdots +|x_n|q_n\\ \text{s.t.}& q_1+q_2+\cdots +q_n=k\\ & 0\le q\le 1\end{array}$$

貪欲法の要領で床関数$\lfloor \ast \rfloor$を用いて変形すれば、
$$|x_{(1)}|+|x_{(2)}|+\cdots +|x_{(\lfloor k\rfloor )}|+(k-\lfloor k\rfloor )|x_{(\lfloor k\rfloor +1)}|$$

最大kノルムに一致することがわかった。