8
$\begingroup$

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.

  1. 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)?$$
  2. 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\}.$$

$\endgroup$
5
  • $\begingroup$ Please curate your notations. The usual symbol for the inf-convolution is $\varphi \Box \psi$. The usual symbol for epigraph is $\text{epi }\varphi$. In your definition of $\text{epi }\varphi$, replace replace $[x,\lambda]$ with $(x,\lambda)$, etc. $\endgroup$
    – dohmatob
    Jan 3, 2016 at 13:17
  • $\begingroup$ FYI: Convexity of the inf-convolution of two functions follows unconditionally from the convexity of the individual functions. See my solution below. $\endgroup$
    – dohmatob
    Jan 5, 2016 at 14:13
  • 1
    $\begingroup$ In the definition of the inf-convolution you need to replace the variable $x$ with $y.$ $\endgroup$ Jan 7, 2016 at 14:39
  • $\begingroup$ What are $\varphi^*$ and $\psi^*$? $\endgroup$ Jan 7, 2016 at 14:41
  • $\begingroup$ Yes, @Justpassingby is right. Bug: LHS is a function of $x$ whilst RHS is a function of $y$. $\endgroup$
    – dohmatob
    Jan 7, 2016 at 22:18

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If I open your link, I get a blank page... $\endgroup$
    – gerw
    Jan 5, 2016 at 8:46
  • $\begingroup$ OK, maybe the paper is not accessible from your location ? I've added a full description for the paper to help search. $\endgroup$
    – dohmatob
    Jan 5, 2016 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .