Can we split a vector into positive and negative parts in LP?

Question

Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v_1&\dots&v_{n}\end{bmatrix}$ can we write as $v=v_+-v_-$ where $v_+$ agrees with $v$ on non-negative components and is $0$ otherwise and $v_-$ agrees with $v$ on non-positive component and is $0$ otherwise.

Eg: $v=[-1,-3,4,5,0,0,1,2,-3,-4]$ then $v_+=[0,0,4,5,0,0,1,2,0,0]$ and $v_-=[-1,-3,0,0,0,0,0,0,-3,-4]$ holds.

I tried using $\max(0,v_i)\leq v_+(i)$ and $v_-(i)\leq\min(0,v_i)$ operations. I am unable to write this correctly without convex optimization.

$v$ is not a constant for me and is a variable. So is there a way to do this with only feasibility Linear Programming with only perhaps $O(1)$ integer variables?

Answer 1

Unfortunately, in the general case, no.

Consider if we had a single variable $x$, one can then write out $x = x_+ - x_i$, and have that $x_+, x_- \geq 0$.

The problem is that one can increase both $x_+$ and $x_-$ by any value $\Delta$ and the value for $x$ stays the same. There isn't any convex way to enforce that one of the values is 0. $\min\{x_+, x_-\} = 0$ is non-convex. One can understand that trying to enforce this is non-convex, by considering two axes, one for $x_+$ and the other for $x_-$. Requiring that one of them be 0, is equivalent to enforcing that the solution must lie on an axis - any penalty incurred where they are both non-zero (e.g. $\min\{x_+, x_i\}$, or $x_+ x_-$), then implies non-convexity.

One may be able to deal with this in an acceptable way by applying an $\ell_1$ penalty of $c(x_+ + x_-)$ for some small constant $c$ which doesn't cause too much distortion to the objective.

Of course, if the number of variables for which one wants to apply this is small enough, one can always consider solving all the different options explicitly (i.e., $x_+ \geq 0, x_- = 0$, $x_- \geq 0, x_+ = 0$), but this will only work for a very small number of variables.

Otherwise, one needs to resort to non-convex optimization techniques, which of course aren't guaranteed to find a global minimum.