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