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? Jul 9, 2019 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? Jul 9, 2019 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. Jul 9, 2019 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$
– KGM
Jul 9, 2019 at 10:57
• @dipaknarayanan That is correct! Jul 9, 2019 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$
– KGM
Jul 9, 2019 at 11:06
• What is the difficulty? If A(i,j) is given, this is simply a linear constraint. Jul 9, 2019 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.
– KGM
Jul 9, 2019 at 20:45
• @dipak narayanan Is A psd? Jul 9, 2019 at 21:00
• @MarkL.Stone, no, it is not. eig(A) gives both positive and negative values.
– KGM
Jul 9, 2019 at 21:08
• Then +1 for @prubins 's idea, but no dice in this case. Jul 9, 2019 at 21:14