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?

Solution 1:

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

Solution 2:

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:

1. the first coordinate inequality depends on cases $$ -a<-b,\quad -a=-b,\quad -a>-b. $$
2. 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.