0
$\begingroup$

I have an QP optimization problem.

$\bf x$ is the binary optimizaion variable of size $12\times 1$.

One of the constraints is non-linear/non-convex.

The constraint is L0 constraint.

The constraint I have is

$$[{\bf Ux}]_{l0}\le 2$$

here ${l0}$ denotes the L0 norm of the resulting vector.

$\bf U$ is given by

\begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}

We can linearize the constraint by introducing new variables and adding big_M constraints.

But I need some solution that does not introduce new variables, but uses the matrix $\bf U$ structure.

RobPratt gave some solution here...https://or.stackexchange.com/questions/11784/how-to-model-this-constraint-for-a-qp-problem/11785#11785

How can we model this particular constraint?

Can we define some Matrix that utilizes the characteristics of $\bf U$?

Any solution?

$\endgroup$
1
  • $\begingroup$ @RobPratt yes. I have updated my question. $\endgroup$
    – KGM
    Mar 11 at 13:31

1 Answer 1

4
$\begingroup$

For each $3$-subset $\{x_i,x_j,x_k\}$ of variables that appear in three different rows, you want to enforce $$\lnot(x_i \land x_j \land x_k).$$ As in the linked answer, conjunctive normal form yields ($4^3=64$) linear constraints $$x_i + x_j + x_k \le 2.$$ PORTA verifies that this formulation (including the bounds on $x$) is ideal.

$\endgroup$
2
  • $\begingroup$ would you please explain. What do you mean by each 3 -subset {$x_i,x_j,x_k$} of variables? In row one the variables $x_1,x_4,x_7,x_{10}$ appear. Similarly, in row 2, the variables $x_2,x_5,x_8,x_{11}$ appear.. and so on $\endgroup$
    – KGM
    Mar 11 at 14:15
  • 1
    $\begingroup$ Pick one variable from each row. For example, $\{x_4,x_{11},x_3\}$ is one such $3$-subset. $\endgroup$
    – RobPratt
    Mar 11 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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