How about this approach.

Rewrite the linear part of the objective function as $c^Tx = \sum\limits_i c_i x_i = \sum\limits_i c_i^{+}(\frac{x_i+|x_i|}{2}) + c_i^{-}(\frac{x_i-|x_i|}{2})$

Now, firstly you see that you have the superposition of $-|x|$ function that are not convex so the initial problem might be not convex.

Secondly, if all of your $c_i^- \leq 0$ and $c_i^+ \geq 0$ then the function is convex so you can either introduce new variables to handle the modulos or use non-differentiable optimization software to solve this.

Thirdly, you observe that non-convexity happen only if your $c_i^-$ (or +) is greater (less) than 0 and $x_i$ could actually reach the negative (positive) hyperpsace. So, maybe some preprocessing might help to throw away some "bad" coefficients.

In the worst case, as I see, when for example you have an extremely wide polytope, you should check every hyperspace $sign(x_i)=const$ and find a solution there, that is $2^n$ runs which might be too expensive for you.
Edit: why you need to check every hyperspace.
suppose you didn't check $x_i \geq 0$. I set the value of $c^+_i = -M$, where $M$ is sufficiently large, e.g. $M = 2 |\min(Qx,x)$|, which makes the solution of the original problem in this hyperspace.

If your $c_i^+ \geq c_i^-$ than $c^Tx = \sum\limits_i c_i^{+}(\frac{x_i+|x_i|}{2}) + c_i^{-}(\frac{x_i-|x_i|}{2}) = \sum\limits_i c_i^{+}\frac{x_i}{2} + c_i^{-}\frac{x_i}{2} + \frac{|x_i|}{2}(c_i^+ - c_i^-)$ which makes your function convex. To solve this problem you can either introduce new variables $y_i$ and to add constraints $y_i \geq x_i$ and $y_i \geq -x_i$ while replacing $|x_i|$ by $y_i$ and using usual QP software or being very lazy and using non-differenciable optimization straitforwardly (though this approach is not recommended).