# Infimal convolution $g^\star = f_1^\star + f_2^\star$

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

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

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

• it may help someone who needs it – Dendi Suhubdy Feb 2 '16 at 14:06
• Where is the assumption of convexity used? – user178826 Sep 22 '16 at 9:36
• @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. – TSF Oct 18 '17 at 11:41