6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Oct 10 '18 at 9:35
  • $\begingroup$ The constraint is nonconvex, but can be modelled with linear constraints if you introduce auxilliary binary variables. $\endgroup$ – Johan Löfberg Oct 10 '18 at 9:46
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Oct 10 '18 at 9:47
3
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$) $\endgroup$ – Johan Löfberg Oct 10 '18 at 10:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Johan Löfberg Oct 10 '18 at 10:18
  • $\begingroup$ I tried to edit to avoid using any of your variables in the generic example. Fixed now. $\endgroup$ – Johan Löfberg Oct 10 '18 at 10:32
  • $\begingroup$ 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$. $\endgroup$ – TEX Oct 10 '18 at 10:57
  • $\begingroup$ (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)$. $\endgroup$ – TEX Oct 10 '18 at 10:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – TEX Oct 10 '18 at 16:52
  • $\begingroup$ 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). $\endgroup$ – TEX Oct 10 '18 at 16:52
  • $\begingroup$ 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. $\endgroup$ – TEX Oct 10 '18 at 17:01
  • $\begingroup$ @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). $\endgroup$ – A.Γ. Oct 10 '18 at 18:10
  • $\begingroup$ 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\},\{<,<,<\}$. $\endgroup$ – TEX Oct 10 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.