Book: Convex Optimization (Author: Stephen Boyd), Appendix A, Topic: A.1.2 Norm,distance, and unit ball

Can anyone please help me in understanding the following definition of "norm"

$$ \| x \| =(\sup\{ t \geq0 \mid tx \in C\})^{-1}$$

where $C\subseteq R^n$ and satisfies these three properties 1) $C$ is symmetric. 2) $C$ is convex. 3) $C$ is closed,bounded, and has non empty interior.

I am familiar with $\parallel x \parallel_{p}$ norm definition but I have not been able to establish the equivalence between the two definitions.

  • $\begingroup$ The $\lVert\,\cdot\,\rVert_p$ norms are special cases. The definition is such that for every $x$, $\lVert x\rVert$ is the factor by which $C$ must be scaled so that $x$ is on the boundary of the scaled set $\lVert x\rVert\cdot C$. It would probably have been better to indicate the dependence on $C$, e.g. by writing $\lVert x\rVert_C$. That is also known as the Minkowski functional of $C$, googling "Minkowski functional" may turn up enlightening links. $\endgroup$ – Daniel Fischer Jan 10 '15 at 23:52
  • $\begingroup$ Could you please clarify your question? Any function $p$ defined in $R^n$ that satisfies: i) $p(a\cdot x)=|a|\cdot p(x)$ for any $a$ scalar; ii) $p(x+y)\le p(x)+p(y)$; and iii) $p(x)=0$ iff $x=0$; is what we call a norm. $\endgroup$ – Sergio Parreiras Jan 10 '15 at 23:52
  • $\begingroup$ Why do "expert people" find questions like this so bad that they vote negatively. I had tagged it under "self learning". This is like very unfair. I asked for someone to help me understand a definition from a well referenced text book…is it a crime. I am sorry, I couldn't come up with a challenging question that could give you a chance to show off your expertise $\endgroup$ – NAASI Jan 11 '15 at 0:14
  • $\begingroup$ @ Daniel. Thank you for giving some clue. $\endgroup$ – NAASI Jan 11 '15 at 0:15
  • 1
    $\begingroup$ Ignore the votes. $\endgroup$ – copper.hat Jan 11 '15 at 0:24

An equivalent definition is $\|x\|_C = \inf \{ t>0 | {x \over t } \in C \}$. This is a little more convenient here.

Let $C = \bar{B}(0,1)$, with the $\|\cdot\|_p$ norm.

If $\|x\|_p \le t$, then ${x \over t} \in C$, and so $\|x\|_C \le t$.

If $\|x\|_p > t$, then for some $\epsilon>0$ we have $\|x\|_p > t+\epsilon$. Then $\|{x \over s} \|_p >1$ for all $0<s \le t+\epsilon$ and so ${x \over s} \notin C$ for all $0<s \le t+\epsilon$, and so $\|x\|_C \ge t+\epsilon > t$.

Hence $\|x\|_p = \|x\|_C$.

Note: The above argument works for any norm $\|\cdot\|_*$ (not just the $\|\cdot\|_p$ norm) and shows that we have $\|\cdot\|_* = \|\cdot\|_{\{x | \|x\|_*\le 1\}}$.

To address Michael's comment:

First, note that on $\mathbb{R}^n$, all norms are equivalent. Hence requiring $C$ to have some topological aspects (boundedness and non empty interior) are not as circular as they might appear at first.

If $\|\cdot\|$ is any norm, let $C = \{x | \|x\| \le 1 \}$. Then the above argument shows that $\|\cdot\| = \|\cdot\|_C$. If $x \in C$, then since $\|-x\| = \|x\|$, we have $-x \in C$ and so $C$ is symmetric. Since $x \mapsto \|x\|$ is convex, it follows that $C$ is convex. $C$ is obviously bounded, and since $\{ x | \|x\|<1 \} \subset C$, we see that $C$ has a non empty interior.

Now suppose that $C$ is convex, balanced, bounded and has a non empty interior. Note that these conditions imply that $0$ is in the interior of $C$.

Let $n(x) = \inf \{ t>0 | {x \over t } \in C \}$. We want to show that $n$ is a norm. Since ${0 \over t} \in C$ for all $t >0$, we see that $n(0) = 0$. Now suppose $x \neq 0$. Since $C$ is bounded, there is some $s >0$ such that $x \notin t C$ for all $t \le s$, and so $n(x) \ge s >0$. Since $0 \in C^\circ$, we see that there is some $t>0$ such that ${x \over t} \in C$, and so $n(x) < \infty$, hence it takes values in $(0,\infty)$.

If $\lambda \ge 0$, we see that $\{ t>0 | {\lambda x \over t } \in C \} = \lambda \{ t>0 | {x \over t } \in C \}$, and since $C$ is balanced, we have $\{ t>0 | {x \over t } \in C \} = \{ t>0 | {-x \over t } \in C \}$, from which we get $\{ t>0 | {\lambda x \over t } \in C \} = |\lambda| \{ t>0 | {x \over t } \in C \}$, and so $n(\lambda x) = |\lambda| n(x)$.

Finally, suppose ${x \over \alpha} \in C$ and ${y \over \beta} \in C$ for some $\alpha,\beta >0$, then since $C$ is convex, we have ${\alpha \over \alpha + \beta} {x \over \alpha} + {\beta \over \alpha + \beta} {y \over \beta} = {x+y \over \alpha + \beta} \in C$. Consequently, we have $n(x+y) \le \alpha+\beta$, and taking the $\inf$ over the appropriate $\alpha,\beta$ gives $n(x+y) \le n(x)+n(y)$, and so $n$ is subadditive.

Hence $n$ is a norm.

  • $\begingroup$ This is good, but of course $C$ does not need to be a norm ball. (Well, it is once you define a norm with it! But that is self-referential.) $\endgroup$ – Michael Grant Jan 11 '15 at 23:21
  • 1
    $\begingroup$ @MichaelGrant: The question is a wee bit ambiguous, so I interpreted it as showing the equivalence between the $\|\cdot\|_p$ norm and the gauge-based definition. (Of course, I neglected to show that the $C$ above is symmetric, bounded and absorbing...) $\endgroup$ – copper.hat Jan 11 '15 at 23:48
  • $\begingroup$ @MichaelGrant: I added a lot more detail... $\endgroup$ – copper.hat Jan 12 '15 at 6:40
  • $\begingroup$ Great! Too bad I can't vote twice! ;-) $\endgroup$ – Michael Grant Jan 12 '15 at 12:37

For any norm (with respect to the definiton you are familiar with) $\Vert \cdot \Vert$ look at $C= \{ x \in \mathbb R : \Vert x \Vert \le 1 \}$

This set satisfies the 3 conditions and if you define a norm using the "new" definition and this $C$, the result is the norm you started with.

Hope this helps

  • $\begingroup$ As I commented with copper.hat, this is self-referential. What if C is not the ball of a previously-defined norm? $\endgroup$ – Michael Grant Jan 11 '15 at 23:23
  • $\begingroup$ This answer is supposed to show the connection between both definitions of a norm... $\endgroup$ – GenericNickname Jan 12 '15 at 7:16

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.