Optimization problem where in the objective function the optimizer is divided by the square root of its L1 norm

Question

I met an optimization problem as follow: $$\max_{\bf{x}} \frac{\bf{c}^T\bf{x}}{\sqrt{||\bf{x} ||_1}}, \\ s.t. \quad \bf{x}\in\{0,1\}^N \\ || \bf{x}||_1 \le M$$ where $\bf{x}$ is a non-zero binary vector and $M$ is given. My attempt was to replace $\frac{\bf{x}}{\sqrt{||\bf{x} ||_1}}$ with $\bf{t}$. So the problem becomes:

$$\max_{t}\bf{c}^T\bf{t} \\ s.t. \quad \bf{t} \in \mathbb{R}^N\\ ||\bf{t}||_1 \le \sqrt{M}$$

The problem seems to become easier, since it is now a linear programming over a L1 norm ball. But my concern is that those two problems are not equivalent, however, I couldn't figure out other methods to approach the original problem. Could anyone point me out some resources to tackle the problem?

Answer 1

For every $k$ between $1$ and $M$, solve the MILP with the constraint $\sum x_i = k$. With the sum (i.e. 1-norm) fixed, the denominator does not influence the optimal solution. Hence, you want to maximize $c^Tx$ with the constraint that you have exactly $k$ non-zeros. The optimal solution is obtained by ordering $c$ and picking the $k$ largest elements and set the corresponding elements in $x$ to 1, no MILP solver needed. Record the optimal objective, and do this for all $k$, and pick the best.

In summary, let $s$ be the sorted version of $c$, and find $\max_k \frac{\sum_{i = 1}^{k}s_i}{\sqrt{k}}$