Skip to main content

## Comments

1 comment

• 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ł

Please sign in to leave a comment.