# Linearization of constraints described as convex functions

 0 I have a problem with constraints of the form yi = fi(x), where x and yi are variables, and f_i are nonlinear functions. Our approach consists of linearizing the function fi and using SOS2 constraints to model the resulting piecewise linear functions. Q1: a few of the functions fi are actually convex. Is there a different way of handling the constraint than the one described above that would exploit the convexity property? Or is there maybe some strategies that can used at optimization time? Q2: say that all the fi are convex (Scenario 1) or nonconvex (Scenario 2)? Should I expect a difference in terms of resolution time? In other words, when modelling with SOS2 constraints, does the property of the fi matter? Thanks Alexis asked 26 Aug '16, 17:01 aguigue 11●1 accept rate: 0%

 0 Q1: If $$f_i()$$ is convex, the pw-linear (SOS2) approximation $$\ell_i()$$ will overestimate it, i.e., $$y_i=f_i(x)\le \ell_i(x)$$. If it happens that the $$f_i$$ are not just convex but also differentiable with closed-form gradients, you can trap $$y_i$$ between the pw-linear approximation and the tangent: $$f_{i}(\hat{x})+\nabla f_{i}(\hat{x})\left(x-\hat{x}\right)\le y_{i}\le\ell_{i}(x)$$ where $$\hat{x}$$ is the value of $$x$$ in a proposed incumbent. The lower limit on $$y_i$$ can be added on the fly using a callback if your MIP solver supports such callbacks. Q2: I don't have a definitive answer, but given how few valid generalizations there are about MIP models, I'd be surprised if one popped up here regarding execution time. answered 27 Aug '16, 16:44 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19%
 0 yi = fi(x) does not describe a convex set even if f is convex, so we should not expect an efficient solution method. answered 28 Aug '16, 09:44 Petter 23●6 accept rate: 0%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×65
×27
×20
×3
×1