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

Direct application of definition of Fenchel-Legendre transform. — dohmatob, Feb 02 '16 at 08:04

score 4 · Accepted Answer · answered Feb 01 '16 at 20:15

4

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

answered Feb 01 '16 at 20:15

Dendi Suhubdy

163

1

it may help someone who needs it – Dendi Suhubdy Feb 02 '16 at 14:06
1

Where is the assumption of convexity used? – Sep 22 '16 at 09: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. – Jürgen Sukumaran Oct 18 '17 at 11:41

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

1 Answers1

Linked