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$
3
  • 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$ 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$
4
  • 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$ Jul 9 '19 at 10:57
  • $\begingroup$ @dipaknarayanan That is correct! $\endgroup$ 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$ 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$ 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$
4
  • $\begingroup$ In this problem, $\bf A$ is a binary matrix, and it is symmetric. $\endgroup$ Jul 9 '19 at 20:45
  • $\begingroup$ @dipak narayanan Is A psd? $\endgroup$ Jul 9 '19 at 21:00
  • $\begingroup$ @MarkL.Stone, no, it is not. eig(A) gives both positive and negative values. $\endgroup$ Jul 9 '19 at 21:08
  • 3
    $\begingroup$ Then +1 for @prubins 's idea, but no dice in this case. $\endgroup$ 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.