How to linearize piecewise nonlinear function?
AnsweredI establish a bilevel optimization model, in the lowerlevel, the objective function is a piecewise nonlinear function, like y=(xc)^a, for x>=c. y=k(cx)^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

I assume you want to use KKT conditions because you want to turn your bilevel 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(cx)^b\) is nonconvex and you cannot construct a single level problem. However, if your nonlinear constraint reads \(y \geq k\cdot (cx)^b\) and \(k \cdot (cx)^b\) is convex for every \(x\) or your nonlinear constraint reads \(y \leq k\cdot (cx)^b\) and \(k \cdot (cx)^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*(3x)^2\) is convex and you can construct multiple inequalities approximating the power function \(f(x) =2*(3x)^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*(3x)^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.
Comments
1 comment