Skip to main content

How to linearize piecewise nonlinear function?



1 comment

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    I assume you want to use KKT conditions because you want to turn your bi-level problem into a single level one.

    In this case, your model has to be continuous and convex. Only then, it is possible to use KKT conditions for constructing a single level problem, because there is no duality gap.

    This means, that the nonlinear constraint you want to approximate has to be convex. A nonlinear equality constraint is by definition nonconvex, i.e., \(y = -k\cdot(c-x)^b\) is nonconvex and you cannot construct a single level problem. However, if your nonlinear constraint reads \(y \geq -k\cdot (c-x)^b\) and \(-k \cdot (c-x)^b\) is convex for every \(x\) or your nonlinear constraint reads \(y \leq -k\cdot (c-x)^b\) and \(-k \cdot (c-x)^b\) is concave for every \(x\), then you can approximate the nonlinear function by linear tangents and use your KKT approach.

    For example, the nonlinear constraint \(y \geq 2*(3-x)^2\) is convex and you can construct multiple inequalities approximating the power function \(f(x) =2*(3-x)^2\). One such approximating inequality would be given by \(y \geq m*x +b\) where to compute \(m\) and \(b\) you choose an arbitrary point \(x'\) in in the domain of \(x\) and compute \(m(x') = f'(x') = -4\cdot(3 - x')\) and \(b(x') = f(x')-m*x'\). You should use multiple points \(x'\) to construct multiple linear inequalities and approximate \(f(x)\) well enough. Probably ~20 should be good enough to start with. In your model, you would replace  \(y \geq 2*(3-x)^2\) by the constraints \(y \geq m(x')*x +b(x')\) for all points \(x'\) you used. This will give you a convex linear problem, which you can then dualize and apply your KKT conditions to construct a single level model.

    Best regards, 


Please sign in to leave a comment.