## 4 Convex Minimization Problem
We note that  
\[\sup_{\mathbf{x}}\left\{\left(B^{T}\boldsymbol{\lambda}\right)^{T}\left( \mathbf{x}-\mathbf{w}\right)-F\left(\mathbf{x}-\mathbf{w}\right)\right\}=F^{* }\left(B^{T}\boldsymbol{\lambda}\right)\]  
hence to compute  
\[\sup_{\boldsymbol{\lambda}}\left[\inf_{\mathbf{x}}\left\{F\left(\mathbf{x}- \mathbf{w}\right)-\boldsymbol{\lambda}^{T}\left(B\mathbf{x}-\mathbf{z}\right) \right\}\right]\]  
one has to deal with  
\[\sup_{\boldsymbol{\lambda}}\left[\boldsymbol{\lambda}^{T}\left(\mathbf{z}-B \mathbf{w}\right)-F^{*}\left(B^{T}\boldsymbol{\lambda}\right)\right]\]  
For many functions \(g\) the conjugate \(g^{*}\) can be easily computed. Next we list conjugate functions for the most popular norms  
1. \(\|\mathbf{u}\|_{\infty}=\max_{i}|u_{i}|\)
2. \(\|\mathbf{u}\|_{2}=\left(\sum_{i=1}^{d}u_{i}^{2}\right)^{\frac{1}{2}}\)
3. \(\|\mathbf{u}\|_{1}=\sum_{i=1}^{d}|u_{i}|\) \begin{tabular}{|c|c c|} \hline \(g(\mathbf{u})\) & \multicolumn{2}{c|}{conjugate \(g^{*}(\mathbf{y})\)} \\ \hline \(\|\mathbf{u}\|_{\infty}\) & \(+\infty\) & if \(\|\mathbf{y}\|_{1}>1\) \\  & \(0\) & if \(\|\mathbf{y}\|_{1}\leq 1\) \\ \hline \(\|\mathbf{u}\|_{2}\) & \(+\infty\) & if \(\|\mathbf{y}\|_{2}>1\) \\  & \(0\) & if \(\|\mathbf{y}\|_{2}\leq 1\) \\ \hline \(\|\mathbf{u}\|_{1}\) & \(+\infty\) & if \(\|\mathbf{y}\|_{\infty}>1\) \\  & \(0\) & if \(\|\mathbf{y}\|_{\infty}\leq 1\) \\ \hline \end{tabular}  We note that some of the functions \(F\) we consider in this paper are different from \(l_{p}\) norms (see Table 1 for the list of the functions). We first select \(F(\mathbf{x})=\|\mathbf{x}\|_{\infty}\), and show below that in this case  
\[r(\mathbf{z})=\sup_{\boldsymbol{\lambda}}\left[\boldsymbol{\lambda}^{T}\left( \mathbf{z}-B\mathbf{w}\right)-F^{*}\left(B^{T}\boldsymbol{\lambda}\right) \right]=\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{\infty}\]Note that with the choice \(F(\mathbf{x})=\left\|\mathbf{x}\right\|_{\infty}\) the problem \(\sup\limits_{\boldsymbol{\lambda}}\left[\boldsymbol{\lambda}^{T}\left(\mathbf{z} -B\mathbf{w}\right)-F^{*}\left(B^{T}\boldsymbol{\lambda}\right)\right]\) becomes  
\[\sup\limits_{\boldsymbol{\lambda}}\left.\boldsymbol{\lambda}^{T}\left(\mathbf{z }-B\mathbf{w}\right)\text{ subject to }\left|\left|B^{T}\boldsymbol{\lambda}\right| \right|_{1}\leq 1\]  
Since \(\left|\left|B^{T}\boldsymbol{\lambda}\right|\right|_{1}=\left|\left|\boldsymbol{ \lambda}\right|\right|_{1}\) the problem reduces to  
\[\sup\limits_{\boldsymbol{\lambda}}\left.\boldsymbol{\lambda}^{T}\left(\mathbf{z }-B\mathbf{w}\right)\text{ subject to }\left|\left|\boldsymbol{\lambda}\right| \right|_{1}\leq 1\]  
The solution to this maximization problem is \(\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{\infty}\). Analogously, when  
\[\mathbf{x}^{T}=\left(\mathbf{x}_{1}^{T},\ldots,\mathbf{x}_{n}^{T}\right),\; \mathbf{y}^{T}=\left(\mathbf{y}_{1}^{T},\ldots,\mathbf{y}_{n}^{T}\right)\in \mathbf{R}^{nd},\text{ and }F(\mathbf{x})=\max\limits_{i}\{\left\|\mathbf{x}_{i} \right\|_{2}\}\]  
one has \(F^{*}(\mathbf{y})=\sup\limits_{\mathbf{x}}\left(\sum\limits_{i=1}^{n}\mathbf{ y}_{i}^{T}\mathbf{x}_{i}-\max\limits_{i}\{\left\|\mathbf{x}_{i}\right\|_{2}\}\right)\) Assuming \(\max\limits_{i}\{\left\|\mathbf{x}_{i}\right\|_{2}\}=1\) one has to look at  
\[\sup\limits_{\{\mathbf{x}\,:\,\left\|\mathbf{x}_{i}\right\|_{2}\leq 1\}}\sum \limits_{i=1}^{n}\mathbf{y}_{i}^{T}\mathbf{x}_{i}-1=\sum\limits_{i=1}^{n} \left\|\mathbf{y}_{i}\right\|_{2}-1\]  
Hence  
\[F^{*}(\mathbf{y})=\left\{ \begin{array}{ll}+\infty&\text{if }\;\sum\limits_{i=1}^{n}\left\| \mathbf{y}_{i}\right\|_{2}>1\\ \\ 0&\text{if }\;\sum\limits_{i=1}^{n}\left\|\mathbf{y}_{i}\right\|_{2}\leq 1 \end{array} \right.\]  
and \(\left|\left|B^{T}\boldsymbol{\lambda}\right|\right|_{2}=\dfrac{1}{n}n\| \boldsymbol{\lambda}\|_{2}=\|\boldsymbol{\lambda}\|_{2}\). Finally the value for \(r(\mathbf{z})\) is given by \(\left|\left|\mathbf{z}-B\mathbf{w}\right|\right|_{2}\).