1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 '18 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$ – Erwin Kalvelagen Aug 3 '18 at 17:41
  • $\begingroup$ Worth a shot. Thanks. $\endgroup$ – rhaskett Aug 3 '18 at 18:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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