I want to show that the Fenchel conjugate of a norm is the indicator function on the unit ball of the dual norm.
The Fenchel conjugate is defined for a function $f$ as,
$$f^*(y) = \sup\limits_{x} \langle y, x\rangle -f(x),$$
the dual norm $\|\cdot\|_*$ of a norm $\|\cdot\|$ is defined as,
$$\|z\|_* = \sup\limits_{\|u\|\leq 1}\langle z, u\rangle,$$
and the indicator function of a set $C$, denoted $i_C$, is defined as,
$$i_C(x) = \begin{cases} 0 & x\in C,\\ +\infty & x\not\in C\end{cases}.$$
Then the problem is to show that $\|x\|^* = i_{\|x\|_*\leq 1}(x)=\begin{cases} 0 & \|x\|_*\leq 1\\ +\infty & \|x\|_*>1\end{cases}.$
First we consider $x$ with $\|x\|_*>1$. Then, by definition of the dual norm, we have,
$$\sup\limits_{\|y\|\leq 1}\langle y,x\rangle>1.$$
So, $\exists y:\|y\|\leq 1$ such that $\langle y,x\rangle >1$, i.e. $\langle y,x\rangle – \|y\| > 0$. If we choose $z=ty$ then we have,
$$\langle z, x\rangle – \|z\| = t(\langle y,x\rangle -\|y\|)$$
and now letting $t\to\infty$ shows that $\langle z, x\rangle – \|z\|$ is unbounded, i.e. $\|x\|^* = \infty$ for $\|x\|_*>1$.
Now, I am stuck on the remaining case. For this, we consider $x$ with $\|x\|_*\leq 1$. In the book I am reading, the next claim in the proof is,
$$\langle x,y\rangle\leq \|y\|\|x\|_*,\quad\forall y$$
how do they arrive at this claim?
Best Answer
The claim that $\langle x,y\rangle\leq \|y\|\|x\|_*$ holds for all $x$ and $y$ is proved as follows: Fix $x$. If $y=0$ the result is trivial. If $y\neq0$, then $\left\|\frac{y}{\|y\|}\right\|=1\leq1$, so that $\langle x,\frac{y}{\|y\|}\rangle \leq\sup_{\|y\|\leq1}\langle x,y\rangle=\|x\|_*$. Multiplying by $\|y\|$ yields the claim.