# how to decide if set is convex?

I have two variables, $x$ and $y$, and a few inequalities of the form $f(x,y) \le g(x,y)$.

I want to know if the intersection of all $(x,y)$ that satisfy each inequality is convex. Is there some generic way to do it? Maybe based on second order derivative (or the Hessian in this case), similarly to the test whether a function is convex?

Finding whether one inequality defines convex set is also good, because if they all define convex sets, then their intersection must define a convex set as well.

Thanks.

-
If the Hessian of $f$ is positive definite, then the set defined by the inequality $f(x,y)\leq c$ is convex for any constant $c$. – Jim Belk May 31 '11 at 1:36
By definition: a set $X \subset \mathbb{R}^n$ is convex if for all $x, y \in X$ all their affine combinations $\theta x + (1 - \theta) y$ (where $0 < \theta < 1$) are also in $X$. For closed $X$ it is sufficient to show that $\frac{1}{2}(x + y) \in X$. – Alexei Averchenko Jun 30 '11 at 12:14
Never forget to try out some random sampling. It can save you a lot of time and effort if you find a counter-example. – user13838 Aug 29 '11 at 11:53

Take $h(x,y)=f(x,y)-g(x,y)$ and if this function $h$ is convex then $h(x,y)\leq0$ is a convex set in $\mathbb{R}^2$. However in general there could be functions $f,g$ which are not convex, but where $f(x,y)\leq g(x,y)$ is still convex (see also other answers). If there is a general method then it should be beyond just convexity of $f-g$.

-

Perhaps, by manipulating your inequalities, this can be useful to you.

Let $f:[a,b]\to\mathbb{R}$. Then $f$ is convex if and only if the set $$A:=\{(x,y):x\in[a,b],\; y\geq f(x) \}$$ is convex in $\mathbb{R}^2$.

To prove this, suppose that $f$ is convex in $[a,b]$. Let $(x_0,y_0),(x_1,y_1)\in A$ and $t\in [0,1]$. Since $[a,b]$ is convex, $$(1-t)x_0+tx_1\in [a,b].$$ Then by the convexity of $f$, $$(1-t)y_0+ty_1\geq (1-t)f(x_0)+tf(x_1)\geq f((1-t)x_0+tx_1).$$ Therefore $$(1-t)(x_0,y_0)+t(x_1,y_1)\in A.$$

Reciprocally, if $(y,f(y)),(x,f(x))\in A$, then for each $t\in [0,1]$, $$((1-t)y+tx,(1-t)f(y)+tf(x))\in A,$$ i.e.: $$(1-t)f(y)+tf(x)\geq f((1-t)y+tx),$$ therefore $f$ is convex in $[a,b]$.

-

Consider the following inequality on $0\leq x< \pi/2$: $$\sin(x + \pi+t\pi) \leq \sin(x) + 1/2$$ as $t$ varies from 0 to 1.

Then the set will transform from convex to non-convex. I don't know if this helpful, but translation of the variable in one of the function affect the outcome.

-