Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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)
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.
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$.
