# How to linearize this L0 norm of a vector?

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?

• @RobPratt yes. I have updated my question.
– KGM
Mar 11 at 13:31

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.
• 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
• Pick one variable from each row. For example, $\{x_4,x_{11},x_3\}$ is one such $3$-subset. Mar 11 at 14:19