How to compute the convex conjugate of norm raised to the power of $2$, $f(x) = \|x\|^2/2$

Question

How would one find the conjugate of the following : $$f(x) = \|x\|^2 /2$$ The conjugate function is defined as $ f^*(y) = \max_x y^Tx - f(x)$

I am stuck at how I can derive the explicit form for $x$.

So far, here are my steps:

To maximize I take the derivative and set to $0$.

$$f'(x) = y - \partial\|x\| \cdot \|x\| = 0$$

$$\partial\|x\| = y/\|x\| $$

Edit : $\|x\|$ is any norm here. Not just the 2-norm.

Where do I go from here?

Answer 1

This problem can be solved by completing the squares.

$$f^{∗}(y)=\max_x y^Tx−f(x)$$ $$f^{∗}(y)=\max_x ( y^Tx−||x||^2/2)$$ $$f^{∗}(y)=\max_x (y^Tx−||x||^2/2 - ||y||_{*}^2/2 + ||y||_{*}^2/2)$$ $$f^{∗}(y)\leq\max_x (||y||_{*}^2/2 - (||x||-||y||_{*})^2/2)$$ trivially, $f^{∗}(y)= ||y||_{*}^2/2$.

Answer 2

Edit: I transcribed a proof from Example 3.27 (pp. 93-94) of Boyd and Vandenberghe here.

---

Here is a proof in the special case that $\| \cdot \|$ is the $\ell_2$-norm.

Note that $\nabla f(x) = x$. When you set the gradient equal to $0$, you get $y - x = 0$, or $x = y$. Thus $f^*(y) = y^T y - \|y\|^2/2 = \|y\|^2/2$.