How to show that $ Ax \le b$ is convex?

Question

For

$$ A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R} $$

one has to show that

$$ K:= \{ x \in \mathbb{R}^n: Ax \le b \}$$

is convex.

Now I'm aware that by definition, a set is convex $ \iff $ for all $x,y \in K, \lambda \in [0,1]$ any point $ \lambda x + (1- \lambda) y$ is again $ \in K$.

However, I do not see how to apply that here. Can you give me any directions? Thanks!

Can you tell if the hints have been useful? – egreg Jun 14 '13 at 22:12 — egreg, Jun 14 '13 at 22:12
Yep, indeed they were ... thank you! – bonifaz Jun 15 '13 at 10:22 — bonifaz, Jun 15 '13 at 10:22

egreg · Answer 1 · 2013-06-15T17:50:48.900

3

$Ax\le b$ implies $\lambda Ax\le \lambda b$, if $\lambda\ge0$.

Thus if $x,y\in K$ and $0\le\lambda\le1$, you have

$$ A(\lambda x+(1-\lambda)y) =\lambda Ax + (1-\lambda)Ay\le \lambda b+(1-\lambda)b=b $$

We use also that $x\le x'$ and $y\le y'$ implies $x+y\le x'+y'$.

edited Jun 15 '13 at 17:50

answered Jun 14 '13 at 19:33

egreg

238,574

user81566 · Accepted Answer · 2013-06-14T19:48:08.157

1

I suggest you to try first the case where $m=n=1$.

The general case is exactly the same.

edited Jun 14 '13 at 19:48

answered Jun 14 '13 at 19:32

user81566

337

How to show that $ Ax \le b$ is convex?

2 Answers2