0
$\begingroup$

The first $A\bar{x}\leq \bar{b}$ is stated to be convex in my book but why?

I cannot see it directly from the definition:

Let $S :=\{\sum \lambda_{i} x_{i} \}$.

$\text{S is a convex space iff } \begin{cases} \sum \lambda_{i} = 1 \\ \lambda_{i} \in [0,1]\\ \lambda_{i} \geq 0 \\ \end{cases} $

  • 0
    You are confused about the definition. Examine the answer and see if that helps.2011-10-18

1 Answers 1

3

We shall prove that the set $S = \{x : Ax \leq b \}$ is convex. The same proof works for $Ax \geq b$.

Consider any $n \in \mathbb{N}$. Consider $n$ elements in $S$. Call them $x_1,x_2,\ldots,x_n$ i.e. $x_k \in S$ for $k \in \{1,2,\ldots,n\}$.

Consider $n$ scalars $\lambda_j$ such that $\displaystyle \sum_{j=1}^{n} \lambda_j = 1$. We want to show that $x = \displaystyle \sum_{j=1}^{n} \lambda_j x_j \in S$.

Since $x_j \in S$, we have $Ax_j \leq b$. Hence, we get $Ax = A \left( \displaystyle \sum_{j=1}^{n} \lambda_j x_j \right) = \displaystyle \sum_{j=1}^{n} A \left(\lambda_j x_j \right) = \displaystyle \sum_{j=1}^{n} \lambda_j A x_j \leq \displaystyle \sum_{j=1}^{n}\lambda_j b = \left(\displaystyle \sum_{j=1}^{n} \lambda_j \right) b = b$ Hence, we have $Ax \leq b.$ Hence, $S$ is a convex set.

  • 0
    @hhh: the same thing holds and the same proof works.2011-10-19