Proving convexity of $h(y) = \inf_{Ax=y}{f(x)}$ for convex $f(x)$ over $\mathbb{R}^n$, and $A\in\mathbb{R}^{m\times n}$

Question

Came across this question in an optimization course:

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be convex, and let $A\in\mathbb{R}^{m\times{n}}$. Consider:

$$h(y) = \inf_{Ax=y}{\{f(x)}\}$$

Prove that $h$ is convex.

Any help? It's not the traditional preservation of convexity under infimum. I believe the direction should be something like: Assume $x_0\in\mathbb{R}^n$ is the $x$ for which $h(y_0)=f(x_0)$. Thus,

$$h(y_0)=f(x_0)\leq{f(x_0+z)}$$

for any $z$ that holds $Az=0$.

From here, I'm not sure how to continue...

Answer 1

Let $\epsilon>0$ be arbitrary and assume that $$ u = \alpha v + (1-\alpha)w,\quad \alpha\in(0,1), \;u,v,w\in\mathbb{R}^m. $$ Assume $A^{-1}(v)=\{x|Ax = v\}$ is not empty. By the assumption, we can find $x$ such that $Ax = v$ and $$ h(v) \leq f(x)\leq h(v)+\epsilon. $$ Also assume that $A^{-1}(w)$ is not empty and find $x'$ such that $$ h(w)\leq f(x')\leq h(w)+\epsilon. $$ Now, note that $\alpha x+(1-\alpha)x' \in A^{-1}(u)$. Therefore, it holds that $$ h(u) \leq f(\alpha x+(1-\alpha)x') \leq \alpha f(x) +(1-\alpha)f(x')\leq \alpha h(v)+(1-\alpha)h(w) +\epsilon. $$ Since $\epsilon>0$ was arbitrary, we get $$h(u) \leq \alpha h(v)+(1-\alpha)h(w) , $$as desired.

If $A^{-1}(v)$ is empty, according to the definition, we have $$ h(v) = \inf_{x\in A^{-1}(v)} f(x) = \inf \varnothing = \infty. $$ Hence if one of the sets $A^{-1}(v)$ or $A^{-1}(w)$ is empty, then $$ h(u) \leq \alpha h(v)+(1-\alpha)h(w)=\infty $$ is obvious. (But it is desirable to assume that $A :\mathbb{R}^n \to \mathbb{R}^m$ is surjective.)

Answer 2

Consider $g(x,y) = f(x) + \delta( (x,y) | Ax=y)$, where $\delta$ is the support function that takes the value 0 if $Ax=y$, and $\infty$ otherwise. Since $g$ is jointly convex and $h$ is the infinimum over one coordinate (partial minimization), $h$ is convex.