Legendre transform of a norm

Solution 1:

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

Solution 2:

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.