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