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.
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.