3
$\begingroup$

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?

$\endgroup$

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks, I didn't know this. It is really interesting :) $\endgroup$ Oct 24, 2015 at 15:08
  • 1
    $\begingroup$ I also noticed you used "if and only if" in the 2nd line of your answer. Doesn't that imply the converse is true? $\endgroup$ Oct 24, 2015 at 15:18
  • 1
    $\begingroup$ Yes, that is right. The epigraph and secant definitions are equivalent. But that doesn't apply in your case because you have $0$ instead of $y$ on the right hand side. $\endgroup$ Oct 24, 2015 at 15:19
  • $\begingroup$ This is a very nice answer. $\endgroup$
    – dohmatob
    Oct 26, 2015 at 8:11
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you please elaborate on the first line of your answer? I don't understand how it follows from the definition of convexity. $\endgroup$ Oct 24, 2015 at 12:45
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't understand how the second to last line is implied by the ones above it. I mean how does it tell you that the straight line lies in the set? $\endgroup$ Oct 25, 2015 at 5:03
  • $\begingroup$ Easy. Let $x = (θ)x_1+(1−θ)x_2$ any point on the line, then the last line is completely equivalent to $\theta x_1 + (1-\theta )x_2 \in \{x|f(x) \leq 0\}$. The straight line lie in the set, therefore the set is convex. $\endgroup$
    – Fraïssé
    Oct 25, 2015 at 5:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .