7

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)

KGM
  • 2,265
  • 7
  • 23
  • 2
    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 09 '19 at 00: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 09 '19 at 00:11
  • 1
    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 09 '19 at 07:06

2 Answers2

8

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
  • 6,167
  • 1
  • 17
  • 48
  • 1
    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 09 '19 at 10:57
  • @dipaknarayanan That is correct! – Kevin Dalmeijer Jul 09 '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$ – KGM Jul 09 '19 at 11:06
  • 1
    What is the difficulty? If A(i,j) is given, this is simply a linear constraint. – Kevin Dalmeijer Jul 09 '19 at 11:11
8

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$.

prubin
  • 39,078
  • 3
  • 37
  • 104