Simplex Solver - is it possible to enforce maximum number of non-zero weights?

Question

I have a problem which I am trying to solve using a simplex solver (but I am happy to use any approach that works).

$$ a_1 x_1 + a_2 x_2 + ... + a_n x_n= TotalCost $$ Where $a_i$ are constant inputs and $x_i$ are the weights that I am optimizing.

I have a constraint that the sum of weights needs to add up to one $$ \sum^n_{i=1} x_i = 1 $$

I wish to have the largest possible number of non-zero weights. However, some weights will be zero (because they have a very high cost). There are solutions to this (such as this Q). However, this doesn't seem to work with my constraint that the weights always sum to one.

How to impose sparsity (or the opposite) in this case?

--- Added later ---

Take for example $n=4$ $$ a = (0.2, 0.25, 0.25, 1.0)$$ The lowest cost solution is $x = (1, 0, 0, 0)$ but I would like to biase the solution such that $x = (0.8, 0.1, 0.1, 0)$ becomes optimal.

My first instinct would be to add a term of the form $$ \lambda \sum^n_{i=1} x_i^2 $$ where $\lambda$ is a constant (i.e. something aking to a $L_2$ regularization) but that is no longer linear.

One can add an $ \alpha \ z$ term, where $ z \ge x_i \ \forall \ i$ but such a constraint seems to either do nothing (when $\alpha$ is too small) or force all $x_i$ that are non-zero to be equal.

Answer 1

Assumptions:

• $0 < a_1 \le \cdots \le a_n$.$\\[2pt]$
• The weights $x_1,...,x_n$ are required to be nonnegative.

The objective is to minimize the total cost $$C=a_1x_1 + \cdots + a_nx_n$$ subject to $$x_1 + \cdots + x_n=1$$ but also, you want to impose to some additional constraints . . .

• As many of $x_1,...,x_n$ are nonzero as possible.$\\[4pt]$
• If $a_k < a_{k+1}$, then $x_k > x_{k+1}$.

As a proposed solution, you could add the constraints $$x_k \ge \left({\small{\frac{a_{k+1}}{a_k}}}\right)x_{k+1}$$ for $1\le k \le n-1$, together with the constraint $$x_n \ge d$$ for some fixed positive constant $d$.

Answer 2

You could add extra binary variables $y_i$ that take value $0$ when $x_i=0$ and penalize $1-y_i$ in the objective function:

Add the following constraint, where $\varepsilon$ is a small constant $<1$: $$ x_i\ge \varepsilon \;y_i\\ y_i \in \{0,1\} $$

Then minimize the following term in the cost function, where $p$ is another constant (the penalty): $$ p\sum_{i}(1- y_i)$$

When $x_i>\varepsilon$, $y_i=1$ and no penalty is accounted for in the objective function. When $x_i=0$, $y_i=0$ and the cost function is penalized. The difficulty may be in finding the best value for $\varepsilon$.