Return to Question

Moved x-post warning to the very top.

Source Link

edit approved Mar 11, 2021 at 7:50

_{Note: Initially posted on MathOverflow.}

I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- x, & x \leq 0 \\ c^+ x, & x > 0 \\ \end{cases} $$

as depicted below

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

$x' \leq c^- x $
$x' \leq c^+ x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

I have heard about SOS constraints. Are they the canonical way to solve this kind of problem ? If my problem contains many such piecewise linear functions, is it reasonable to expect a solver from being able to solve such a problem with thousands of SOS1 constraints ?

Example

$$\begin{array}{ll} \text{maximize} & a \max(x,0) + b \min(x,0) + c \max(y,0) + d \min(y,0)\\ \text{subject to} & x,y \in [−1,1]\end{array}$$

Note

Initially posted on mathoverflow: https://mathoverflow.net/questions/385971/maximizing-a-piecewise-linear-convex-function

I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- x, & x \leq 0 \\ c^+ x, & x > 0 \\ \end{cases} $$

as depicted below

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

$x' \leq c^- x $
$x' \leq c^+ x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

Example

$$\begin{array}{ll} \text{maximize} & a \max(x,0) + b \min(x,0) + c \max(y,0) + d \min(y,0)\\ \text{subject to} & x,y \in [−1,1]\end{array}$$

Note

Initially posted on mathoverflow: https://mathoverflow.net/questions/385971/maximizing-a-piecewise-linear-convex-function

_{Note: Initially posted on MathOverflow.}

I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- x, & x \leq 0 \\ c^+ x, & x > 0 \\ \end{cases} $$

as depicted below

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

$x' \leq c^- x $
$x' \leq c^+ x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

Example

$$\begin{array}{ll} \text{maximize} & a \max(x,0) + b \min(x,0) + c \max(y,0) + d \min(y,0)\\ \text{subject to} & x,y \in [−1,1]\end{array}$$

Source Link

asked Mar 11, 2021 at 7:39

lovasoa

Maximizing a piecewise-linear convex function

I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- x, & x \leq 0 \\ c^+ x, & x > 0 \\ \end{cases} $$

as depicted below

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

$x' \leq c^- x $
$x' \leq c^+ x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

Example

$$\begin{array}{ll} \text{maximize} & a \max(x,0) + b \min(x,0) + c \max(y,0) + d \min(y,0)\\ \text{subject to} & x,y \in [−1,1]\end{array}$$

Note

Initially posted on mathoverflow: https://mathoverflow.net/questions/385971/maximizing-a-piecewise-linear-convex-function