LP: add extra costs in the objective function for every variable which is not equal to $0$

Question

I am trying to optimise an LP problem but extra costs should be added if a variable is larger than $0$.

For example, if we have the following objective function:

$$\text{minimize} \qquad 2X_1 + 3X_2 + 3X_3$$

For every $X_i$ in the solution that is not $0$ extra costs of 1 should be added to the objective function. So if the solution is $X_1 = 0$ $X_2 = 2$ $X_3 = 3$ Then the total costs are $2 \cdot 0+3 \cdot 2+3 \cdot 3 + 2 = 17$ Is this possible in such a way that it remains a linear program? And is it also possible to only add extra costs if $X_1$ or $X_2$ is not equal to $0$?

Answer 1

No. What you want to do is often called $L_0$ regularization: $$\min_{X}\quad 2X_1 + 3X_2 + 3X_3 + \|X\|_0$$ and this extra term takes you well outside the domain of linear programming (the general form of this problem is known to be NP-hard; relaxations using the $L_1$ norm are very common and are the topic of e.g. compressed sensing). Of course, if you only have a small number of variables $n$ you can brute-force a solution by trying all $2^n$ possible assignments of "zero" or "non-zero" to your variables.

Answer 2

In fact, when parameterized by the number of non-zero variables,
no known algorithm is much faster than just trying
each possibility for what variables are non-zero:


Reduce from Dominating Set:

Each vertex is a variable, and there are no other variables. ​ For each vertex u,
let B_u be the set of vertices v such that [[u,v are adjacent] or [u,v are the same vertex]].
Minimize 0 $\;\;\;\;\;\;\;\;$ subject to, for each u, $\;\;\; 1 \: \leq \: \displaystyle\sum_{v\in B_u} v \:\:\:\:$.
One can constrain them to be non-negative and/or at-most-1
without changing which [possibilities for what variables are non-zero]
let the modified objective function's overall minimum be achieved.


However, that does not indicate anything about the opposite parameterization;
namely, by number of variables which equal zero.