Let $\| x \|_1 = \sum_{i=1}^n |x_i|$ and $\| x \|_\infty = \max_{i=1}^n |x_i|$ be the $l_1$ and $l_\infty$ norms on $\mathbb{R}^n$.
For any given norm on $\mathbb{R}^n$, the associated dual norm (in the functional analysis sense), denoted $\| \cdot \|_*$ is defined as $\| z \|_* = \sup\{ z^{t} x : \| x \| < 1 \}$.
As shown here, $\left(\| x \|_1\right)_{*} = \| x \|_\infty$ and vice-versa (at least in finite dims).
Can this be proved using linear programming duality? I think so, but how? I see $l_1$ ball has $2n$ vertices and $2^n$ facets whereas $l_\infty$ ball has $2^n$ vertices but $2n$ facets. This suggests connection to linear programming duality. I would like to gain a deeper understanding of this.
Could someone give a reference or a hint on how to do this if not a full solution? I think I'd have use some auxilliary variable tricks to convert absolute values and max operators into linear variables?
Thank you!
One direction: \begin{align} &\sup\{z^\top x: ||x||_\infty \le 1\}\\ &= \max_x \left\{\sum_j z_j x_j: \max_j |x_j| \le 1\right\}\\ &= \max_x \left\{\sum_j z_j x_j: |x_j| \le 1 \ \forall j\right\}\\ &= \max_x \left\{\sum_j z_j x_j: x_j \le 1 \ \forall j, -x_j \le 1 \ \forall j\right\}\\ &= \min_{\alpha,\beta}\left\{\sum_j (\alpha_j + \beta_j): \alpha_j - \beta_j = z_j \ \forall j, \alpha_j \ge 0 \ \forall j, \beta_j \ge 0 \ \forall j\right\}\\ &= \min_{\alpha,\beta}\left\{\sum_j |z_j|\right\}\\ &= \sum_j |z_j| \end{align}
The other direction: \begin{align} &\sup\{z^\top x: ||x||_1 \le 1\}\\ &= \max_x \left\{\sum_j z_j x_j: \sum_j |x_j| \le 1\right\}\\ &= \max_{x,y} \left\{\sum_j z_j x_j: x_j - y_j \le 0\ \forall j, -x_j - y_j \le 0\ \forall j, \sum_j y_j \le 1, y_j \ge 0 \ \forall j\right\}\\ &= \min_{\alpha,\beta,\gamma}\left\{\gamma: \alpha_j - \beta_j = z_j \ \forall j, -\alpha_j - \beta_j + \gamma \ge 0 \ \forall j, \alpha_j \ge 0 \ \forall j, \beta_j \ge 0 \ \forall j, \gamma \ge 0\right\}\\ &= \min_{\alpha,\beta,\gamma}\left\{\gamma: \gamma \ge |z_j| \ \forall j\right\}\\ &= \max_j |z_j| \end{align}