Understanding whether a set of vectors is convex I have a set $\Theta$ of vectors $\theta$ and I want to find whether $\Theta$ is convex. The difficulty that I have is related to some "peculiar" constraints that I impose on some components of $\theta$: I would like your help to understand whether these constraints are cause of non-convexity of $\Theta$. 

Intro: Let me introduce my question by starting from a simple case. 
Let $\theta\equiv (a,b,q)$ where $a,b$ are scalars and $q$ is a row vector of dimension $d_q$ with each element in $[0,1]$. I interpret $\theta$ as an ordered triplet. 
Let $\Theta\equiv \Big\{\theta\equiv (a,b,q) \text{: } (a,b)\in \mathbb{R}^2\text{, } q\in [0,1]^{d_q} \Big\}$
$\Theta$ so defined is convex.

Additional notation: Let me now add constraints on some components of $q$. In order to do that I need to index the components of $q$ in a certain way, as explained below.
Let 
$$
\mathcal{Q}_{1}(a,b)\equiv \{+\infty, -\infty, -a, -b\}
$$
$$
\mathcal{Q}_{2}(a,b)\equiv \{+\infty, -\infty, b-a, -b\} 
$$
$$
\mathcal{Q}(a,b)\equiv  \mathcal{Q}_{1}(a,b)\times \mathcal{Q}_{2}(a,b)=\{(\infty, \infty), (-\infty,\infty), (-a,\infty), (-b, \infty)\text{, ...}\} 
$$
Notice that $\mathcal{Q}(a,b)$ has cardinality $4^2$. 
Let $d_q\equiv 4^2$. 
Each element of $q$ corresponds to an element of $\mathcal{Q}(a,b)$. This relation can be used to "reshape" $q$ as a matrix $4\times 4$
$$
q\equiv \begin{array}{|c|c|c|c|c|} 
&  \color{blue}{b-a}   & \color{blue}{-b}   &  \color{blue}{\infty}          &  \color{blue}{-\infty}  \\
\hline
\color{blue}{-a}                   & q(1,1)  &q(1,2) & q(1,3) & q(1,4)  \\
\hline
\color{blue}{-b  }                 & q(2,1)  &q(2,2) & q(2,3) & q(2,4)  \\
\hline
\color{blue}{ \infty }             & q(3,1)  &q(3,2) & q(3,3) & q(3,4)  \\
\hline
 \color{blue}{-\infty }            & q(4,1)  &q(4,2) & q(4,3) & q(4,4)  \\
 \hline  
\end{array}$$
where $q(i,j)$ denotes the $ij$-the element of the matrix above.

Constraints: I am now ready to introduce the desired constraints on some components of $q$. 
1) Constraint (1): $$q(4,1)=q(4,2)=q(4,3)=q(4,4)=q(1,4)=q(2,4)=q(3,4)=0$$
2) Constraint (2): $$q(3,3)=1$$
3) Constraint (3): for every two elements $u', u''$ of $\mathcal{Q}(a,b)$ such that $u'\leq u''$, we have that 
$$
q(i,j)-q(i,l)-q(k,j)+q(k,l)\geq 0
$$
where 


*

*$u'\leq u''$ is intended component-wise

*$(i,j)$ and $(k,l)$ are the coordinates of respectively $u', u''$ in the matrix above.

Question: let 
$$\Theta\equiv \Big\{\theta\equiv (a,b,q) \text{: } (a,b)\in \mathbb{R}^2\text{, } q\in [0,1]^{d_q} \text{, and $q$ satisfies constraints (1), (2), (3)} \Big\}$$
Is $\Theta$ convex?

My thoughts:  The constraints (1), (2), (3) are linear in $q$. Therefore, I am tempted to conclude that $\Theta$ is convex. Is this correct?
 A: No, the set does not have to be convex even if the constraints look linear. The easiest intuition behind it is the following: consider the epigraph of a function
$$
\operatorname{epi}(f)=\{(x,y)\in\Bbb{R}^2\colon x\in\Bbb{R},y\ge f(x)\}
$$
and repeat your reasoning. The constraint is "linear", hence, the set is convex for any function $f$. Indeed, it is convex in $y$ for any fixed $x$, however, you need it to be jointly convex in $(x,y)$, which is true only for convex functions.
Something similar happens in your example. The "linear" constraints make the set convex for fixed $(a,b)$, but different $(a,b)$ results in very different sets $u'\le u''$, making the "linear" constraints on $q$ be different too. Non-linearity (and non-convexity as well) is hidden in the coefficients $\pm 1$ that do depend on $(a,b)$ (via different indices for $q$).
For example, if we consider the following
$$
q=\begin{bmatrix} x&y&1&0\\x&y&1&0\\x&y&1&0\\0&0&0&0
\end{bmatrix}
$$
then you may just check that it satisfies all the constraints


*

*for $a=b=1$ iff $0\le y\le x\le 1$,

*for $a=b=-1$ iff $0\le x\le y\le 1$,

*for $a=b=0$ iff $0\le x=y\le 1$.


Now it is easy to make a counterexample for convexity, e.g. choose $x_1=0.5$, $y_1=0$ in the first case and $x_2=0$, $y_2=1$ in the second case. In the midpoint, $0.25\ne 0.5$.
