# Maximizing the number of nonnegative coordinates of $Wx$

I want to find good incumbent solutions to the following problem: $$\newcommand{\RR}{\mathbb{R}}$$ $$\newcommand{\norm}{\left\Vert#1\right\Vert}$$

Given a matrix $$W \in \RR^{m \times n}$$, find the maximum number of nonnegative coordinates of $$Wx$$, over $$x \in \RR^n \backslash \{0\}$$.

The following linear formulation solves it, however it's not efficient:

\begin{align} \max_{x \in \RR^n, a \in \RR^m} \quad & \sum_{i=1}^m a_i \\ \text{subject to} \quad & \norm{x}_1 = n \\ & -U(1 - a_i) \le w_i^T x \le Ua_i ~\text{for } 1 \le i \le m \\ & a_i \in \{0, 1\} \end{align}

Here $$U$$ is a large enough scalar, say $$U = n\norm{W}_1$$.

I would like to run it on matrices with $$m = 700$$ and $$n = 100$$.

• You can omit the $\le U a_i$. Dec 9, 2021 at 4:44

First, a comment on the MIP model. I assume that the constraint $$\|x\|_1 = n$$ is intended to eliminate $$x=0$$ as a solution. An alternative that works with probability 1 is to generate a random vector $$r\in \mathbb{R}^n$$ from a continuous distribution, say uniform over $$[-1,1]^n$$, normalize it so that $$\|r\|_2=1$$, and use the normalization constraint $$r^\prime x = 1$$. This works unless the optimal $$x$$ is orthogonal to $$r$$, which has probability 0 of occurring given that the distribution of $$r$$ is uniform over a region with positive volume. The reason I suggest this is that eliminates any binary variables added (either by you or the solver) to deal with absolute values.

As far as generating a "good" incumbent, you can apply a number of different metaheuristics. I tried a genetic algorithm (coded in R) on a randomly generated matrix $$W$$. The GA converges in under a minute on my PC using your dimensions (700 x 100), but to compare it to the optimal solution (computed using CPLEX) I scaled the matrix down to 70 x 10. (I tried 700 x 100, but CPLEX did not look as if it was going to terminate in what was an acceptable time for me.) My first trial at 70 x 10 produced an optimal solution with 54 nonzeros versus a GA solution with 51. A retry with a different random number seed yielded an optimum of 59 nonzeros and a GA solution with 57.

• Your first paragraph is really helpful, the absolute values seem bad for optimization. Just that reformulation of the $x \neq 0$ constraint improves performance by at least an order of magnitude. Could you elaborate on the genetic algorithm? Dec 9, 2021 at 14:11
• Assuming you have at least some idea of how GAs work, there's not much to say. The "chromosome" is simply $x$, a vector double-precision values with somewhat arbitrary lower and upper bounds. I generated the $W$ matrix with values in $[-10, 10]$, and I restricted values of $x$ to the same interval, but that was just guesswork. The GA starts with a random population of several hundred $x$ values, using the number of nonnegative components of $Wx$ as the fitness value, and mates and mutates them until a generation limit is hit.
– prubin
Dec 9, 2021 at 16:52
• There is a nice GA library for R, which is what I used, with mostly default parameter settings. If you know R, I'm happy to share the R notebook.
– prubin
Dec 9, 2021 at 16:53
• I adjusted my answer above slightly. First, there was a typo in the domain of $r$. It should be uniform over $[-1,1]$, not $[0,1]$. Second, it's probably good practice in general to normalize $r$. I don't think it's really necessary when the domain is $[-1, 1]$, but in general you want to avoid very large (small) norms for $r$ since they will possibly force $x$ to scale in a way that could conflict with the "big M" (or, here, $U$) constraints.
– prubin
Dec 9, 2021 at 19:05