Piecewise-Linear Quadratic Optimization for an "Almost Convex" Problem

Question

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.

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?

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.