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$
  • 1
    $\begingroup$ Your argument is correct. Why do you think it's not? $\endgroup$ – Omar Antolín-Camarena May 11 '16 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$ – Mike Wojnowicz May 11 '16 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$ – Omar Antolín-Camarena May 11 '16 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$ – Michael Grant May 13 '16 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 '17 at 23:03
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$
  • 1
    $\begingroup$ Ugh. Really? But I see the $||x|| \leq 1$ version everywhere. Why the superfluous framing? There must be a reason. $\endgroup$ – Mike Wojnowicz May 11 '16 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 '16 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$ – Daniel Fischer May 11 '16 at 8:40
  • 1
    $\begingroup$ Because using $\leq$ gives you a convex optimization problem. $=$ does not. $\endgroup$ – Michael Grant May 12 '16 at 19:38
4
$\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$
  • $\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$ – Mike Wojnowicz May 11 '16 at 5:24
  • 2
    $\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 '16 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$ – Mike Wojnowicz May 11 '16 at 5:30
  • $\begingroup$ @Royi: What is the relationship of the referenced question to the answer above? $\endgroup$ – copper.hat Sep 5 '17 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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