Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
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
2  
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

3 Answers 3

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$.

share|improve this answer

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]$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.