How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint.

$$\max \eta$$

subject to

$${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$

here

$$\bf{A}$$ is a Binary Matrix of size $$N\times N$$ (given, known)

$$\bf{U}$$ is an optimization variable matrix $$\bf U$$ of size $$N\times M$$ (Binary matrix)

• Welcome to OR.SE! It's a little unclear what you are asking. You said you are "having a hard time with the constraint," but what sort of trouble are you having exactly, what have you tried already, and what are you asking for help with? – LarrySnyder610 Jul 9 '19 at 0:10
• It might also help if you explain where this problem arises from (provide some context) and whether it is a homework-type problem, or part of a research project or something like that -- in other words, do you know for sure that it is possible to linearize/convexify (if that is indeed what you are asking), or are you trying to figure out whether it is possible? – LarrySnyder610 Jul 9 '19 at 0:11
• Also, if the question is only about the last constraints, maybe you can remove the other constraints and simplify the notation. For example, $x^\top A x = 0$. If you modify the notation, I will edit my answer accordingly. – Kevin Dalmeijer Jul 9 '19 at 7:06

The constraints $${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$ can be rewritten as $$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$

Next, you can linearize each of the $$U(i,m)U(j,m)$$ terms as explained here.

• Thanks for your answer. So, we can linearize each of the $U(i,m)U(j,m)$ terms by introducing $Z(i,j,m)=U(i,m)U(j,m)$ and adding the following constraints $Z(i,:,m) \leq U(i,m)\\Z(:,j,m) \leq U(j,m)\\Z(i,j,m) \geq U(i,m) + U(j,m) - 1$ – dipak narayanan Jul 9 '19 at 10:57
• @dipaknarayanan That is correct! – Kevin Dalmeijer Jul 9 '19 at 11:00
• however, I am having difficulty in expressing the main constraint: $\sum_{i=1}^N\sum_{j=1}^NA(i,j)Z(i,j,m)=0$ – dipak narayanan Jul 9 '19 at 11:06
• What is the difficulty? If A(i,j) is given, this is simply a linear constraint. – Kevin Dalmeijer Jul 9 '19 at 11:11

Kevin Dalmeijer's answer is correct for the general case. Since $$A$$ is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a typical equation with the simpler notation $$x^T A x = 0$$ (mostly to save typing).

A square matrix $$A$$ may have a square root $$B$$, such that $$BB=A$$. In some cases, such as when $$A$$ is positive semidefinite (implying symmetric), the square root is guaranteed to exist and will be symmetric ($$B^T=B$$). (If $$A$$ is positive definite, $$x^TAx=0\implies x=0$$ and there's not much to solve.) If your $$A$$ is such a matrix, you can compute the square root $$B$$ before solving the problem, rewrite $$x^T Ax=0$$ as $$x^TB^TBx=0$$, and observe that this is equivalent to $$Bx=0$$.

• In this problem, $\bf A$ is a binary matrix, and it is symmetric. – dipak narayanan Jul 9 '19 at 20:45
• @dipak narayanan Is A psd? – Mark L. Stone Jul 9 '19 at 21:00
• @MarkL.Stone, no, it is not. eig(A) gives both positive and negative values. – dipak narayanan Jul 9 '19 at 21:08
• Then +1 for @prubins 's idea, but no dice in this case. – Mark L. Stone Jul 9 '19 at 21:14