Consider e.g. a binary integer linear programming problem

$$ \text{min}\ {\bf c}^T {\bf x} $$
s.t.
$$ {\bf A} {\bf x} = {\bf b},\ {\bf G} {\bf x} \le {\bf h},  \ x_i \in \{-1, 1\} $$
 
We can put this into your framework with ${\bf Q} = 0$, by replacing $x_i \in \{-1,1\}$ by the bounds $-1 \le x_i \le 1$ and changing $c_i$ to 
$$ c'_i = \cases{c_i - M & $x_i \ge 0$\cr c_i + M & $x_i < 0$}$$

If $M$ is sufficiently large (but still on the same order of magnitude as 
the other coefficients, so the size of the new problem is essentially the same as that of the old one), this will cause the minimum to occur at a point where all $x_i \in \{-1,1\}$.

Since binary integer programming is NP-hard, and it has a polynomial-time reduction to your problem, your problem is also NP-hard.

EDIT:  With the added condition that $c_i^+ \ge c_i^-$, this doesn't apply.  The objective is now convex, and local search methods will work.  Look up
convex optimization - in particular, you might read Boyd and  Vandenberghe, 
["Convex Optimization"](http://www.stanford.edu/~boyd/cvxbook/).