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

Failed to parse (unknown function "\s"): {\displaystyle \begin{align} \s.t. x_1 + x_2 - x_3 \le 10 \\ x_1 - 3x_2 + 2x_3= 12 \end{align}}

$-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$.