1
$\begingroup$

I have an optimization problem that I'm trying to cast as a linear program. However, I have an objective function of the form

$$\begin{array}{ll} \text{maximize} & a_1 x_1 - a_2 \lvert x_1\rvert\\ \text{subject to} & \color{gray}{\text{(constraints)}}\end{array}$$

I tried doing the classic linear reformulation using a replacement variable $x_1'$ and adding the constraints:

$$x_1 - x'_1 \le 0$$

$$-x_1 - x'_1 \le 0$$

The problem that I ran into is that the solutions seem to be constraining $x_1$ to positive values, even when they obviously should be negative. Looking at the docs I have on this, it seems that this is because the assumption is that all values of it will be maximized or minimized in the same direction and if you break this assumption then you're forced to utilize the M/ILP method with binary determiners in order to solve this.

I haven't found any discussion on the limitation of using the variables $x_1$ and $x'_1$ in the objective function. Is it possible to do what I want without resorting to ILP?

$\endgroup$
  • $\begingroup$ So far one thing we're considering is splitting the value for $x1$ into a positive and negative component, then doing operations on the positive and negative component separately. If it ends up working I'll report back here. $\endgroup$ – Nate Diamond Apr 20 '17 at 0:02
3
$\begingroup$

$$\begin{array}{ll} \text{maximize} & a_1 x - a_2 | x |\\ \text{subject to} & \color{gray}{\text{(linear constraints)}}\end{array}$$

where $a_1, a_2 \in \mathbb R$ are given. Writing as a minimization problem,

$$\begin{array}{ll} \text{minimize} & a_2 | x | - a_1 x\\ \text{subject to} & \color{gray}{\text{(linear constraints)}}\end{array}$$

The objective function to be minimized is

$$f (x) := a_2 |x| - a_1 x = \begin{cases} -(a_1 + a_2) \, x & \text{if } x \leq 0\\ \,\,\,\,(a_2 - a_1) \, x & \text{if } x \geq 0\end{cases}$$

If $a_1, a_2 \geq 0$, then $f$ is convex. In that case, the epigraph of $f$ is also convex and can be defined by the intersection of half-spaces, as follows

$$\left\{ (x,y) \in \mathbb R^2 \mid y \geq (a_2 - a_1) \, x \land y \geq -(a_1 + a_2) \, x \right\}$$

and we have the following linear program in $x, y \in \mathbb R$

$$\begin{array}{ll} \text{minimize} & \,\,\,\, y\\ \text{subject to} & \,\,\,\,(a_2 - a_1) \, x - y \leq 0\\ & -(a_1 + a_2) \, x - y \leq 0\\ & \,\,\,\,\,\color{gray}{\text{(linear constraints on } x)}\end{array}$$

$\endgroup$
3
$\begingroup$

You could split the original problem into two linear programming problems, the first with objective $f(x_1)=a_1 x_1 -a_2 x_1$ and (additional) constraint $x_1\geq 0$, and the second with objective $f(x_1)=a_1 x_1 + a_2 x_1$ and (additional) constraint $x_1 <0$. Then you would select the best of the two solutions as the solution of the original problem.

$\endgroup$
  • $\begingroup$ But it may be that these two problems don't have individual solutions but are unbounded. $\endgroup$ – Wolfgang Bangerth Apr 21 '17 at 2:37
  • $\begingroup$ @WolfgangBangerth Wouldn't this mean that the original problem is also unbounded? $\endgroup$ – Stelios Apr 21 '17 at 11:43
  • $\begingroup$ No -- try to maximize $-|x|$. It clearly has a maximum. But neither $-x$ nor $-(-x)$ do. $\endgroup$ – Wolfgang Bangerth Apr 21 '17 at 17:49
  • $\begingroup$ Oh, but I now see that you want to add additional constraints. Then I suppose this makes sense. $\endgroup$ – Wolfgang Bangerth Apr 21 '17 at 17:50
0
$\begingroup$

Splitting the variable into positive and negative components seems to have worked for us. I'll include my solution, though there are likely limitations to the scope of the solution.

Basically, for each variable $x_1$, we split the variable into two: $x_{1+}$ and $x_{1-}$. We then added the constraints:

$-x_{1+}\le 0$

and

$x_{1-}\le 0$

We were then able to apply our value function for coefficients to each part individually. For instance,

$f(x_{1+},x_{1-}) = a_1 x_{1+} - a_1 x_{1-}$

With the final solution for the variable $x_1$ being:

$x_1 = x_{1+} + x_{1-}$

After we attempted this and proved it out, we found discussion on the method here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.