6
$\begingroup$

In their book on Convex Optimization, Boyd and Vandenberghe state that given a norm, $||\cdot||$, defined on $\mathbb{R}^n$, the dual norm is defined as $$||z||_*= \sup \{ z^Tx : ||x|| \leq 1 \}$$

In other places, I have encountered an equivalent characterization of the dual norm as $$||z||_*= \sup_{x \neq 0} \displaystyle\frac{z^Tx}{||x||}$$ I don't actually see how these two things are equivalent, even though this is said to be a simple one-liner.

In particular, what's confusing to me is that I would have argued the following, even though this seems to not be correct: By norm homogeneity, the set we're taking the supremum over is invariant to dilations. That is, for any $\alpha >0$, we have $$\displaystyle\frac{z^T(\alpha x)}{||\alpha x||} = \displaystyle\frac{\alpha (z^Tx)}{ |\alpha| ||x||} = \displaystyle\frac{z^Tx}{||x||}$$ and therefore we may find the supremum of the set by merely considering the $x$ values with some constant norm, for example, the unit norm: $$||z||_*= \sup_{x \neq 0} \displaystyle\frac{z^Tx}{||x||} = \sup_{x : ||x||=1} \displaystyle\frac{z^Tx}{||x||} = \sup \{ z^T x : ||x|| = 1\}$$.

Why is this logic incorrect?

$\endgroup$
5
  • 1
    $\begingroup$ Your argument is correct. Why do you think it's not? $\endgroup$ May 11, 2016 at 5:17
  • 1
    $\begingroup$ Because I see the $||x|| \leq 1$ version everywhere (not only in the BV book, but in tutorials by mathematicians all over the internet), and I don't understand why it would be framed that way if the interior of the unit ball was not relevant for finding the supremum. $\endgroup$
    – ashman
    May 11, 2016 at 5:19
  • 4
    $\begingroup$ I bet the reason is simply that $\{x:\left|\right|\le 1\}$ is convex. It's briefer to say "taking the unit ball gives a bijection between norms and centrally symmetric convex bodies" than something like "taking the unit sphere gives a bijection between norms and sets which are the boundary of a centrally symmetric convex body". $\endgroup$ May 11, 2016 at 5:30
  • $\begingroup$ "the interior of the unit ball was not relevant for finding the supremum." As we've all said, convexity is the reason. But I wanted to expand on this particular sentence of yours. How do you know it's not relevant for "finding" the supremum? We know the solution is on the boundary of the ball, yes. But tractable numerical algorithms for finding that solution could very well utilize the interior of the ball, too. So it really is premature to claim that the interior is "not relevant". $\endgroup$ May 13, 2016 at 15:55
  • $\begingroup$ also see Equivalent Definitions of the Operator Norm, since the dual norm can be considered the operator norm of functionals $\endgroup$
    – Yibo Yang
    Sep 9, 2017 at 23:03

2 Answers 2

5
$\begingroup$

Note that if $\|x\| < 1 $ and $z^T x \ge 0$, then $z^T {x \over \|x\|} \ge z^T x$. Hence $\sup \{z^T x : \|x \| \le 1 \} = \sup \{z^T x : \|x \|= 1 \}$.

$\endgroup$
4
  • $\begingroup$ So why is the common framing $\sup \{z^T x : ||x|| \leq 1\} $ and not $\sup \{z^T x : ||x|| = 1\} $? Shouldn't Ockham's razor apply? $\endgroup$
    – ashman
    May 11, 2016 at 5:24
  • 3
    $\begingroup$ It is a matter of taste. It is nicer to deal with convex domains. Not really an Occam's razor sort of thing... $\endgroup$
    – copper.hat
    May 11, 2016 at 5:26
  • $\begingroup$ Okay. Well I could buy that argument, especially for the BV text which is a text on convex optimization. In general though, when I'm learning from a math textbook and encounter an apparently superfluous aspect to a definition, it's usually because I'm overlooking something (and the apparently superfluous piece actually covers some sort of weird edge case I wasn't considering). So I found this confusing. But thanks to you (and everyone) for clearing that up. $\endgroup$
    – ashman
    May 11, 2016 at 5:30
  • $\begingroup$ @Royi: What is the relationship of the referenced question to the answer above? $\endgroup$
    – copper.hat
    Sep 5, 2017 at 20:59
4
$\begingroup$

You're correct. But note that in the BV definition, there is no benefit in taking $\|x\|<1$, so the definition may as well have stipulated that $\|x\|=1$.

$\endgroup$
4
  • 1
    $\begingroup$ Ugh. Really? But I see the $||x|| \leq 1$ version everywhere. Why the superfluous framing? There must be a reason. $\endgroup$
    – ashman
    May 11, 2016 at 5:17
  • 1
    $\begingroup$ I'm not sure, but perhaps one reason is that the BV definition shows that the dual norm is the conjugate of the indicator function of the unit ball for the original norm. Hopefully someone else can shed more light on why the BV definition is seen so often. $\endgroup$
    – littleO
    May 11, 2016 at 5:23
  • 2
    $\begingroup$ @MikeWojnowicz Taking $\lVert x\rVert \leqslant 1$ (or just $\lVert x\rVert < 1$) avoids the problem of $\sup \varnothing$ in the case of looking at the vector space $\{0\}$ you'd run into when considering only $\lVert x\rVert = 1$. That's an edge case of course, but it's nice to have something that also works for edge cases without problem. The constraint $\lVert x\rVert = 1$ also works in that case if one notes that since the sup is taken in $[0,+\infty]$, we have $\sup \varnothing = 0$. But some people dislike $\sup \varnothing$. Also, $\leqslant 1$ is more convenient in some proofs. $\endgroup$ May 11, 2016 at 8:40
  • 1
    $\begingroup$ Because using $\leq$ gives you a convex optimization problem. $=$ does not. $\endgroup$ May 12, 2016 at 19:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .