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

Question

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

Answer 1

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