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

Numerical Example

$ \min{|x_1| + 2|x_2| + |x_3|} $

$ \begin{align} \ s.t. x_1 + x_2 - x_3 \le 10 \\ x_1 - 3x_2 + 2x_3= 12 \end{align} $

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 \le x_1 \le U_1 $

$ -U_2 \le x_2 \le U_2 $

$ -U_3 \le x_3 \le 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{align} \ s.t. x_1 + x_2 - x_3 \le 10 \\ x_1 - 3x_2 + 2x_3= 12 \end{align} $

$ x_1 - 3x_2 + 2x_3 = 12 $

$ -U_1 \le x_1 \le U_1 $

$ -U_2 \le x_2 \le U_2 $

$ -U_3 \le x_3 \le 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 $.