3
$\begingroup$

I'm trying to solve the following problem for $x$ which is a $n \times 1$ vector and all of its elements should be either $0$ or $1$. And let $X = diag(x)$.

The equation from which I need to derive $x$ is:

$(A + BXCD)x + e = 0$

All matrices are $n \times n$ and have integer elements. The $e$ vector is $n \times 1$ and also has integer elements.

$A$ and $D$ are not invertible. $B$ and $C$ are permutation matrices so they are invertible. And $D$ is like a selection matrix, it sets some columns to zero, and for the columns that should not be zero, $D_{i,i} = 1$.

Also: there will always exist a valid solution for $x$ based on the way the matrices are constructed (beyond the scope of this post but there will always be a solution).

My attempt at a solution... Note that $X$ is idempotent, and $x^{T}X = x^T$, and $Xx = x$. $$ B^{-1}Ax + XCDx + B^{-1}e = 0\\ x^{T}B^{-1}Ax + x^{T}CDx + x^{T}B^{-1}e = 0\\ x^{T}(B^{-1}A + CD)x + x^{T}B^{-1}e = 0 $$

Let $P = B^{-1}A + CD$ and let $f = B^{-1}e$. Without loss of generality, let $Q = (P + P^{T}) / 2$. Note that $Q$ is symmetric but, in general, not invertible.

$$ x^{T}Qx + x^{T}f = 0\\ x^{T}(Qx + f) = 0\\ x = 0\\ x = -Q^{+}f $$ $Q$ is not invertible so $Q^{+}$ is the Moore-Penrose pseudo-inverse. The trivial solution does not solve the original problem (remember I multiplied everything by $x^{T}$) and the pseudo-inverse means that the solution to $x$ will no longer be a binary vector of $0$'s and $1$'s.

Just to throw out another idea, I also tried a minimization like $$ \underset{x}{\text{minimize}}\frac{1}{2}\parallel Qx + f \parallel_{2}^{2} + \frac{\lambda}{2}\parallel x \parallel_{2}^{2} $$ where the regularization term helps solve the equation despite that $Q$ is not invertible. From something I learned in system identification (to be clear this is not a sys ID problem), this is a version of the so-called "normal equations" with optimal solution: $$ x* = (Q^{T}Q + \lambda I)^{-1}Q^{T}(-f) $$ But again, this results in $x*$ that does not satisfy the original constraints of members being $0$ or $1$. Any thoughts or ideas? Am I screwed / this problem is NP-hard? Maybe I can make a change of variables to solve it more easily? In practice the matrices will be quite large (and sparse) so MILP will probably not be feasible.

$\endgroup$

1 Answer 1

1
$\begingroup$

An identification of an error, some thoughts, and perhaps a reduction to subset-sum, showing the problem is hard.

Your argument looks OK up to a certain point. You arrive at $$ x^t (Qx + f) = 0 $$ and conclude that $x^t = 0$ or $Qx + f = 0$. That's incorrect. Any $x$ with either of those properties is a solution, but there may be many others. All that this says is that $x$ is perpendicular to $Qx + f$, and they could easily both be nonzero vectors unless you know something about $Q$ that's not clear to me from your explanation.

Frankly, the matrix $Q$ is the first place where you've introduced fractions (because $B^{-1}$ is still a permutation matrix); it might be better to write your equation as $$ x^t ((2Q) x + 2f) = 0 $$ which now is still an all-integer equation. Better still, define $$ Q = P + P^t, f = 2B^{-1} e $$ (which I'm going to assume are the definitions for the rest of this answer) and then you get your original formula, $$ x^t (Qx + f) = 0 \tag{1} $$ except that now everything in sight is an integer.

My own instinct here would be not to factor your equation as you have, but to complete the square, but having done so, I didn't find it led me anywhere.

One observation is that if both $Q$ and $f$ have all-positive entries, then there's no solution, because letting $x$ be any not-all-zero vector of zeroes and $1$s, $Qx + f$ is a sum of several columns of $Q$, together with $f$, which will therefore be an all positive vector $s$. And $x^t s$ will be a sum of select entries of $s$, therefore positive. All this really tells you is that if $Q$ is all positive, then you probably want to look for negative entries in $f$; those are good places to put "1"s in $x$. Not much use, I know.

Frankly, this looks darned hard.

Wait...here's a reduction to subset-sum. Suppose you have a list of positive integers $s_1, \ldots, s_n$, and want to know whether some subset of them adds up to $K$. Let $M = 1000(s_1 + \ldots s_n)$, and then let $$ Q = diag(s_1, s_2, \ldots, s_n, M) \\ f = (0, \ldots, 0, -(M + K)) $$ A bit-vector $x$ can be viewed as a "selection" from the initial list, with $M$ added as a last item): $x_i$ is $1$ means that "we include $s_i$ in the sum" (and $x_{n+1} = 1$ means that we include $M$). Then $$ x^t Q x $$ is exactly the sum of some subset, possibly with $M$ added in.

Now suppose we can solve $$ x^t Q x + x^t f = 0 $$ for some nonzero vector $x$ (which is what's required for solving your problem). Then $x^t Q x$ will be a sum of positive numbers, so $x^t f$ must contain negative numbers, hence $x_{n+1}$ must be $1$. That means that $$ x^t Q x $$ must be a sum of selected weights from the input set, plus $M$, and we need this to equal $M + K$. If we can find a solution for the first $n$ entries of $x$, then we'd have the sum of our weights being $K$, i.e., we'd have solved the subset-sum problem.

In short: knowing nothing more about $Q$ and $f$ than what you've told us, a general method of finding a "selection vector" $x$ for this problem can also be used to solve the subset-sum problem. So...as expressed by equation $1$, your problem is definitely hard.

$\endgroup$
3
  • $\begingroup$ Thanks for your input and for spotting my error! I forgot to say, but I am already doing the trick of multiplying $x^{T}Qx + x^{T}f = 0$ by 2 to keep everything as integers. I understand your conversion to the subset-sum problem, and I guess, since my version is more "general" and doesn't have the same constraints on $Q$ being diagonal and $f$ being mostly zero, my version is even harder. $\endgroup$
    – tphillips
    Commented Oct 7, 2020 at 14:01
  • $\begingroup$ For practical purposes (as opposed to proofy stuff), if there were some way to pick $s_{1}, ..., s_{n}$ and $K$ to actually solve the subset-sum version of my problem, it would be nice. I see on Wikipedia there are some (pseudo-)polynomial approximations which could still be helpful $\endgroup$
    – tphillips
    Commented Oct 7, 2020 at 14:04
  • $\begingroup$ Yeah...I really know very little about subset-sum except that it's known to be hard. Indeed, it's one of the few known-to-be-hard problems I can state more or less clearly, so I hit it lucky seeing your question. But I have no further insight, alas. $\endgroup$ Commented Oct 7, 2020 at 17:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .