1
$\begingroup$

Let $f_1$ and $f_2$ be convex functions on $R^n$. Their infimal convolution $g = f_1 \diamond f_2$ is defined as $$ g(x) = \inf \{f_1(x_1) + f_2(x_2) \mid x_1 + x_2 = x\}. $$ Prove that $g^\star = f_1^\star + f_2^\star$.

$\endgroup$
  • $\begingroup$ Direct application of definition of Fenchel-Legendre transform. $\endgroup$ – dohmatob Feb 2 '16 at 8:04
3
$\begingroup$

I finally found a solution to the problem

$$ g*(y) = \underset{x}{\sup}\; \{x^Ty - g(x)\} $$

As we know

$$ g(y) = \underset{x_1 + x_2 = x}{\inf}\; \{f_1(x_1) + f_2(x_2)\} $$

Now we have

$$ g*(y) = \underset{x}{\sup}\; \{x^Ty - \underset{x_1 + x_2 = x}{\inf}\; \{f_1(x_1) + f_2(x_2)\} \} $$

$$ = \underset{x}{\sup}\; \{x^Ty + \underset{x_1 + x_2 = x}{\sup}\; \{-f_1(x_1) - f_2(x_2)\} \} $$

$$ = \underset{x}{\sup}\underset{x_1 + x_2 = x}{\sup}\; \{x^Ty -f_1(x_1) - f_2(x_2)\} \} $$

$$ = \underset{x_1,x_2}{\sup}\; \{x_1^Ty + x_2^Ty -f_1(x_1) - f_2(x_2)\} \} $$

$$ = f_1^\star(x_1) + f_2^\star(x_2) $$

$\endgroup$
  • 1
    $\begingroup$ it may help someone who needs it $\endgroup$ – Dendi Suhubdy Feb 2 '16 at 14:06
  • 1
    $\begingroup$ Where is the assumption of convexity used? $\endgroup$ – user178826 Sep 22 '16 at 9:36
  • $\begingroup$ @dohmatob On the contrary, this was very helpful to find and consequently not a waste of bandwidth. Kind of rude to imply otherwise, to be honest. $\endgroup$ – TSF Oct 18 '17 at 11:41

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.