I have a 7-14 dimensional piecewise linear cost function I'd like to minimize with two quadratic terms of the form:

$$ f(X) = X^tCX + d \sum_i |x_i-x^*_i|^2 + \sum_i P_i(x_i-x^0_i) $$ $$ \sum_i x_i = 1, 0 \leq x_i \leq 1$$

where $d>0$, $C$ is positive definite and $X^*,X^0$ are fixed.

The $P_i(x_i-x_i^0)$ are continuous and piecewise-linear with an "almost nice" form.

enter image description here

They are always $0$ when $x_i-x_i^0 \leq 0$ and convex piecewise linear when $x_i-x_i^0 \ge 0$, but note that the blue curve is not convex for all $x_i-x_i^0$. So close!

I tried splitting this into $2^7$ to $2^{14}$ convex problems by restricting the domains of $x_i \leq x^0_i, x_i \geq x^0_i$ combinatorially by that was too computationally intensive.

Is there a good (python) solver for functions that are piecewise-linear and quadratic and non-convex? Is there a more clever way to simplify this problem?

  • $\begingroup$ For anyone finding this question years later Moehle et. al. published a solution to the problem recently. arxiv.org/abs/2008.04985 $\endgroup$
    – rhaskett
    Jan 13, 2021 at 5:48

1 Answer 1


You could implement the piecewise linear functions using SOS2 variables (SOS2=Special Ordered Sets of Type 2). This approach does not care about convexity (that is, convexity related to the piecewise linear functions; for most solvers it is still important that the quadratic terms are convex). MIQP (Mixed Integer Quadratic Programming) solvers with support for SOS2 variables and callable from Python are readily available. If an MIQP solver does not support SOS2 variables, we can simulate them with binary variables. Some solvers to consider are Cplex, Gurobi, SCIP.

If the non-convexities only appear at $x=0$, we can optimize the formulation. We will still arrive at an MIQP model.

  • $\begingroup$ Thanks a bunch. After some exploration these SOS2 variables look like a promising solution. Quick follow up. I noticed CPlex/Gurobi/SCIP are all commercial solvers. Is there an open source solver that has the same functionality? $\endgroup$
    – rhaskett
    Aug 3, 2018 at 17:07
  • $\begingroup$ Sorry, I am not aware of an open source MIQP solver (they may well exist: I just never used any). $\endgroup$ Aug 3, 2018 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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