Convexity of $f_t(y)=\min_x \left[ \frac{1}{2t}\|x-y\|^2 + f(x) \right]$ I need to show that the function below is convex
$$ f_t(y)=\min_x \left[ \frac{1}{2t}\|x-y\|^2 + f(x) \right]$$ given that $f(x)$ is a convex function from $R^n$ to $R\;$ $x,y \in R^n$ and $t \in R$
I  know that $ \|x-y\|^2 $ is a convex function of $y$ and therefore for every $x$ we have
\begin{align*}
\|{x-(\lambda y_1 + (1-\lambda)y_2)}\|^2
\leq \lambda \|{x-y_1}\|^2 + (1-\lambda)\|{x-y_2}\|^2
\end{align*}
And now:
\begin{align*}
f_t( \lambda y_1 + (1-\lambda ) y_2 ) &= \min_x \left[ \frac{1}{2t}\|x-(\lambda y_1 + (1-\lambda ) y_2 )\|^2 + f(x)\right]\\
&\le \min_x \left[\frac{1}{2t}  \lambda \|{x-y_1}\|^2 + (1-\lambda)\|{x-y_2}\|^2 + f(x)\right]
\end{align*}
And here I'm stuck.
 A: Assume that $t > 0$.
We need to prove that
$$f_t(\lambda y_1 + (1-\lambda)y_2) \le \lambda f_t(y_1) + (1-\lambda)f_t(y_2). \tag{1}$$
Let
$h(x, y) := \frac{1}{2t}\|x - y\|^2 + f(x)$.
Let $\epsilon > 0$. There exist $x_1$ and $x_2$ such that
$h(x_1, y_1) \le f_t(y_1) + \epsilon$ and $h(x_2, y_2) \le f_t(y_2) + \epsilon$.
Thus, we have
\begin{align*}
 f_t(\lambda y_1 + (1-\lambda)y_2) &\le h(\lambda x_1 + (1-\lambda)x_2, \lambda y_1 + (1-\lambda)y_2)\\
 & \le \lambda h(x_1, y_1) + (1-\lambda)h(x_2, y_2) \\
 &\le \lambda (f_t(y_1) + \epsilon) + (1-\lambda)(f_t(y_2) + \epsilon)\\
 & = \lambda f_t(y_1) + (1-\lambda)f_t(y_2) + \epsilon.
\end{align*}
Since this holds for any $\epsilon > 0$, (1) holds.
We are done.
See [1], page 88.
References
[1] Boyd and Vandenberghe, "Convex optimization".
http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
A: Let $g(x)$ be the first function inside the $\min$.
Note that $f_t(y) = (g \square f)(y) = \min\{ g(x_1) + f(x_2) \mid x_1+x_2 = y \}$. This is called infimal convolution.
Show that $\operatorname{epi} (g \square f) = \operatorname{epi} g + \operatorname{epi}  f$. It follows from this that $g \square f$ is convex.
For a reference, see Rockafellar, "Convex Analysis", Theorem 5.4.
Addendum: To show the epigraph equality above.
Suppose $(y,\alpha) \in \operatorname{epi} (g \square f)$. Then $g(x_1)+f(x_2) \le \alpha$ for all $x_1,x_2$ such that $x_1+x_2 = y$. Note that $(x_1,g(x_1)) \in \operatorname{epi} g$ and $(x_2,f(x_2)) \in \operatorname{epi} f$. Since
$(y, g(x_1)+f(x_2))) \in \operatorname{epi} g + \operatorname{epi}  f$ it follows that $ (y,\alpha)) \in \operatorname{epi} g + \operatorname{epi}  f $.
$(x_1,\alpha_1) \in \operatorname{epi} g$ and $(x_2,\alpha_2) \in \operatorname{epi} f$, then
$g(x_1) \le \alpha_1, f(x_2) \le \alpha_2$ and so
$(g \square f)(x_1+x_2) \le g(x_1)+f(x_2) \le \alpha_1+\alpha_2$. Hence
$(x_1,\alpha_1)+(x_2,\alpha_2) \in \operatorname{epi} (g \square f)$.
