The infimal convolution of two functions f and g is defined as:
$(f \square g)(x)=\inf\limits_{y \in \mathbb{R}^n} \{ f(y) + g(x-y) \}$
I'm asked to prove that $(f \square g)(x)=\inf\limits_{\lambda \in \mathbb{R}} \{ (x,\lambda) \in epi(f)+epi(g) \}$.
I think I am close enough because I proved that $epi(f \square g)=epi(f) + epif(g)$ (I think that is the geometric interpretation of the infimal convolution). But I'm stucked on how to proceed in that probably easy proof.
Best Answer
$\newcommand{\epi}{\operatorname{epi}}$What you are trying to prove is not true without additional assumptions on $f$ and $g$.
Allow me to denote the infimal convolution of $f$ with $g$ by $f\# g$ because it renders better in MathJax.
Firstly, we can show that:
Proposition 1. $\epi f + \epi g \subseteq \epi(f \# g)$.
Proof. If we take $(x, a) \in \epi f$ and $(x', a') \in \epi g$, then
\begin{align} (f \# g)(x+x') = \inf_{x+x' = z_1 + z_2} f(z_1) + g(z_2) \leq f(x) + g(x') \leq a + a'. \end{align}
which comples the proof. $\Box$
Proposition 2. If the infimal convolution is exact, that is, if we can write $(f \# g)(x) = \min_{y} f(y) + g(x-y)$, then $\epi (f\# g) = \epi f + \epi g$.
Proof. Take $(x, c) \in \epi (f\# g)$. It suffices to show that $(x, c) \in \epi f + \epi g$. If the infimal convolution $f\# g$ is exact, then for given $x$, there exists a $y^* = y^*(x)$ so that
\begin{align} (f \# g)(x) = f(y^*) + g(x-y^*), \end{align}
therefore,
\begin{align} {}&{}f(y^*) + g(x-y^*) \leq c \\ \Leftrightarrow{}&{}g(x-y^*) \leq c - f(y^*) \\ \Leftrightarrow{}&{} \left(x-y^*, c - f(y^*) \right) \in \epi g \end{align}
Then,
\begin{align} (x,c) = (y^*, f(y^*)) + \left(x-y^*, c - f(y^*) \right) \in \epi f + \epi g, \end{align}
which completes the proof. $\Box$
Proposition 3. If $f\# g$ is exact, then $(f\# g)(x) = \inf_{\lambda \in \mathbb{R}}\{(x, \lambda) \in \epi f + \epi g\}$.
Proof. In general, for any function $F:\mathbb{R}^n \to \mathbb{R}$, it is
$$F(x) = \inf_{\lambda \in \mathbb{R}} \{F(x) \leq \lambda\} = \inf_{\lambda \in \mathbb{R}} \{(x, \lambda) \in \epi F\}.$$
This is known as epigraphical relaxation. For the infimal convolution we have
\begin{align} (f\# g)(x) {}={}& \inf_{\lambda \in \mathbb{R}} \{(x, \lambda) \in \epi (f\# g)\} \\ {}={}& \inf_{\lambda \in \mathbb{R}} \{(x, \lambda) \in \epi f + \epi g\}. \end{align}
Note: There are some conditions under which the infimal convolution is exact, for example if $f$ and $g$ are lsc and convex and $f$ satisfies $\lim_{t\to\infty} f(x)/\|x\| = \infty$, then $f\# g$ is exact.