Skip to main content

How to linearize piecewise nonlinear function?

Answered

Comments

2 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Jaromił Najman
    • 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, 
    Jaromił

    0

Post is closed for comments.