Matrix equation & integer programming

Question

I have a series of matrix equations that look like:

$$x^TA_ky=b_k$$

with $k = 1, 2, .. n$

and $A_k, b_k$ known double precision matrices, $x$ and $y$ unknown.

Besides,

$$x, y$$

are vectors with each component -1 or 1.

(i) Is there any good method to solve x and y directly?

(ii) If not, what if we relax the integer constraints, and then "round" the x and y to -1 and 1? would it be bad because of the rounding?

(iii) If this is still difficult, I think it may be a good idea to try something like:

$$min\sum_{k=1}^n |x^TA_ky-b_k|^2 + \lambda||x||_2^2 + \mu ||y||_2^2$$ so that the magnitude of x and y are not too "wild".

Can anyone give some suggestions for these kinds of problems? Thanks!

Answer 1

Here is how we can develop a MIP model. We prefer to use binary variable, so let's introduce:

$$p_i, q_i \in \{0,1\}$$

We can interpret:

$$\begin{align} & x_i = 2p_i -1\\ & y_i = 2q_i-1\end{align}$$

I.e. we can map this to $x_i, y_i \in \{-1,+1\}$. We can then write:

$$ \sum_{i,j} x_i y_j a_{i,j}^k = \sum_{i,j} \left(1-2 (p_i \text{ xor } q_i)\right) a_{i,j}^k = b^k $$

This is a bit complicated. It says if $p_i=q_j$ (or equivalently if $x_i=y_j$) then the value of $(1-2 (p_i \text{ xor } q_i))$ becomes $+1$ else it will be $-1$.

This can be linearized as: $$\begin{align} & w_{i,j} \le p_i + q_j \\ & w_{i,j} \ge p_i - q_j \\ & w_{i,j} \ge q_j - p_i \\ & w_{i,j} \le 2 - p_i - q_j \\ & \sum_{i,j} \left(1-2 w_{i,j} \right) a_{i,j}^k = b^k \\ & p_i, q_j, w_{i,j} \in \{0,1\} \end{align}$$

Add a dummy objective and you have your MIP model.

PS. Not many MIP models have an XOR operation. This is interesting. See link for more info about the linearization.

PS2. A small example showing this works:

----     62 PARAMETER a  

            i1          i2          i3          i4          i5

i1       0.998       0.579       0.991       0.762       0.131
i2       0.640       0.160       0.250       0.669       0.435
i3       0.360       0.351       0.131       0.150       0.589
i4       0.831       0.231       0.666       0.776       0.304
i5       0.110       0.502       0.160       0.872       0.265


----     62 PARAMETER b                    =        2.222  

----     62 VARIABLE p.L  

i1 1.000,    i4 1.000,    i5 1.000


----     62 VARIABLE q.L  

i1 1.000,    i2 1.000,    i4 1.000


----     62 VARIABLE w.L  

            i1          i2          i3          i4          i5

i1                               1.000                   1.000
i2       1.000       1.000                   1.000
i3       1.000       1.000                   1.000
i4                               1.000                   1.000
i5                               1.000                   1.000


----     62 VARIABLE x.L  

i1  1.000,    i2 -1.000,    i3 -1.000,    i4  1.000,    i5  1.000


----     62 VARIABLE y.L  

i1  1.000,    i2  1.000,    i3 -1.000,    i4  1.000,    i5 -1.000

Answer 2

As Erwin said in a comment, this can be linearized and solved as an integer linear program. If $A_k$ and $b_k$ are integer-valued, I think it could also be solved as a constraint programming problem. (That might also be true even if they are not integer-valued, but I'm not positive.) If the dimension is not too large, it might be just as easy to solve by partial enumeration.

Regarding your list of items: (i) not that I know of; (ii) I doubt this would work (meaning the rounded solution would likely be infeasible); and (iii) I don't see how this makes sense -- if the domains for $x_i$ and $y_i$ are $\{-1,1\}$, then their euclidean norms are constant (equal to their dimension).