0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am well aware of this - unfortunately there is no way to enforce that $\min(|v_+|,|v_-|) = 0$ as this is a non-convex constraint. One also can't apply a penalty to this, even within the larger setting of convex optimization (i.e., there can't be a penalty term of $\min(|v_+|,|v_-|)$ as this is non-convex). $\endgroup$ – MotiN Jul 19 '18 at 7:49
  • $\begingroup$ Agreed, I will edit the answer to be clearer $\endgroup$ – MotiN Jul 22 '18 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.