Transform an optimisation problem into a linearly-constrained quadratic program? I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether there is any trick that allows me to still use algorithms for linearly-constrained quadratic programs to solve my problem. 

Intro: 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\}$

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.

Objective function: The objective function is
$$
T(q)\equiv (b(q))^2
$$
where $b: [0,1]^{d_q}\rightarrow \mathbb{R}$ is a linear function of $q$.

Minimisation problem:
$$
(\star) \hspace{1cm}\min_{\theta \in \Theta} T(q)\\
\text{ s.t. the constraints (1), (2), (3) are satisfied}
$$

Why $(\star)$ is not a linearly-constrained quadratic program: I believe that $(\star)$ is not a linearly-constrained quadratic program because of constraint (3) which makes the feasibility set non-convex (see this answer for explanations). Instead, for a given $(a,b)\in \mathbb{R}^2$, 
$$
(\star) (\star) \hspace{1cm}\min_{q\in [0,1]^{d_q}} T(q)\\
\text{ s.t. the constraints (1), (2), (3) are satisfied}
$$
is a linearly-constrained quadratic program. 

Question: I'm not an expert of optimisation but my understanding is that linearly-constrained quadratic programs are nice because relatively easy to solve. Hence, is there any way that I can solve $(\star)$ still exploiting some advantages of linearly-constrained quadratic programs?
 A: My interpretation is that the question is: How can I assure that the linear inequality $q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0$ holds when $q_{ij} \geq q_{kl}$. 
This is an implication betweeen linear inequalities
$$q_{ij} \geq q_{kl} \Rightarrow q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0 $$
Unfortunately not LP-representable. However, it can be modelled using auxilliary binary variables (thus leading to a mixed-integer quadratic program)
For notational simplicty, consider the generic case for some constraints (not even necessarily linear) $p(x)\geq 0$ and $w(x)\geq 0$ and decision variable $x$
$$p(x) \geq 0 \Rightarrow w(x) \geq 0 $$
Introduce a binary variable $\delta$ and a large number $M$ (more later). The implication is guaranteed to hold if the following two constraints hold
$$p(x) \leq M \delta, w(x)\geq -M(1-\delta)$$
If $p(x)$ is positive, $\delta$ will be forced to be $1$, which forces $w(x)$ to be non-negative.
This is called big-M modelling. When you implement, $M$ should not be made unnecessarily large, but just large enough so that it doesn't affect the feasible space in $x$ when the binary variable is inactive. In your case, assuming the expressions are built from $q$ the difference and sums between your up to 4 $q$ variables can trivially never exceed 4, hence $M=4$ or something like that should be possible. If the variables $a$ and $b$ are involved, you have to know bounds on these so you can bound the expressions accordingly.
If $p(x)$ is a vector of length $n$, and you want the condition to be activated when all elements are non-negative, you would introduce a vector binary variable $\Delta$ in addition to your previous $\delta$, and use $p(x) \leq M\Delta, \delta \geq 1 + \sum\Delta - n$. If all elements are positive, all $\Delta$ binaries will be forced  to be $1$, forcing $\delta$ to be $1$.
A: Here is the idea (see below for clarification). Would it be possible to make a piece-wise convex optimization here? The major problem comes from the constraint (3) that depends on the relation $u'\le u''$. If we think of $q$ as a $16\times 1$ vector then the condition (3) is
$$
A(a,b)q\,\ge 0
$$
where $A(a,b)$ is a $16\times 16$ matrix of $0$ and $\pm 1$ depending on how many relations $u'\le u''$ and of what kind for that $(a,b)$ we have.
However, the relation is quite robust, and it may be worth to partition the space $\Bbb{R}^2\ni (a,b)$ in such a way that the matrix $A(u',u'')$ is the same inside a partition unit. The partition will depend on comparisons (greater than, smaller than or equal to) between the numbers $a$, $b$, $a-b$ from the $q$-table (values for $u'$ and $u''$ affecting $u'\le u''$), should be quite straightforward to formulate. Inside each partition element the set is convex, so we can solve a number of convex problems and then pick the best solution among them.

EDIT: Clarification of the idea.
The critical constraint (3) depends only on the set
$$
U(a,b)=\{(u',u'')\colon u'\le u''\}.
$$
The same set $U$ results in the same matrix $A(a,b)$ and the same set of inequalities for $q$ in (3).
Let's look at the $u'\le u''$ closer:


*

*the first coordinate inequality depends on cases
$$
-a<-b,\quad -a=-b,\quad -a>-b.
$$

*the second coordinate inequality depends on
$$
b-a<-b,\quad b-a=-b,\quad b-a>-b.
$$
It gives you 9 possible different combinations where $U$ is the same. If we ignore equality cases (they give more restrictive set for $q$, which is not good for optimization - check it!) then we are left with 4 cases of different partitions for $(a,b)$ that give the same set of $q$ satisfying (3). For example, the first case is
$$
b<a,\quad b<\frac12 a.
$$
In this case we get for 
$$
q=\begin{bmatrix}
x_1 & y_1 & z_1 & 0\\
x_2 & y_2 & z_2 & 0\\
x_3 & y_3 & z_3=1 & 0\\
0 & 0 & 0 & 0
\end{bmatrix}
$$
the following inequalities in (3)
$$
0\le x_i\le y_i\le z_i,\quad i=1,2,3,
$$
$$
0\le x_{j+1}-x_j\le y_{j+1}-y_j\le z_{j+1}-z_j,\quad j=1,2. 
$$
Other 3 cases can be easily obtained from this one by permutations of the first two columns and rows in $q$ (verify!).
Therefore, it is enough to solve 4 optimization problems, one for each case, and pick the best solution of the four. Each sub-problem is convex.
