1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Welcome to SE! Below, I've posted a complete solution to your problem, explaining all the steps in detail. Cheers! $\endgroup$ – dohmatob Oct 5 '19 at 10:47
  • $\begingroup$ @dohmatob thank you for your help! $\endgroup$ – user711343 Oct 5 '19 at 22:13
  • $\begingroup$ If it was helpful, please don't forget to upvote my answer. $\endgroup$ – dohmatob Oct 8 '19 at 7:40
  • $\begingroup$ @dohmatob I have already upvoted, but upvote is not shown because I don't have enough reputation. $\endgroup$ – user711343 Oct 9 '19 at 11:58
  • $\begingroup$ Ah, ok :). BTW, Ive updated your question. Welcome aboard :) $\endgroup$ – dohmatob Oct 9 '19 at 13:34
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.