# multivariate piecewise linear equality constraint

 0 Is there a way to transform an optimization problem that is linear except for one equality constraint which is multivariate non-separable piecewise-linear? I found a lot of informations for inequality piecewise-linear constraints, but I've had no luck in finding informations about equality constraints. asked 09 Sep '14, 11:05 giulatona 11●3 accept rate: 0% How are the regions on which your pw-linear function is a particular linear function defined? Does $$f(x)=a'x+b$$ when $$x$$ lies in a (known) hyperrectangle, a polytope with known vertices, a polytope given by inequalities, or something else? (11 Sep '14, 17:26) Paul Rubin ♦♦ My function only has two regions and these are defined through a linear inequality (12 Sep '14, 04:37) giulatona

 2 While in the case of linear constraints, strict equality requirements don't affect the convexity properties of constraints in question (i. e., piecewise-linear equality constraints can still be transformed using the usual techniques) [edited, see @Matthew Saltzman's comment below]. For instance (a simple price function w/ quantity discount), $\begin{array}{l} \min & y\\ \text{s.t.} & y = \begin{cases} x & ,~ 0 \le x \le 10 \\ 10 + .99 * ( x - 10 ) & ,~ 10 < x \\ \end{cases} \\ & x \ge \ldots \\ & x \ge 0 \\ \end{array}$ can be (equivalently) formulated as $\begin{array}{l} \min & y\\ \text{s.t.} & y = 0 * z_1 + 10 * z_2 + ( 10 + .99 * ( M - 10 ) ) * z_3 \\ & x = 0 * z_1 + 10 * z_2 + M * z_3 \\ & 1 = z_1 + z_2 + z_3 \\ & x \ge \ldots \\ & 0 \le x \le M \\ & z ~~\text{SOS2 vars} \end{array}$ In the rather rare case that your modeling language/solver doesn't support SOS2 variables, binary aux. variables have to be introduced; cf. answered 09 Sep '14, 14:31 fbahr ♦ 4.6k●7●16 accept rate: 13% Thank you for your response. I would also like to know if there are situations that allow simple reformulation into linear programming and avoid SOS2 or binary variables. For example, if it was a convex PWL function with a less than constraint I know I don't need binary variables. Are there any similar cases for equality constraints? (11 Sep '14, 06:00) giulatona 2 Piecewise linear equality constraints are nonconvex (unless they reduce to simple linear constraints) even if the PWL function itself is convex, so you won't get away without some sort of nonconvex representation. (11 Sep '14, 10:11) Matthew Salt... ♦ Thank you, is it possible to use SOS2 representations with multivariate functions? From what I've found so far it seems like it is not possible (11 Sep '14, 11:12) giulatona
 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: