The conjugate function of infimal convolution

There is a similar discussion:
Infimal convolution conjugate

I just want to ask how to prove that for convex $f_i$ $\forall i$ if

$$ g(x) = \inf\{f_1(x_1)+f_2(x_2)|x_1+x_2=x\} $$

then $g^{*}(y) = f_1^{*}(y)+f_2^{*}(y)$ ?

We know the definition for the conjugate function is $$g^*(y) = \sup_x \{\langle x,y \rangle - g(x)\} $$

We have the following:
$$g^*(y) = \sup_x \{\langle x,y \rangle - (\inf\{f_1(x_1)+f_2(x_2)|x_1+x_2=x)\} $$

Then how to deal with this complicated term?

Solution 1:

Note that $$\begin{align}g^*(y) &= \sup_{x,x_1,x_2} \{ x^Ty - f_1(x_1) - f_2(x_2) | x_1+x_2 = x \} \\ &= \sup_{x_1,x_2} \{ (x_1+x_2)^Ty - f_1(x_1) - f_2(x_2)\} \\ &= \sup_{x_1,x_2} \{ x_1^Ty - f_1(x_1) + x_2^Ty - f_2(x_2)\} \\ &= \sup_{x_1} \{ x_1^Ty - f_1(x_1) \} + \sup_{x_2} \{ x_2^Ty - f_2(x_2)\} \end{align}$$