5
$\begingroup$

I need a help with prooving that a given set is a convex set:

$\{ x \in R^n | Ax \leq b, Cx = d \}$

I know the definition of convexity: $X \in R^n$ is a convex set if $\forall \alpha \in R, 0 \leq\alpha \leq 1$ and $\forall x,y \in X$ holds: $\alpha x + (1 - \alpha)y \in X$.

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

  • 1
    Take two vectors in the set and do convex combination. The result still lies in the set, thus it's convex.2012-12-05

3 Answers 3

9

Suppose $Ax\leq b,Cx=d$ and $Ay\leq b,Cy=d$. Now, $A(\alpha x+(1-\alpha )y)=\alpha Ax+(1-\alpha )Ay\leq\alpha b+(1-\alpha )b=b(\alpha +1-\alpha)=b$ and similarly one can show $C(\alpha x+(1-\alpha )y)=d$.

3

HINT: Via the definition. Define the set $S$, and let $X_1, X_2 \in S$. Then $\begin{cases} AX_1\le b, CX_1=d \\ AX_2\le b, CX_2=d \\ \end{cases} $ The convex combination of $X_1$ and $X_2$ is $X=\alpha X_1 + (1-\alpha) X_2$, where $\alpha\in[0,1]$.

How to verify that X belongs to the set S?

  • 0
    Spoiler: Plug X into the inequality and equality. The rest goes like @prita$m$'s answer.2012-12-05
1

Here AX≤b represents a lower closed halfspace and CX=d is a hyperplane. As the lower closed halfspace as well as hyperplane are the convex set. Hence, S is convex set, by using the property that the intersection of the convex sets is a convex set.