I'm having a hard time proving to myself that the following function is convex: $$f'(x')= \inf_{Ax = x'} f(x)$$
where $f(x)$ is convex.
i.e., I'm trying to show
$$f'(tx_1+(1-t)x_2) \le tf'(x_1)+(1-t)f'(x_2)\tag{1}$$
where $t\in[0,1]$ By definition,
$$f'(tx_1+(1-t)x_2) \le f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)$$
But how does this relate this to $(1)$?
Problem: Suppose $f(x)$ is convex. Prove that $g(y) = \inf\limits_{Ax = y} f(x)$ is convex.
Proof: Let $t\in [0, 1]$. We need to prove that $$g(t y_1 + (1-t)y_2) \le t g(y_1) + (1-t)g(y_2).\tag{1}$$
Let $\epsilon > 0$. From the definition of infimum, there exists $x_1$ and $x_2$ such that $Ax_1=y_1$, $Ax_2 = y_2$, $f(x_1) \le g(y_1) + \epsilon$ and $f(x_2) \le g(y_2) + \epsilon$. Thus, we have \begin{align} g(ty_1 + (1-t)y_2) &\le f(tx_1 + (1-t)x_2)\\ & \le tf(x_1) + (1-t)f(x_2) \\ &\le t (g(y_1) + \epsilon) + (1-t)(g(y_2) + \epsilon)\\ & = tg(y_1) + (1-t)g(y_2) + \epsilon. \end{align} Since this holds for any $\epsilon > 0$, (1) holds. We are done.
Reference: Boyd and Vandenberghe, "Convex Optimization".