Why do these two elements exist and satisfy this equation?

Question

From Convex optimization by Boyd and Vanderberghe:

In the below red box, why do there exist $y1,y2$ such that the equation follows? Doesn't it depend on what the domain of $f$ and what the function $f$ are?

---

Answer 1

Maybe it is easier to think about the inequality as $$|f(x_i,y_i)−g(x_i)|≤\epsilon$$ It is basically saying, you can get to within epsilon of the infimum, for any epsilon. This follows from the definition of infimum.

As for the domain, it seems to me that there is a bit of fudging in the calculation of the infimum. The infimum for a given $x$ coordinate is not necessarily calculated over the whole of $y\in C$ but only over those values for which $f(x,y)$ makes sense, i.e. values $y$ such that $y\in C$ and for which $(x,y)$ lies in the domain of $f$. This is kind of implied by how they define the domain of $g$ ("for some $y \in C$").

With that proviso, the rest follows without any problems. An $y_1$ can be found such that it lies in $C$ and $(x_1,y_1)$ is in the domain of $f$, and for which $|f(x_1,y_1)−g(x_1)|\le \epsilon$. The same goes for $y_2$.