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