Let $E$ be a normed vector space. Given two functions $\varphi$, $\psi : E \to (-\infty, +\infty]$, one defines the inf-convolution of $\varphi$ and $\psi$ as follows: for every $x \in E$, let$$(\varphi \Box \psi)(x) = \inf_{x \in E} \{\varphi(x – y) + \psi(y)\}.$$I have two quetsions.
- Let $\varphi$, $\psi: E \to (-\infty, +\infty]$ be functions such that $D(\varphi^*) \cap D(\psi^*) \neq \emptyset$. How do I see that$$\text{epist}(\varphi \Box \psi) = (\text{epist}\,\varphi) + (\text{epist}\,\psi)?$$
- If $\varphi$, $\psi: E \to (-\infty, +\infty]$ are convex functions such that $D(\varphi^*) \cap D(\psi^*) \neq \emptyset$, does it follow that $(\varphi \Box \psi)$ is a convex function?
Notation. We denote by $D(\varphi)$ the domain of $\varphi$, that is,$$D(\varphi) = \{x \in E: \varphi(x) < +\infty\}.$$Given a function $\varphi: E \to (-\infty, +\infty]$, set$$\text{epist}\,\varphi = \{(x, \lambda) \in E \times \mathbb{R}: \varphi(x) < \lambda\}.$$
Best Answer
(i) The (strict) epigraph of the inf-convolution of two functions is the Minkowski sum of the (strict) epigraphs of those functions. If your functions are proper convex l.s.c, (so that $\varphi^{**} = \varphi$, etc.) then your conclusion follows from Theorem 1 (ii) of this nice paper.
Just in case the above link for the reference paper doesn't work (maybe not accessable from your location, etc.), here is the paper information:
Infimal convolution, c-subdifferentiability, and Fenchel duality in evenly convex optimization, M.D. Fajardo · J. Vicente-Pérez · M.M.L. Rodríguez
Received: 7 October 2010 / Accepted: 16 June 2011 © Sociedad de Estadística e Investigación Operativa 2011
Update: on the convexity of inf-conv of convex functions
(ii) Yes if $\varphi$, and $\psi$ are convex, then so is $\varphi \Box \psi$ (without any other conditions!).
Proof. Let's prove something a bit more general (from this authoritative book by HHB and PLC):
If $X$ and $Y$ are real Hilbert spaces and $F : X \times Y \rightarrow (-\infty,+\infty]$ is convex, then so is the marginal function $f : X \rightarrow (-\infty,+\infty], x \mapsto \inf_{y \in Y}F(x, y)$.
Indeed, take $x_1,x_2 \in \text{dom }f$ and $\alpha \in (0, 1)$. Further, let $\eta_k \in (f(x_k), +\infty]$. Then there exist $y_1, y_2 \in Y$ such that $F(x_1, y_1) < \theta_1$ and $F(x_2, y_2) < \theta_2$. Now using the convexity of $F$, we have $$ \begin{split} f(\alpha x_1 + (1-\alpha)x_2) &\le F(\alpha x_1 + (1-\alpha)x_2, \alpha y_1 + (1-\alpha)y_2) \\ &\le \alpha F(x_1, y_1) + (1-\alpha)F(x_2, y_2) < \alpha \theta_1 + (1-\alpha)\theta_2. \end{split} $$ Thus $f(\alpha x_1 + (1-\alpha)x_2) < \alpha \theta_1 + (1-\alpha) \theta_2$, and in the limit $\theta_k \, \searrow \, f(x_k)$ (i.e taking the supremum of the RHS w.r.t the $\theta$'s), we obtain the convexity of $f$.
For your particular case, simply take $F(x, y) :\equiv \varphi(y-x) + \psi(x)$, a sum of two convex functions. Conclude.