Help needed in understanding the constraints of convex optimisation problem

Question

A convex optimisation problem is of the form:

$$\begin{array}{ll} \text{minimize} & f(x)\\ \text{subject to} & g_i (x) \leq 0 \text{ for } i \in \{1,2,\dots,m\}\\ & h_i (x) = 0 \text{ for } i \in \{1,2,\dots,p\}\end{array}$$

where $f$ is a convex function, $g_i$ are convex functions, $h_i$ are affine functions and $x$ is optimisation variable. On page 8 of this paper by Zico Kolter (updated by Honglak Lee), it is written that:

Is it imporant to note the direction of these inequalities: a convex function $g_i$ must be less than zero. This is because the $0$-sublevel set of $g_i$ is a convex set, so the feasible region, which is the intersection of many convex sets, is also convex (recall that affine subspaces are convex sets as well). If we were to require that $g_i \geq 0$ for some convex $g_i$, the feasible region would no longer be a convex set, and the algorithms we apply for solving these problems would no longer be guaranteed to find the global optimum. Also notice that only affine functions are allowed to be equality constraints. Intuitively, you can think of this as being due to the fact that an equality constraint is equivalent to the two inequalities $h_i \leq 0$ and $h_i \geq 0$. However, these will both be valid constraints if and only if hi is both convex and concave, i.e., $h_i$ must be affine

Can somebody explain me this quote? My questions:

1. What is the feasible region?

2. Why would the feasible region not be convex if $g_i \geq 0$? Isn't a sublevel set of a convex function always convex?

3. What is being mentioned about the equality constraints of the affine set?

Answer 1

1. The feasible region is the set of $x$ satisfying all constraints. In other words, its the set of valid (if not necessarily optimal) solutions.
2. Yes, the sublevel sets of convex $g_i$ are always convex, but if the constraint is $g_i(x)\ge 0$ then you are interested in superlevel sets, not sublevel sets. Superlevel sets are convex for concave functions. For example, consider the convex function $g(x)=x^2-4$. The constraint $g(x)\le 0$ is satisfied by the interval $[-2,2]$, which of course is convex. Flip the constraint to $g(x)\ge 0$, and the feasible set is $(-\infty, -2] \cup [2,\infty)$, which is not convex.
3. The statement about the equality constraints is that they are required to be affine (linear plus constant term). If you add a nonlinear equality constraint ($h(x)=0$, $h()$ not linear), the feasible region will not be convex. The intuitive argument being offered is that $h(x)=0$ is the same as the pair of constraints $0\le h(x) \le 0$. Our previous guarantee of convexity in the feasible region could only be invoked if $h$ were both concave (so that $\{x:h(x)\ge 0\}$ is known convex) and convex (so that $\{x:h(x)\le 0\}$ is known convex). A function that is simultaneously convex and concave must be affine.