Inequality involving a convex function

Question

Do the points that satisfy an inequality involving a convex function constitute a convex set? Specifically if $x \in \mathbb R^n$ and I have a function $f(x)$ then is the set $\{x \mid f(x) \le 0\}$ convex?

If this is true then is it enough to show that the sets formed by constraint functions in a convex optimization problem are convex sets rather than having to show that the constraint function itself is convex?

I am also having trouble understanding what is meant by minimizing a convex function "over a convex set". Does this mean that the feasible set of the problem is convex or the constraint inequalities are convex?

Answer 1

Yes, if $f$ is convex, $A = \{x \mid f(x) \le 0\}$ is a convex set. This follows just from the definition of convexity of $f$.

But the converse is not true. The set $A$ can be convex, even if $f$ is not. In this case, it is a matter of notation, whether $$\text{Minimize } g(x) \text{ such that } f(x) \le 0.$$ is called a convex problem. I would say, that this problem is not convex, since the constraint function $f$ is not convex.

Note that both problems are essentially equivalent.

But I would call $$\text{Minimize } g(x) \text{ such that } x \in A,$$ a convex problem, since the set $A$ is convex. And this is "minimizing $g$ over the convex set $A$".

In my opinion, the answers to your second and third paragraph are a matter of taste.

Answer 2

gerw is correct, but since you asked for some elaboration I thought I would offer it. One of the fundamental truths in convex analysis is this: a function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ is convex if and only if its epigraph $$\mathop{\textrm{epi}} f \triangleq \{(x,y)\in\mathbb{R}^n\times\mathbb{R}\,|\,f(x)\leq y\}$$ is a convex set. You've probably seen the standard secant definition of convexity: that $\mathop{\textrm{dom}}(f)$ is a convex set, and $$f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) \quad \forall x_1,x_2\in\mathop{\textrm{dom}}(f),~\lambda\in[0,1].$$ In my view the epigraph definition of convexity is more basic---the convexity of the domain is built in, for instance---but in fact, each can be derived from the other. From this it should be clear that the $0$-level set $$\{x\in\mathbb{R}^n\,|\,f(x)\leq 0\}$$ being just an $n$-dimensional slice of a convex set, is itself convex.

The converse is not true. For instance, let $f(x)=\lfloor x \rfloor$. This function is not convex, of course, but $$\{x\in\mathbb{R}\,|\,f(x)\leq 0\} = (-\infty,1)$$ which is a convex set (an interval).

There is another property known as quasiconvexity that is interesting: a function $f$ is quasiconvex if and only if its $\alpha$-sublevel set $$\{x\in\mathbb{R}^n\,|\,f(x)\leq \alpha\}$$ is a convex set (possibly empty) for all $\alpha\in\mathbb{R}$. All convex functions are quasiconvex of course, but the converse is not true; the floor function above is quasiconvex, for instance.

Answer 3

The set $\{x | f(x) \leq 0\}$ is so called $0$-level sublevel set of $f(x)$.

If $f(x)$ is convex, then its $\alpha$-sublevel sets are convex, $\alpha \in \mathbb{R}$ and it is not hard to show.

Take two points $x_1, x_2 \in \{x | f(x) \leq 0\}$, then $f(x_1) \leq 0$, and $f(x_2) \leq 0$

From definition of convexity, $f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1- \theta) f(x_2)$

At this point, notice that $\theta \in [0,1]$, so $\theta f(x_1) \leq 0$ is true, and $(1- \theta) f(x_2) \leq 0$ is true.

$\Rightarrow \theta f(x_1) + (1- \theta) f(x_2) \leq 0$ is also true (why?),

$\Rightarrow \theta x_1 + (1-\theta)x_2 \in \{x | f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1- \theta) f(x_2) \leq 0\}$

Since the straight line lies in the set for all $x_1,x_2$, therefore the set is convex.