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.
$\endgroup$ 13 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$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?
$\endgroup$ 1 $\begingroup$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.
$\endgroup$
