6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I don't think this is so easy to do in general. The conjugate for a norm is known as the dual norm: en.wikipedia.org/wiki/Dual_norm. For the $\ell_p$ norm the dual is the $\ell_q$ norm with $1/p+1/q=1$, for the nuclear norm the dual is the operator norm and so forth. Note that norms are not differentiable at zero, so to do the maximization you need to use the sub-gradient. $\endgroup$ – Peder Nov 24 '13 at 3:35
  • 1
    $\begingroup$ Possible duplicate of Fenchel Conjugate of a norm squared $\endgroup$ – user357151 Apr 9 '18 at 3:11
1
$\begingroup$

For norm, conjugate is indicator of unit ball for dual norm.

See Conjugate Functions at page 7-9:

enter image description here

By Lieven Vandenberghe.

$\endgroup$
3
  • $\begingroup$ Welcome to Math.SE! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 26 '17 at 15:36
  • $\begingroup$ Image - i.imgur.com/d0vc1B7.png. $\endgroup$ – Royi May 21 '17 at 4:04
  • 2
    $\begingroup$ This doesn't answer the question, because the question asks for the conjugate of $\|x\|^2$, not $\|x\|$. $\endgroup$ – littleO May 21 '17 at 4:51
1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ In my question $\|x\|$ is not necessary the 2-norm. It is any arbitrary norm. That's why I was having trouble. $\endgroup$ – Ireth Nov 23 '13 at 22:03
  • $\begingroup$ hmm, do you know that there is a closed form expression for the conjugate in that case? $\endgroup$ – littleO Nov 23 '13 at 22:32
  • $\begingroup$ For the conjugate of only $\|x\|$, there is a closed form expression. Doesn't the square on the norm change things (if you look at my gradient). $\endgroup$ – Ireth Nov 23 '13 at 22:53
  • $\begingroup$ Yes, I agree the square on the norm changes things; I know the conjugate of a norm is the indicator function for the dual norm unit ball, but I don't know a closed form expression for the conjugate of the square of a norm. (Except for the 2-norm.) Hopefully somebody else will have an answer. $\endgroup$ – littleO Nov 23 '13 at 23:06
0
$\begingroup$

My friend Hrushikesha and I think in the following way -

$f(x)= \frac{1}{2}\parallel x \parallel ^2$

$f^*(y)=\sup_x(x^Ty-\frac{1}{2}\parallel x \parallel ^2 ) $

From Hölder's inequality ,

$x^Ty \leq \parallel x \parallel \parallel y \parallel_*$ where, $\parallel y\parallel_*$ is dual norm.

$ \Rightarrow \sup_x(x^Ty-\frac{1}{2}\parallel x \parallel ^2 ) \leq \sup_x (\parallel x \parallel \parallel y \parallel_* - \frac{1}{2}\parallel x \parallel ^2) = \sup_{\parallel x \parallel} (\parallel x \parallel \parallel y \parallel_* - \frac{1}{2}\parallel x \parallel ^2)$

$ = \frac{1}{2}\parallel y \parallel_* ^2$

For a particular $y$ there is $x$ for which $x^Ty = \parallel x \parallel \parallel y \parallel_*$

Thus, $f^*(y)= \frac{1}{2}\parallel y \parallel_* ^2$

$\endgroup$
-1
$\begingroup$

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)=\max_x (||y||^2/2 - (x-y)^2/2)$$ trivially, $f^{∗}(y)= ||y||^2/2$.

$\endgroup$
3
  • $\begingroup$ Is this true if $\|x\|$ is just any norm - not just the 2-norm? $\endgroup$ – Ireth Nov 23 '13 at 21:55
  • $\begingroup$ In my question $\|x\|$ is not necessary the 2-norm. It is any arbitrary norm. That's why I was having trouble. $\endgroup$ – Ireth Nov 23 '13 at 22:03
  • $\begingroup$ This is true for 2 norm only. $\endgroup$ – Vivek Bagaria Nov 24 '13 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.