prove region S defined by a set of linear constraints Ax <= B where A is rectangular matrix and b is column vector is convex

Question

A feasible region S defined by a set of linear constraints { Ax <= B } where A is M by N rectangular matrix and b is column vector . prove that S is convex

Answer 1

Look at the definition of convexity and verify it directly: For any two points $x$ and $y$ in $S$, consider the points $\lambda x + (1-\lambda) y$ (for $\lambda \in [0,1]$) on the straight line between then and show that the entire line segment lies in $S$.

Answer 2

Hint: if $x$ and $y$ satisfy the constraint and $0 \le t \le 1$, then $tx + (1-t)y$ satisfies it.

Answer 3

For $\lambda\in [0,1]$, $y,z\in S$ we have $$ A(\lambda y+(1-\lambda)z)=\lambda Ay+(1-\lambda)Az\leq \lambda b+(1-\lambda)b=b,$$ where we used $y,z\in S$ at the $\leq$. So by definition $S$ is convex.