Answers to: Linearization of constraints described as convex functionshttp://www.or-exchange.com/questions/14143/linearization-of-constraints-described-as-convex-functions<p>I have a problem with constraints of the form yi = fi(x), where x and yi are variables, and f_i are nonlinear functions. </p>
<p>Our approach consists of linearizing the function fi and using SOS2 constraints to model the resulting piecewise linear functions.</p>
<p>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?</p>
<p>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?</p>
<p>Thanks</p>
<p>Alexis</p>enSun, 28 Aug 2016 09:44:02 -0400Answer by Petterhttp://www.or-exchange.com/questions/14143/linearization-of-constraints-described-as-convex-functions/14145<p>yi = fi(x) does not describe a convex set even if f is convex, so we should not expect an efficient solution method.</p>PetterSun, 28 Aug 2016 09:44:02 -0400http://www.or-exchange.com/questions/14143/linearization-of-constraints-described-as-convex-functions/14145Answer by Paul Rubinhttp://www.or-exchange.com/questions/14143/linearization-of-constraints-described-as-convex-functions/14144<p>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.</p>
<p>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.</p>Paul RubinSat, 27 Aug 2016 16:44:43 -0400http://www.or-exchange.com/questions/14143/linearization-of-constraints-described-as-convex-functions/14144