Xrfgtjtk

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:

$$minsum_{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!

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-1end{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

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