7
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – LarrySnyder610 Jul 9 '19 at 0:10
  • $\begingroup$ 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? $\endgroup$ – LarrySnyder610 Jul 9 '19 at 0:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin Dalmeijer Jul 9 '19 at 7:06
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – dipak narayanan Jul 9 '19 at 10:57
  • $\begingroup$ @dipaknarayanan That is correct! $\endgroup$ – Kevin Dalmeijer Jul 9 '19 at 11:00
  • $\begingroup$ 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$ $\endgroup$ – dipak narayanan Jul 9 '19 at 11:06
  • 1
    $\begingroup$ What is the difficulty? If A(i,j) is given, this is simply a linear constraint. $\endgroup$ – Kevin Dalmeijer Jul 9 '19 at 11:11
8
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.