How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

Question

I am looking for an algorithm to solve the following optimization problem

$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.

In my numerical experiments, $\mathbf{w} = \sum_i \mathbf{x}_i$ does not solve problem.

Can anyone give me a hint? Thanks!

Answer 1

Let $L_i$ be a constant lower bound on $\mathbf{w}^T \mathbf{x}_i$. You can linearize the problem by introducing binary decision variable $y_i\in\{0,1\}$ to indicate whether $\mathbf{w}^T \mathbf{x}_i \ge 0$. The problem is to maximize $\sum_i (2y_i-1)$ subject to linear "big-M" constraints $$ -\mathbf{w}^T \mathbf{x}_i \le -L_i(1-y_i) \quad \text{for all $i$} \tag1\label1 $$ that enforce the logical implication $$ y_i = 1 \implies \mathbf{w}^T \mathbf{x}_i \ge 0 \quad \text{for all $i$}. \tag2\label2 $$ Some solvers support "indicator" constraints \eqref{2} directly without requiring the user to explicitly declare linear constraints \eqref{1}.

Answer 2

If you have machine learning libraries handy, you can use gradient ascent to find the maximum or at least a good approximation for the maximum.

We first need to replace $\text{sgn}$ with an increasing continuous (and most likely smooth) bijection $\sigma:\mathbb{R}\rightarrow(a,b)$ such as the $\tan^{-1}$ or $\tanh$ functions. We should also normalize the vectors $x_i$ so that $\|x_i\|=1$ for all $i$. One can then maximize $\sum_{i}\sigma(w^Tx_i)$ using gradient ascent.

I do not have any proof that this algorithm tends to produce the actual maximum value, but I did a few basic computer experiments using this algorithm, and this algorithm seems to be satisfactory if you do not expect a proof that everything works perfectly.

My experiments indicate that after training, the values $\sigma(w^Tx_i)$ tend to be either very close to $a$ or $b$. This means that $\sum_i\sigma(w^Tx_i)\approx \frac{(a+b)\cdot n}{2}+\frac{(b-a)}{2}\sum_i\text{sgn}(w^Tx_i)$ where $n$ is the number of vectors of the form $x_i$, so by maximizing $\sum_i\sigma(w^Tx_i)$ we simultaneously maximize $\sum_i\text{sgn}(w^Tx_i).$ We usually (but not always) get the same value $\sum_i\text{sgn}(w^Tx_i)$ regardless of the initialization, choice of $\sigma$, or optimizer.