Fenchel Conjugate of $\ell_p^p$ What is the Fenchel Conjugate of $f(x) = \| x\|_p^p$, where $x\in \mathbb{R}^n$?
It is known that the conjugate of $f(x)=\frac{1}{p}|x|^p$ is $f^*(x) = \frac{1}{q}|x|^q$. Does that extend to the $p$-norm?
 A: I believe that it extends to p-norms in that the Fenchel conjugate of $\frac{1}{p}\| x\|_p^p$ is $\frac{1}{q}\| x\|_q^q$ where $q=\frac{p}{p-1}$.
Here's a proof for the more general question of showing that the convex conjugate of $f(x) = \frac{1}{p} \| x\|^p$ for any norm is $f^*(y) = \frac{1}{q} \| y\|_*^q$ (note that the dual norm of $\| \cdot\|_p$ is $\| \cdot\|_q$ which then gives your desired result). The proof follows closely the one given in Example 3.27 (pp. 93-94) of Boyd and Vandenberghe, which is for any norm squared $\frac{1}{2}\| \cdot\|^2$.
Note that due to Holder's inequality we have $y^T x \leq \| y \|_* \|x\|$ and so
\begin{equation}
f^*(y) := \sup_{x} y^T x - \frac{1}{p} \| x\|^p \leq \sup_{\|x\|} \| y \|_* \| x \| - \frac{1}{p} \| x\|^p
\end{equation}
Let's compute the maxima of the right-hand side by setting the derivative wrt | x | to 0.
\begin{align}
 (\| y \|_* \| x \| - \frac{1}{p} \| x\|^p)'&=0 \\
 \| y \|_*  -   \| x\|^{p-1} &=0 \\
 \| x\| &= \| y \|_*^{\frac{1}{p-1}} 
\end{align}
and so
\begin{equation}
f^*(y) \leq  \| y \|_*^{\frac{p}{p-1}} - \frac{1}{p} \| y \|_*^{\frac{p}{p-1}} =  \frac{1}{q} \| y \|_*^{q} 
\end{equation}
Note that his can always be achieved by letting $x$ be any vector with $y^T x = \|y\|_* \|x\|$, scaled so that $\|x\| = \| y \|_*^{\frac{1}{p-1}}$ which concludes the proof.
