1
$\begingroup$

This question already has an answer here:

I just noticed somewhere in Convex Optimization that the dual cone of $l^1$ is $l^\infty$! (A diamond in $\mathbb{R}^2$ for $l^1$ is a square in $\mathbb{R}^2$ for $l^\infty$.) In fact I cannot imagine that. Can you please explain it geometrically by the definition of the dual cone? [Ref. Convex Optimization book, Stephen Boyd]

$K = \{(x,t): \Vert x\Vert_1 \le t\} \Rightarrow K^* = \{(x,t): \Vert x\Vert_\infty \le t\}$

Definition:
$K$ is a cone, then the dual cone is : $K^* = \{y: x^T y \geq 0 \ \text{for all} \ x \in K\}$

I would be glad if you have any comment about that. For simplicity you can discuss about that in $\mathbb{R}^2$.

$\endgroup$

marked as duplicate by Community Oct 13 '16 at 23:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

The key is the dual relationship $\|x\|_\infty = \max_{\|z\|_1 \le 1} z^T x$.

Note \begin{eqnarray} K^* &=& \{ (y,s) | x^T y + st \ge 0 \text{ for all } (x,t) \in K \} \\ &=& \{ (y,s) | -x^T y + s \ge 0 \text{ for all } (-x,1) \in K \}\\ &=& \{ (y,s) | x^T y \le s \text{ for all } \|x\|_1 \le 1 \}\\ &=& \{ (y,s) | \max_{\|x\|_1 \le 1 }x^T y \le s \}\\ &=& \{ (y,s) | \|y\|_\infty \le s \}\\ \end{eqnarray}

$\endgroup$
  • $\begingroup$ @AminJaili: Thanks for catching the typo. I added a line elaborating the last result, it follows from the dual relationship on the first line. $\endgroup$ – copper.hat Jun 12 '16 at 14:39
  • $\begingroup$ Also, could you have any geometric interpretation about the dual of a cone in this case in two dimensional space? I mean, how we get an square from a diamond!? $\endgroup$ – Amin Jun 12 '16 at 14:46
  • 1
    $\begingroup$ @copper.hat, Nice explanation! $\endgroup$ – ZFR Jun 12 '16 at 14:48
  • $\begingroup$ @AminJaili: If you mean $K \subset \mathbb{R}^2$ then since $\|x\|_1 = \|x\|_\infty = |x|$, we see that $K=K^*$. I think it is easier to first look for geometric inspiration in the context of the unit balls in $l_1, l_\infty$ rather than the cones. The geometric intuition is that a convex compact set can be described as a collection of points or the intersection of all half planes containing the set. This is the essence of duality. $\endgroup$ – copper.hat Jun 12 '16 at 15:06
  • $\begingroup$ @AminJaili: No, you are confusing the cones with the unit balls. If $K \subset \mathbb{R}^2$, then it is defined by $\{(x,t)| |x| \le t \}$ which doesn't distinguish between $l_1, l_\infty$ norms (since they are the same on $\mathbb{R}$). Convince yourself of the duality of the unit balls first before looking at cone duality. In some sense they are the same thing, but you need to develop intuition first. $\endgroup$ – copper.hat Jun 12 '16 at 15:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.