By definition, a function is nonconvex if it is not convex. Nonconvex functions can be modelled using mixed integer linear constraints. We are interested in the following class of problems with form:
For simplicity, consider one univariate PWL nonconvex function \(f(x)\) with \(K\) pieces. Figure 1 shows a PWL function (on a bounded interval) of form:
\[
f(x) = f(\ell_k) + c_k (x - \ell_k), \ \ell_k \leq x \leq \ell_{k + 1}, k = 0, \ldots, K - 1.
\]
Figure 1: PWL function
For \(k = 0, \ldots, K - 1\), we have:
The function value at breakpoint, \(f(\ell_k)\).
The slope, \(c_k\).
The breakpoint, \(\ell_{k}\).
Modelling Approach 1
We can introduce new variables \(u_0, \ldots, u_{K - 1}\) and \(y_0, \ldots, y_{K - 1}\) and constraints:
and \(f(x)\) can be replaced by \(\sum^{K - 1}_{k = 0} \left[f(\ell_k) + c_k (u_k - \ell_k) \right]y_k\). However, this is not the correct approach because it is nonlinear. The correct approach to model function \(f(x)\) is:
This is correct formulation of the function \(f\) because on intervals that do not contain \(x\) indicator variable \(y_k = 0\) which will also force \(u_k = 0\) and hence the summation terms become:
On the other hand, for interval \(\left[ \ell_k, \ell_{k + 1} \right]\) which contains \(x\), we will have \(y_k = 1\) and \(x = u_k \in \left[ \ell_k, \ell_{k + 1} \right]\) hence the appropriate summation term will become:
and \(f(x)\) can be replaced by \(\sum^K_{k = 0} f(\ell_k) \lambda_k\).
Example
Consider a problem where we are interested in buying supplies from a set of different vendors (offering quantity discounts) to satisfy a total need. The problem can be formualted as:
Assuming that we have \(n\) univariate PWL functions \(f_j(x_j)\), such that function \(f_j(x_j)\) has \(K_j\) pieces, then using the same approach we can model it as:
