The problem I have can be defined as:
$$
\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}
$$
s.t. linear equality constraints:
$$
\mathbf{Ax=b}
$$
and linear inequality constraints:
$$
\mathbf{Gx \leq h}
$$
$\mathbf{Q}$ is positive semi-definite. The only difference to the regular quadratic programming is that $\mathbf{c}$ is piecewise:
$$
c\_i=
\begin{cases}
c^+\_i & x\_i \geq 0 \\
c^-\_i & x\_i < 0 
\end{cases}
$$
so the objective function is continuous at $x\_i=0$.


Can someone let me know how to solve this problem ? Is this problem NP hard ? It seems the objective function is not convex anymore and has many possible local minimums. Can we take advantage of fact that all breakpoints are at zeros ? Any help would be greatly appreciated.


There's a special property I forgot to mention: $c^+\_i > c^-\_i$ in my problem.



Quadratic Programming With Piecewise Linear Term
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).


