Optimization with absolute values

Authors: Matthew Chan (mdc297), Yilian Yin (), Brian Amado (ba392), Peter (pmw99), Dewei Xiao (dx58) - SYSEN 5800 Fall 2020

Steward: Fengqi You

Introduction

Absolute values can make it relatively difficult to to determine the optimal solution when handled without first converting to standard form. This conversion of the objective function is a good first step in solving optimization problems with absolute values. As a result, you can go on to solve the problem using linear programing techniques.

Method

Defining Absolute Values

An absolute value of a real number can be described as its distance away from zero, or the non-negative magnitude of the number. Thus,

$|x|={\begin{cases}-x,&{\text{if }}x<0\\x,&{\text{if }}x\geq 0\end{cases}}$

Absolute values can exist in optimization problems in two primary instances: in constraints and in the objective function.

Absolute Values in Constraints

Within linear equations, linear constraints can exist in several forms.

The first form exists as $|X|=0$, where ${\textstyle X}$ is a linear combination of variables.

In this case, the only solution is if $|X|=0$, simplifying the constraint to $X=0$. Note that this solution also occurs if the constraint is in the form $|X|<=0$ due to the same conclusion (only solution $X=0$).

Second form a linear constraint can exist in is $|X|\leq C$ where ${\textstyle X}$ remains a linear combination of variables and constant ${\textstyle C>0}$.

In this case, we can describe an equivalent feasible solution by splitting the inequality into

$X\leq C$

$-X\leq C$

We can understand this visually as the solution ${\textstyle X}$ must lie between ${\textstyle -C}$ and ${\textstyle C}$, as shown below:

The last case for linear constraints is when $|X|\geq C$.

Visually, the solution space is the complement of the second solution above, resulting in the following representation:

In expression form, the solutions can be written as:

$X\geq C$

$-X\geq C$

As seen visually, the feasible region has a gap and thus non-convex. The expressions also make it impossible for both to simultaneously hold true. This means that it is not possible to transform constraints in this form to linear equations. An approach to reach a solution for this particular case exists in the form of Mixed-Integer Linear Programming, where only one of the equations above is “active”.

Absolute Values in Objective Functions

WIP

Numerical Example

$\min {|x_{1}|+2|x_{2}|+|x_{3}|}$

${\begin{aligned}\ s.t.x_{1}+x_{2}-x_{3}\leq 10\\x_{1}-3x_{2}+2x_{3}=12\end{aligned}}$

We replace the absolute value quantities with a single variable:

$|x_{1}|=U_{1}$

$|x_{2}|=U_{2}$

$|x_{3}|=U_{3}$

We must introduce additional constraints to ensure we do not lose any information by doing this substitution:

$-U_{1}\leq x_{1}\leq U_{1}$

$-U_{2}\leq x_{2}\leq U_{2}$

$-U_{3}\leq x_{3}\leq U_{3}$

The problem has now been reformulated as a linear programming problem that can be solved normally:

$\min {U_{1}+2U_{2}+U_{3}}$

${\begin{aligned}\ s.t.x_{1}+x_{2}-x_{3}\leq 10\\x_{1}-3x_{2}+2x_{3}=12\end{aligned}}$

$-U_{1}\leq x_{1}\leq U_{1}$

$-U_{2}\leq x_{2}\leq U_{2}$

$-U_{3}\leq x_{3}\leq U_{3}$

The optimum value for the objective function is $6$, which occurs when $x_{1}=0$ and $x_{2}=0$ and $x_{3}=6$.

Applications

There are no specific applications to Optimization with Absolute Values however it is necessary to account for at times when utilizing the simplex method.

Consider the problem Ax=b; max z= x c,jx,i. This problem cannot, in general, be solved with the simplex method. The problem has a simplex method solution (with unrestricted basis entry) only if c, are nonpositive (non-negative for minimizing problems).

The primary application of absolute-value functionals in linear programming has been for absolute-value or L(i)-metric regression analysis. Such application is always a minimization problem with all C(j) equal to 1 so that the required conditions for valid use of the simplex method are met.

By reformulating the original problem into a Mixed-Integer linear program, in most case we should be able to use GAMS/Pyomo/JuliaOPT to solve the problem.

WIP

3

• Application in Financial: Reduction to a Linear Programming Problem

maximize ${\textstyle \mu \sum _{j}\!x_{j}\mathbb {E} \!R_{j}-\mathbb {E} \left\vert \sum _{j}\!x_{j}{\tilde {R}}_{j}\right\vert }$

subject to $\sum _{j}\!x_{j}=1$

$\!x_{j}\geq 0$ $j=1,2,..n.$

where $R=\sum _{j}\!x_{j}\!R_{j}$

$\mathbb {E} \!R=\sum _{j}\!x_{j}\mathbb {E} \!R_{j}$

$\mathbb {E} \left\vert \!R-\mathbb {E} \!R\right\vert =\mathbb {E} \left\vert \sum _{j}\!x_{j}{\tilde {R}}_{j}\right\vert$As formulated, this problem is not a linear programming problem. We use the same trick we used in the numeric example to replace each absolute value with a new variable and then impose inequality constraints that ensure that the new variable will indeed be the appropriate absolute value once an optimal value to the problem has been obtained. But first, let us rewrite with the expected value operation replaced by a simple averaging over the given historical data:

Let's see some other applications:

• Minimizing the sum of absolute deviations

• Minimizing the maximum of absolute values

Conclusion

The presence of an absolute value within the objective function prevents the use of certain optimization methods. Solving these problems requires that the function be manipulated in order to continue with linear programming techniques like the simplex method.

References

To be formatted:

1. http://lpsolve.sourceforge.net/5.1/absolute.htm
2. https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut04.pdf
3. https://www.ise.ncsu.edu/fuzzy-neural/wp-content/uploads/sites/9/2019/08/LP-Abs-Value.pdf
4. Vanderbei R.J. (2008) Financial Applications. In: Linear Programming. International Series in Operations Research & Management Science, vol 114. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74388-2_13