I am reading Boyd's Convex Optimization book. In section 3.2.5 Minimization, he talks about why partial minimization preserves convexity. Specifically,
If $f$ is convex in $(x,y)$, and $C$ is a convex nonempty set, then the function
$$
g(x)= \inf_{y\in C} f(x,y)
$$
(3.16) is convex in $x$, provided $g(x) > -\infty$ for all $x$.
Then the book explains the result in terms of epigraphs:
I am not allowed to post picture yet, please see the book's explanation here
That's all the book says in terms of epigraphs. My question is, doesn't this explanation ignore the infimum part in 3.16? Why is $(x,y,t)\in epi f$ for some $y\in C$ automatically a convex set? Does it have any bearing on the fact that the infimum of $t=f(x,y)$ is obtained at "some" $y$?
I am not a math major and am learning convex optimization by myself, sorry if the question is completely obvious and naive.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To answer my own question:
$(x, t)\in \text{epi }g \Rightarrow t\geq g(x)=\inf_{y\in C} f(x,y)$, suppose the infimum is obtained at $y\star$, that means $t\geq f(x,y\star)\Rightarrow (x,y\star,t)\in \text{epi}f$, therefore $(x,t)\in \{(x,t)~| \quad (x,y,t) \in \text{epi} (f), \quad \text{for some} ~ y \in C \}$.
However, there is a small problem in the above deduction regarding the equal sign condition, and that results in the counter point Ashkan provided. Fixing the problem should be easy (possibly the one Ashkan gave) so it will be omitted here.
Best Answer
That's wrong I think ! The $\text{epi}(g)$ is not necessarly represented using that set in picture !
For example take $f(x,y) = x^2 + e^{-y}$ and $C = [0 , + \infty)$. Then $$g(x)= \inf_{y\in C} f(x,y) = x^2$$
And clearly $(0,0) \in \text{epi}(g)$ but $(0,0) \notin \{(x,t)~| \quad (x,y,t) \in \text{epi} (f), \quad \text{for some} ~ y \in C \}$
However, the result (lemma) itself is correct I think!
I guess that we have $$\text{epi(g)} = \overline{\{(x,t)~| \quad (x,y,t) \in \text{epi} (f), \quad \text{for some} ~ y \in C \}}$$