# 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?

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}
• In the first line, how could you remove the "$\inf$"? ($g(x) = \inf$...) – sleeve chen Feb 7 '17 at 9:31
• I used that $\inf(f(x)) = -\sup(-f(x))$. – LinAlg Feb 7 '17 at 9:52