# The conjugate function of infimum of sum of functions

Given convex functions $$f_1, \ldots, f_k$$. Given $$g(x)$$, such that:

$$g(x) = \inf_{x_1, \ldots, x_k} \left\{ f_1(x_1) + \ldots + f_k(x_k) | x_1 + \ldots + x_k = x \right\}$$

Find $$g^*(x)$$.

I found this similar question and did similar steps (you may find them below):

By definition: $$f^*(y) = \sup_{x \in dom g} (y^T x - f(x))$$

Then $$g^*(x) = \sup_{x \in dom g} (y^T x - \inf_{x_1, \ldots, x_k} \left\{ f_1(x_1) + \ldots + f_k(x_k) | x_1 + \ldots + x_k = x \right\} = \ldots$$

Using the fact that $$\sup (-f(x)) = - \inf (f(x))$$

Then $$\ldots = \sup_{x \in dom g} (y^T x + \sup_{x_1, \ldots, x_k} \left\{ -f_1(x_1) - \ldots - f_k(x_k) | x_1 + \ldots + x_k = x \right\} =$$

$$= \sup_{x \in dom g, x_1, \ldots, x_k} (y^T x + \left\{ -f_1(x_1) - \ldots - f_k(x_k) | x_1 + \ldots + x_k = x \right\}$$

After these steps some questions arose:

1. Why the author removed constraint $$x_1 + \ldots + x_k = x$$ in the solution?
2. Why $$\sup_{x, x_1, \ldots, x_k} \{f(x) | x_1 + \ldots + x_k = x \} = \sup_{x_1, \ldots, x_k} \{f(x) | x_1 + \ldots + x_k = x \}$$ If so, how to prove it?
• Welcome to SE! Below, I've posted a complete solution to your problem, explaining all the steps in detail. Cheers! – dohmatob Oct 5 '19 at 10:47
• @dohmatob thank you for your help! – user711343 Oct 5 '19 at 22:13
• If it was helpful, please don't forget to upvote my answer. – dohmatob Oct 8 '19 at 7:40
• @dohmatob I have already upvoted, but upvote is not shown because I don't have enough reputation. – user711343 Oct 9 '19 at 11:58
• Ah, ok :). BTW, Ive updated your question. Welcome aboard :) – dohmatob Oct 9 '19 at 13:34

I'll just write down the full solution to your problem, and explain all the steps in the derivations.

So, let $$f_1,\ldots,f_k:\mathcal H \rightarrow (-\infty,+\infty]$$ be functions (convex or not) on a Hilbert space $$\mathcal H$$. Define $$g(x) := \inf_{x_1,\ldots,x_k}\left\{\sum_i f_i(x_i) \mid \sum_i x_i = x\right\}.$$ The function $$g$$ is also called the infimal convolution of $$f_1,\ldots,f_k$$, written $$g=\Box_{i=1}^k f_i$$.

Now, one computes $$\begin{split} g^*(x) &:= \sup_y x^Ty - g(y) \overset{(a)}{=} \sup_{y}x^Ty - \inf_{x_1,\ldots,x_k}\left\{\sum_i f_i(x_i) \mid \sum_i x_i = y\right\}\\ &\overset{(b)}{=} \sup_{y}x^Ty + \sup_{x_1,\ldots,x_k}\left\{-\sum_i f_i(x_i) \mid \sum_i x_i = y\right\}\\ & \overset{(c)}{=} \sup_{y,x_1,\ldots,x_k}\left\{x^Ty -\sum_i f_i(x_i) \mid \sum_i x_i = y\right\} \\ &\overset{(d)}{=} \sup_{y,x_1,\ldots,x_k}x^T\sum_i x_i -\sum_i f_i(x_i) \overset{(e)}{=} \sup_{y,x_1,\ldots,x_k}\sum_i (x^Tx_i -f_i(x_i)) \overset{(f)}{=} \sum_i\sup_{x_i}x^Tx_i - f_i(x_i)\\ &\overset{(*)}{=} \sum_i f_i^*(x), \end{split}$$ where

• (a) is just plugging-in the definition of $$g(y)$$
• (b) is because $$-\inf something = -\sup-thatthing$$
• (c) is because $$\sup_a u(a) + \sup_b u(b) = \sup_{a,b}(u(a) + u(b))$$
• (d) is just substituting the constraint $$y=\sum_i x_i$$ to get $$x^Ty = x^T\left(\sum_i x_i\right)$$. After this substitution, the variable $$y$$ doesn't play a role anymore in the maximization, and so can be deleted. Indeed, $$\sup_{a,b}u(a) = \sup_a u(a)$$.
• (e) is because $$x^T\sum_i x_i - \sum_i f_i(x_i) = \sum_i x^Tx_i - \sum_i f_i(x_i)=\sum_i(x^Tx_i - f_i(x_i))$$
• (f) is because $$\sup_{a,b}u(a) + u(b) = \sup_a u(a) + \sup_b u(b)$$
• (*) is because $$f_i^*(x) := \sup_{x_i}x^Tx_i - f(x_i)$$ by definition.

Therefore we have proven that

Convex conjugate of infimal convolution. $$(\Box_{i=1}^kf_i)^*(x) = \sum_{i=1}^k f_i^*(x)\; \forall x$$