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

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?

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

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