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's gravatar image

aguigue
111
accept rate: 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.

link

answered 27 Aug '16, 16:44

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 27 Aug '16, 16:45

yi = fi(x) does not describe a convex set even if f is convex, so we should not expect an efficient solution method.

link

answered 28 Aug '16, 09:44

Petter's gravatar image

Petter
236
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 26 Aug '16, 17:01

Seen: 878 times

Last updated: 28 Aug '16, 09:44

OR-Exchange! Your site for questions, answers, and announcements about operations research.