How to linearize piecewise nonlinear function?

Answered

Z S

• March 21, 2024 13:47

I establish a bi-level optimization model, in the lower-level, the objective function is a piecewise nonlinear function, like y=(x-c)^a, for x>=c. y=-k(c-x)^b, for x<c, a,b,c and k are constant. I want to use KKT conditions to solve my model, so I want to linearize the piecewise nonlinear function. How can i use piecewise linear approximation method to linearize? 

Regards

 

Related to

• Piecewise Linear

0

• 

  Jaromił Najman

  Gurobi Staff

  • March 22, 2024 10:48
  • Edited

  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

Please sign in to leave a comment.