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?

• So cuttting away all the information, you are asking if $q(i,j)\leq q(k,l)$ implies $q(i,j)-q(i,l)-q(k,j)+q(k,l)\geq 0$ is LP-representable? If so, the answer is no. It is MILP-representable though. – Johan Löfberg Oct 10 '18 at 9:35
• The constraint is nonconvex, but can be modelled with linear constraints if you introduce auxilliary binary variables. – Johan Löfberg Oct 10 '18 at 9:46
• I mean that what you are trying to encode is "if this relation hold, then this other relation should hold", i.e. implication between two linear inequalities. – Johan Löfberg Oct 10 '18 at 9:47

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

• Then I simply don't understand the question and notation. My interpretation is that $q$ are the decision variables. Note that the model above enumerates all possible cases, it is not 1 constraint, or a list of selected constraints known a-priori. It is all possible combinations of $(i,j,k,l)$ (i.e in the order of $4^4$) – Johan Löfberg Oct 10 '18 at 10:15
• and if the implications should be triggered by linear relations involving relations between $a$ and $b$ instead such as $\textbf{if } b-a \geq -a$ then $q(1,1)...\geq 0$. , nothing changes. Same idea and approach. – Johan Löfberg Oct 10 '18 at 10:18
• I tried to edit to avoid using any of your variables in the generic example. Fixed now. – Johan Löfberg Oct 10 '18 at 10:32
• Thanks. I need to visualise it in my specific case. (Step 1) My constraint (3) is: $\forall u'\leq u''$ with $u', u''\in \mathcal{Q}(a,b)$, we have that $q(i,j)-q(i,l)-q(k,j)+q(k,l)\geq 0$. This can be rewritten as: $-(u'-u'')\geq 0 \rightarrow q(i,j)-q(i,l)-q(k,j)+q(k,l)\geq 0$. – TEX Oct 10 '18 at 10:57
• (Step 2): introduce $M>0$ and $\delta\in \{0,1\}$ and notice that constraint (3) can be rewritten as: $\forall u', u''\in \mathcal{Q}(a,b)$, $-(u'-u'')\leq M\delta$ and $q(i,j)-q(i,l)-q(k,j)+q(k,l) \geq -M(1-\delta)$. – TEX Oct 10 '18 at 10:57

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

• Thanks. Let me add some considerations: 1) I have already built an algorithm that partitions the space $\mathbb{R}^2$ into partitioning sets such that the matrix $A(\cdot, \cdot)$ is the same inside a partition unit. 2) Following your hint, one could then run the program $(\star) (\star)$ for each partitioning set and then pick the minimum found. – TEX Oct 10 '18 at 16:52
• The main issue here is step 1): in practice, the algorithm constructs a grid on $\mathbb{R}^2$ and then tells me to which partitioning set each point of such a grid belongs to; now, constructing an "exhaustive" grid on $\mathbb{R}^2$ requires too much memory; also, consider that in my actual case I don't have $\mathbb{R}^2$ but $\mathbb{R}^4$ (here I have provided a simplified example). – TEX Oct 10 '18 at 16:52
• This is a "physical" issue that I don't know how to overcome. In other words: I don't know how to get the collection of partitioning sets without constructing the initial grid and constructing the initial grid requires too much memory. – TEX Oct 10 '18 at 17:01
• @TEX My conjecture is that it is enough to compare the basic elements in the table ($-a$, $-b$, and $b-a$, $-b$) to each other to split the space into partitions. It will give you 4 cases (excluding equalities that give more restrictive set of $q$'s). – A.Γ. Oct 10 '18 at 18:10
• I'm not sure I follow. For any $l\in \{1,2\}$, let $\pi$ be an operator applied to $\mathcal{Q}_l(\cdot, \cdot)$ that gives us (1) the positions of the components of $\mathcal{Q}_l(\cdot, \cdot)$ when ordered from the smallest to the largest; (2) the relational operators ($=,<$) between the components of $\mathcal{Q}_l(\cdot, \cdot )$ when ordered from the smallest to the largest. For example, consider $(a,b)=(-500,500)$. Then $\pi(\mathcal{Q}_1(-500,500))=\{4,2,1,3\},\{<,<,<\}$ and $\pi(\mathcal{Q}_2(-500,500))=\{4,2,1,3\},\{<,<,<\}$. – TEX Oct 10 '18 at 18:30