Quadratic Programming With Piecewise Linear Term

Question

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.

Answer 1

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).

Answer 2

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".

Answer 3

I would try first to solve this as a standard MIQP (Mixed Integer Quadratic Programming) problem using variable splitting:

$$\begin{align} &\min \frac{1}{2}x'Qx + \sum_i \left( -c_i^- x_i^- + c_i^+ x_i^+ \right)\\ &x_i = x_i^+-x_i^-\\ &x_i^+ \le \delta_i x_i^{up}\\ &x_i^- \le (1-\delta_i) (-x_i^{lo})\\ &Ax=b\\ &Gx \le h\\ &x_i^+,x_i^- \ge 0\\ &\delta_i \in \{0,1\}\\ &x_i^{lo}\le x_i \le x_i^{up} \end{align}$$

I assume here $x_i^{lo}$ and $x_i^{up}$ are lower- and upper-bounds on $x_i$.

Solvers like Cplex and Gurobi can solve this type of problem directly. Depending on the size they may solve this in a reasonable time. If this turns out to be too difficult you can set an allowed gap (e.g. 5% or 1%) to let the solver stop early and produce a good solution instead of a proven optimal solution.