Legendre transform of a norm Let $||\cdot||$ be a norm on $\mathbb{R}^n$, with dual norm $||x||_* :=\max_\limits{y:||y||\leq 1}y^T x$.  I'd like to show $$\max_{x \in \mathbb{R}^n}(x^T d-||x||)=\begin{cases}
0 & \text{ if } ||d||_* \leq 1 \\ 
\infty & \text{ otherwise }  
\end{cases}$$
(the Legendre transform of a norm is the characteristic function of the unit ball (wrt the dual norm)  
I'm lost because I don't know how to take the gradient of the objective (and I think $||\cdot||$ is non differentiable anyway).  I know that the dual of the dual norm is the original norm: $||\cdot||_{**} \equiv ||\cdot||$
 A: Using the fact that $\|x\| \equiv \underset{y \in \mathbb{R}^n,\|y\|_* \le 1}{\sup }x^Ty$, you immediately get
\begin{equation}
\begin{split}
\underset{x \in \mathbb{R}^n}{\text{sup }}x^Td - \|x\| &= \underset{x \in \mathbb{R}^n}{\sup}x^Td - \underset{y \in \mathbb{R}^n,\|y\|_* \le 1}{\sup }x^Ty = \underset{y \in \mathbb{R}^n, \|y\|_* \le 1}{\inf }\underset{x\in \mathbb{R}^n}{\sup}x^T(d - y) \\
&= \underset{y \in \mathbb{R}^n, \|y\|_* \le 1}{\inf }\begin{cases}0,&\mbox { if }y = d,\\+\infty, &\mbox{ otherwise}\end{cases}\\
&= \begin{cases}0,&\mbox { if }\|d\|_* \le 1,\\+\infty, &\mbox{ otherwise,}\end{cases}
\end{split}
\end{equation}
where the second equality follows from Sion's minimax theorem (as an easy exercise, the reader should check that the hypotheses of the Theorem are satisfied).
A: Case 1: $\|d\|_*\le 1$.
You know that $\|x\|=\|x\|_{**}=\max_{\|y\|_*\le 1}x^Ty\ge x^Td$, then 


*

*$x^Td-\|x\|\le 0$, $\forall x\in\mathbb{R}^n$,

*$x^Td-\|x\|=0$ at $x=0$.


Therefore, $\max=0$.
Case 2: otherwise, i.e. $\|d\|_*>1$.
Let us split $x=\|x\|\cdot\frac{x}{\|x\|}=\|x\|\cdot x_0$. So 
$x^Td-\|x\|=\|x\|\cdot(x_0^Td-1)$. Maximizing w.r.t. the unit direction $x_0$ first with fixed $\|x\|$ gives
$$
\max_{\|x_0\|=1}\|x\|\cdot(x_0^Td-1)=\|x\|\cdot\max_{\|x_0\|=1}(x_0^Td-1)=\|x\|\cdot\underbrace{(\|d\|_*-1)}_{>0}.
$$
Now maximizing w.r.t. the length $\|x\|$ gives clearly $+\infty$.
P.S. You can apply the splitting in Case 2 to Case 1 too. Then $\|d\|_*-1\le 0$ and the maximum w.r.t. $\|x\|$ is zero.
