-1

I need a help with prooving that a given set is a convex set: $A \in \mathbb{R}^{m\times n}, c \in \mathbb{R}^n , b\in \mathbb{R}^m:$ $? \in argmin\{ c^Tx| Ax=b,x \geq 0\}$

I know the definition of convexity: $S \in \mathbb{R}^n$ is a convex set if $\forall \lambda \in \mathbb{R}, 0 \leq\lambda \leq 1$ and $\forall x_1,x_2 \in S$ holds: $\lambda x_1 + (1 - \lambda)x_2 \in S$.

I tried to apply this for my set but I dont know how to prove that it works... Thanks in advance for any tips.

Empy2
  • 50,853
user1762087
  • 103

1 Answers1

2

Let $d=\min\{c^Tx:Ax=b\}$
Given $x_1\in S$, $x_2\in S$, we know $Ax_1=b,Ax_2=b,c^Tx_1=d,c^Tx_2=d$.
Calculate $A(\lambda x_1+(1-\lambda)x_2)$ and $c^T(\lambda x_1+(1-\lambda)x_2)$.
Conclude that $\lambda x_1+(1-\lambda)x_2\in S$ as well.

Empy2
  • 50,853
  • +1 (but this would be even better without the (unnecessary) arrows on top of some vectors but not of all). – Did Jan 03 '15 at 10:03