Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Take two vectors in the set and do convex combination. The result still lies in the set, thus it's convex. – Frenzy Li Dec 5 '12 at 8:54
up vote 5 down vote accepted

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$.

share|cite|improve this answer

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?

share|cite|improve this answer
Spoiler: Plug X into the inequality and equality. The rest goes like @pritam's answer. – Frenzy Li Dec 5 '12 at 9:00

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.