Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?

Question

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?

Answer 1

$$\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}$$

Answer 2

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.

Answer 3

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.